Featured post

Introduction

Among the types of posts you may find in this Blog:

  • Citations: Brief “shout outs” to recent papers citing my work
  • Ideas: Research ideas or other thoughts that might (or might not) be worth pursuing
  • Mentoring: In particular, tips related to my tutorials on “How to Be a Ph.D. Student” and “Presenting a Paper”
  • News: Occasional news about my activities, the Insight centre, Constraint Programming and Artificial Intelligence
  • Papers: A look back at my old papers, with an eye to current relevance

Note that I may edit posts — including this one 🙂 after their original posting.

Comments are encouraged. Use “Leave a Reply”.

Note that you can subscribe to the blog via RSS or follow via email. See the sidebar.

Classification and Acquisition

Classifier-based constraint acquisition, Prestwich, Freuder, O’Sullivan and Browne, Annals of Mathematics and Artificial Intelligence, has been published and is available online.

Modeling a combinatorial problem is a hard and error-prone task requiring significant expertise. Constraint acquisition methods attempt to automate this process by learning constraints from examples of solutions and (usually) non-solutions. Active methods query an oracle while passive methods do not. We propose a known but not widely-used application of machine learning to constraint acquisition: training a classifier to discriminate between solutions and non-solutions, then deriving a constraint model from the trained classifier. We discuss a wide range of possible new acquisition methods with useful properties inherited from classifiers. We also show the potential of this approach using a Naive Bayes classifier, obtaining a new passive acquisition algorithm that is considerably faster than existing methods, scalable to large constraint sets, and robust under errors.

Doing Good

The Operations Research organizations INFORMS and IFORS have initiatives for using technology for good that CP people might want to contribute to:

INFORMS Pro Bono Analytics (PBA) brings together INFORMS members, other analytics practitioners, and nonprofit professionals and organizations working in underserved communities with the goal of enabling these vital nonprofits to begin making data driven decisions. In short, think “helping nonprofits with data” when you think of PBA. Sometimes our work is as complex as building a system to forecast real-time demand for services, and other times it’s as simple as helping an organization choose between analytical tools or organize and store collected data from past fundraising campaigns. Even if your organization is just getting started with data, we can provide advice and assistance on what data to collect, how to collect it, and where to keep it.

The aim of the [IFORS] Developing Countries On-Line Resources page is to offer the OR worker all publicly-available materials on the topic of Operations Research for Development. It also aims to provide a venue for people who are working in the area to share their completed or in-process work, learn from others, and stimulate comments and discussions on the work.

These could be of particular interest to those who participate in the CPAIOR conferences.

ConstrAInts

With the increasing presence and popularity of AI it is important to get the word out that constraint satisfaction is AI. While a strength of the field is its multi-disciplinary nature, it certainly has a ‘home’ — arguably its ‘primary residence’ 🙂 in the AI community. In fact, I’ve argued that constraints are ubiquitous in AI, to the point where they might even serve as a kind of “lingua franca” unifying the subfields of AI. In particular, constraint satisfaction has been used for machine learning and vice versa, and constraints resonate with other currently high profile topics in AI like explanation and human-centric AI.

Members of the constraints community have a very strong presence in the larger AI community. For example, Francesca Rossi, a former president of the ACP, is a past president of IJCAI and future president of AAAI, and Barry O’Sullivan, a former president of the ACP, is a past president of EurAI and a current member of the Executive Council of AAAI.

Microplates, Avenues and Smorgasbords

An entry by Maria Andreina Francisco in a thread at the Constraint Google Group engendered several thoughts, which I thought I’d collect into a blog post. Italics are excerpts from Maria’s entry. 

I’m currently a postdoc at a pharmaceutical bioinformatics group.  

It is always exciting to hear about CP applications to bioinformatics. The last International Workshop on Constraint-Based Methods for Bioinformatics I’m aware of (the 12th, WCB’16) was in 2016. There was one scheduled for 2018, but I’m not sure if it took place, or if there has been one since; does anyone know? Is it time for another? In any case, I’ve added Andreina’s ModRef 2020 contribution on microplate layout design to my nascent page of Sample Applications of CP

I share Alexander’s experience that building a first proof of concept with minizinc is quick and painless, but getting it to work on larger instances with more complex constraints… well, not so quick and painless. 

It appears that there is a research “avenue” opportunity here, which may be difficult to “enter”, but very rewarding if new entrances can be found. Can we conduct some fundamental research addressing the difficulties of practial implementation, especially with regards to “scaling up”? 

For example, I once heard an observation from a practioner that a perceived drawback of CP for end users was that seemingly small changes to the model could have unpredictably big effects on solution time. Somehow that seems like a problem that could be amenable to some fundamental research. 

Some sort of general comment would be that I think it was easier to write models when I knew less about CP.  Nowadays I imagine a model in my head only to realise that all the pieces are not all available in one solver and I need to decide which solver/parts I want to keep and rethink the rest. 

The idea that it could be easier to write models when you know less about CP, because all the pieces you want aren’t available in one solver, is an interesting take on things. Could a ’smorgasbord’ approach — as opposed to a ‘portfolio’ approach 🙂 be implemented that allowed one to pick and choose and assemble the pieces one needed, as needed? Or better yet could one automate this, build a system that analyzed the problem and automatically assembled the pieces to build and operate on an appropriate model? Back to my “Holy Grail” hobbyhorse. 🙂

Erdős-Faber-Lovász

