My Constraint Programming Blog

This Monday/Tuesday I visited Örebro (Sweden) attending the SweConsNet Workshop 2012, Monday) (co-located with Swedish Artificial Intelligence Society Workshop 2012, program, Monday and Tuesday). SweConsNet is the Network for Sweden-based researchers and practitioners of Constraint programming and is a Special Interest Group of SAIS.

SweConsNet Workshop 2012

One of the greatest joy attending these workshops is to meet and talk to all the clever and nice CP guys in Sweden/Denmark/Norway. But of course, the talks are also very interesting and they yield much inspiration and/or thoughts. Here's the program (the page SweConsNet Workshop 2012 have links to most presentations):

• Mats Carlsson, SICS. On the Reification of Global Constraints.
  Joint Work with: Nicolas Beldiceanu (EMN, Nantes, France), Pierre Flener and Justin Pearson (Uppsala University).
• Federico Pecora: Constraint reasoning and motion planning in the SAUNA project (This is a joint talk with SAIS).
• Uwe Köckemann, Federico Pecora and Lars Karlsson. Towards Planning With Very Expressive Languages via Problem Decomposition Into Multiple CSPs (This is a joint talk with SAIS).
• Invited talk: Associate professor Rune Møller Jensen from the IT University of Copenhagen will talk about AI and CP methods for optimizing liner shipping operations. (This is a joint talk with SAIS).
• Krzysztof Kuchcinski, Lund University. Operation Scheduling, Binding and Data Routing for Run-Time Reconfigurable Architecture.
• Håkan Kjellerstrand. Comparison of >= 14 CP systems - and counting.
• Stefano Di Alesio, Simula School of Research and Innovation AS, Norway. Testing Deadline Misses for Real-Time Systems Using Constraint Optimization Techniques.
• SAIS Masters Thesis Award Winner Rodrigo Gumucio. (This is a joint talk with SAIS).
• Maria Andreina Francisco Rodriguez, Uppsala University. Consistency of Automaton-Induced Constraint Decompositions.
  Joint work with: Pierre Flener and Justin Pearson (Uppsala University).
• Roberto Castañeda Lozano, SICS & KTH - ICT. Code Generation is a Constraint Problem.
  Joint work with: Mats Carlsson (SICS), Frej Drejhammar (SICS), Christian Schulte (KTH - ICT & SICS).

The two talks that I liked most this year was:

• Mats Carlsson's talk about "On the Reification of Global Constraints" which will probably/hopefully have a deep impact on the CP field
• and Roberto Castañeda Lozano about "Code Generation is a Constraint Problem", both for the interesting problem and the excellent presentation.

Thanks to Christian Schulte who together with the Federico Pecora and Lars Carlsson arranged these great days.

My SweConsNet talk: "Comparison of >= 14 CP systems - and counting"

My own talk at the workshop was Comparison of >= 14 CP systems - and counting (PowerPoint). The purpose of it was twofold:

• Point out that my models - and especially the page Common constraint programming problems - could be used to compare different CP systems since quite a few implements the same problem using the same ("as same as possible") approach. As of now there are:
  • 276 problems that is implemented in >= 2 systems (in total 1260 implemented models)
  • 73 problems in >= 6 systems
  • 44 problems in >= 8 systems
  • 15 problems in >= 10 systems
• Mention some strengths/weaknesses - or rather: my likes/dislikes - about these 14 tested systems, especially for a person learning the CP system or learning CP in general. One of my running theme is that the syntax for the most common things in modeling (e.g. the Element constraint and reifications) should be as easy as possible. The links are to my model pages for each system:
  • MiniZinc(888 models)
  • JaCoP (18 models)
  • Choco (20 models)
  • Comet (166 models)
  • Gecode (162 models)
  • Gecode/R (29 models)
  • ECLiPSe (176 models)
  • Tailor/Essence' (29 models)
  • SICStus Prolog (151 models)
  • Zinc (39 models)
  • JaCoP/Scala (38 models)
  • Google or-tools/Python (203 models)
  • Google or-tools/Java (36 models)
  • Google or-tools/C# (122 models)

After the "Thanks" slide (which concluded the talk), there are some more slides for the Q/A session or as reserves.

Note: This is kind of an extension of my SweConsNet Workshop 2009 talk where I presented my take on the then tested 6 CP systems. See Report from SweConsNet2009, including my presentation.

Posted by hakank at 10:52 AM | Permalink

Some days ago I was told that the journal paper I have co-authored about Manufacturing Cell Design Problem (MCDP, see below) has been accepted for publication in a journal. Also, some weeks ago a short conference paper about the same topic was accepted. My part in both papers was that I created a couple of MiniZinc models (first the standard formulation and then some other using different approaches) and running a large number of benchmarks on a couple of FlatZinc solvers. This is really fun, since these papers are my first academic papers related to Constraint Programming.

Since the papers are not yet published/presented, I cannot reveal much more than the following. After the publications, I will blog more.

The journal paper

The journal paper is

Ricardo Soto, Hakan Kjellerstrand, Orlando Durán, Broderick Crawford, Eric Monfroy, Fernando Paredes: Cell formation in group technology using constraint programming and Boolean satisfiability

Published in the journal Expert Systems with Applications (ScienceDirect page, "In Press, Corrected Proof")

Abstract:

Cell formation consists in organizing a plant as a set of cells, each of them containing machines that process similar types or families of parts. The idea is to minimize the part flow among cells in order to reduce costs and increase productivity. The literature presents different approaches devoted to solve this problem, which are mainly based on mathematical programming and on evolutionary computing. Mathematical programming can guarantee a global optimal solution, however at a higher computational cost than an evolutionary algorithm, which can assure a good enough optimum in a fixed amount of time. In this paper, we model and solve this problem by using state-of-the-art constraint programming (CP) techniques and Boolean satisfiability (SAT) technology. We present different experimental results that demonstrate the efficiency of the proposed optimization models. Indeed, CP and SAT implementations are able to reach the global optima in all tested instances and in competitive runtime.

Keywords:

Manufacturing cells; Machine grouping; Constraint programming; Boolean satisfiability

Conference paper

The short conference paper is the following (with almost the same authors as the journal paper)

Ricardo Soto, Hakan Kjellerstrand, Juan Gutiérrez, Alexis López, Broderick Crawford, and Eric Monfroy: Solving Manufacturing Cell Design Problems using Constraint Programming

for the conference IEA/AIE 2012 (International Conference on Industrial, Engineering and Other Applications. of Applied Intelligent Systems, 2012 Dalian, China )

Abstract:

A manufacturing cell design problem (MCDP) consists in creating an optimal production plant layout. The production plant is composed of cells which in turn are composed of machines that process part families of products. The goal is to minimize part flow among cells in order to reduce production costs and increase productivity. In this paper, we focus on modeling and solving the MCDP by using state-of-the-art constraint programming (CP) techniques. We implement different optimization models and we solve it by using two solving engines. Our preliminary results demonstrate the efficiency of the proposed implementations, indeed the global optima is reached in all instances and in competitive runtime.

More about MCDP

Manufacturing Cell Design Problem is a kind of clustering problem where the object is to cluster machines that belongs to the same part (families) as good as possible. For a little more about the problem, see the following (Powerpoint) presentation by My Mingang Fu, Lin Ben, and Kuowei Chen Manufacturing Cell Design - Problem Formulation.

Posted by hakank at 08:13 AM | Permalink