Mathematicians have recently “proven” the Erdős-Faber-Lovász coloring conjecture. I put “proven” in quotes because the proof only works for “large enough” hypergraphs, a restriction that I think is rather cavalierly addressed in the linked article. Nevertheless, it would be interesting to consider whether some of the techniques used in the proof could be adapted for general constraint satisfaction problem solving. At least one technique they use seems already to be related to a CP staple: “hardest first (fail first)” ordering; perhaps some readers can identify others. Even more interesting would be if some of the methods used in the proof suggest new CP techniques. And it would be exciting if any existing CP techniques suggest alternative or improved proofs of the conjecture.

The Power of Social Media

I noticed this week that views of my post on Comparing CP and MIP had gone up 4,940.00%! Of course, that is a bit of a joke, because the prior view count was so tiny. Nevertheless, I was curious as to what caused this sudden attention to an older post. There were also two Comments, which in addition to being helpful additions to the post, provided a clue as to its sudden popularity. One Comment was from Philippe Laborie and the other from Eray Cakici. A little googling revealed that a link to my post had appeared in their Twitter accounts. Philippe tweeted and Eray retweeted.

So let me return the favor by pointing you at the SlideShare presentations of Philippe and Eray. And “keep those cards and letters coming” everyone. An old expression, perhaps I should say nowadays “keep those comments and tweets coming”. 🙂

What’s in a Name

Back in 2004 the Boston Globe newspaper ran a story about “the most influential academic discipline you’ve never heard of”. What was the discipline? Operations research.

Operation everything

It stocks your grocery store, schedules your favorite team’s games, and helps plan your vacation. A primer on the most influential academic discipline you’ve never heard of.

This is rather ironic for those of us in Constraint Programming, since CP deals with many of the same applications as Operations Research, and is, if anything, less well known.

Part of the problem unquestionably lies in the name. “Operations Research”, what is that? The study of hospitals? And the alternative, “Mathematical Programming”, is even worse. Is it mathematics? Is it coding? The only worse name for a field? “Constraint Programming”.

I once had a fellow from a company that I was trying to interest in working with my lab tell me he liked the idea, but ask me if there was some other name for what I did, because “constraints” had such a negative connotation, it turned other people in his company off. Of course, we do have some very positive terms associated with the field: “satisfaction”, “relaxation”, “optimization”. But if I said “I use relaxation for optimal satisfaction”, people might think I was some kind of new age guru.

Indeed even “optimization” is an imperfect standard bearer. I once had a fellow at a commercially-oriented conference tell me that “optimization” could turn his potential customers off. Astonished, I asked why, and he explained that they worried that it meant that the computer would make all the decisions and they would be cut out of the loop. Of course, it doesn’t have to mean that, but perhaps such fears help to explain the current popularity of terms like “human-centred” and “human-aware” as modifiers to “Artificial Intelligence”.

In any case, if we are to compete with such media-friendly terms as “artificial intelligence” and “deep learning” we need to work at getting the message out about what we can do. Actually Operations Research is currently doing a pretty good job of that for their field. See “O.R. & Analytics Impact Everything” at the INFORMS website, and the INFORMS Success Stories.

The ACP has its Success Stories as well, of course, and there are other resources, but we can always do more. I’ve started work on a new page, Sample Applications of Constraint Satisfaction, to make a small contribution towards “getting the word out”.

Refrigerators

I had so much fun with The Application Game that I decided to play again googling “constraint satisfaction problem” and “refrigerator”. I came up with “Service robot planning via solving constraint satisfaction problem“.

The problem of demographic shifts towards the elderly is deteriorating, as the relative number of caregivers is insufficient to provide the support required for their wellbeing, which is further aggravated by the increasingly hectic lifestyle. Service robot is getting more prominent as a possible solution. Robot manipulation and mobility is an important field, but they also require high level planning for these minute actions in order to provide ample support. Automatic service composition, contributed significantly by web services, offers the necessary technology for the task. Robot planning problem can be solved by representing it as constraint satisfaction problem (CSP) due to it being able to support loose binding of services and variables of wider domain. 

What does this have to do with refrigerators?

Given a certain goal, planner module will compose a sequence of plans for the robot to execute such that after the plans are completed, the goal is achieved. For example, given that the goal is to place a canned soft drink in the fridge and that all cabinet needs to be closed, the robot will first find where the soft drink is. If there is one that happens to be in the kitchen cabinet, the robot will approach it, open the cabinet and pick up the soft drink, and then close it. It will subsequently approach and open the fridge, after which it will place the canned drink before closing it. No prior programming is required for the plan.

Ok, tenuous, but this paper illustrates an interesting point.

The paper is published in the ROBOMECH Journal. Its authors are in a Graduate School of System Design, not a computer science department. The closest it comes to referencing the CP literature seems to be a 2008 paper by De Moura and BjØrner on Z3: An efficient SMT solver, in the International Conference on Tools and Algorithms for the Construction and Analysis of Systems and a 2014 paper by Georgievski and Aiello, “An Overview of Hierarchical Task Network Planning” in ArXiv.

In other words, your typical attendee at the CP conference or reader of the Constraints journal might well not have run across this paper. I believe there are many such papers. In a way, this is a positive sign, of the degree to which our “baby” has moved out into the world. Still, the more we are aware of applications of constraint satisfaction the better. The more that people applying constraint satisfaction are aware of the broader body of work in our field the better. The more that people in general are aware of the breadth of applications of constraint satisfaction the better. An application like this one to service robots could help interest students in the field or convince funding agencies of our “impact”. It could suggest new collaboration opportunities or suggest new directions for basic research.