Skip to main content
40 votes

How to select a Constraint Programming Solver

@Rob wrote a great and extensive answer, but I would like to add two systems. MiniZinc is a high level CP system that is great for learning CP, prototyping problems as well as testing different ...
hakank's user avatar
  • 934
30 votes

How to select a Constraint Programming Solver

... Do you have a set constraint programming solver that you always use, no matter which global constraint you actually need (implementing the needed global constraint yourself if needed)? Find one ...
Rob's user avatar
  • 2,110
23 votes

Combinatorial Optimization: Metaheuristics, CP, IP -- "versus" or "and"?

Here, in approximate order, are my criteria. Do I need a provably optimal solution (which rules out metaheuristics, other than to generate an initial feasible solution)? Is this something CPLEX can ...
prubin's user avatar
  • 39.3k
19 votes
Accepted

What is the difference between integer programming and constraint programming?

You have asked a broad question, so I will provide a broad answer. Integer programming typically refers to integer linear programming which is a mathematical modeling and solution paradigm. Decisions ...
alerera's user avatar
  • 1,542
14 votes

How to use the least number of colours to colour different routes of a bus route such that no two intersecting routes will have the same colour

Recognize that each route can be viewed as being a node on a graph. Edges connect nodes if the routes the nodes represent intersect. This is the canonical graph coloring problem for which there are a ...
Richard's user avatar
  • 543
13 votes
Accepted

How to implement a custom global constraint in IBM's ILOG CP optimizer

The Graph Coloring example shipped with CP optimizer (file: color.cpp in the examples directory): ...
Joris Kinable's user avatar
13 votes

Adding a constraint in constraint programming

This is not true in practice. Moreover, this is something almost impossible to guess without experimenting. Indeed, adding constraints (proven to be mathematical valid, or just guessed by your flair ...
Hexaly's user avatar
  • 2,986
12 votes

Good resources for solving techniques (Metaheuristics, MILP, CP etc)

You should take a look at a series of three courses at coursera : Basic Modeling for Discrete Optimization Solving Algorithms for Discrete Optimization Advanced Modeling for Discrete Optimization ...
Antarctica's user avatar
  • 2,917
12 votes

To which area does constraint programming belong?

In general, I think Constraint Programming or Constraint Satisfaction Problems have their roots in Computer Science/Artificial Intelligence communities that may or may not overlap to some extent with ...
Paul Bouman's user avatar
  • 2,100
12 votes
Accepted

Is there a better way of defining a constraint on positive integer variables such that no two variables are the same and are uniquely assigned a value

Introduce binary variables $y_{ij}\in \{0,1\}$ that take value $1$ if and only if $x_i$ is assigned to value $j\in \{1,...,N\}$, and use the following constraints: \begin{align} x_i &= \sum_{j=1}^...
Kuifje's user avatar
  • 13.5k
11 votes
Accepted

Solving Quadratically Constrained Quadratic Program with Cross Product Terms Only

Rather than solving this directly as MIQCQP, you might consider linearizing the products $y_{ij} x_{ij}$, as shown here, yielding instead an MILP problem.
RobPratt's user avatar
  • 32.3k
10 votes

Constraint programming resources

Here's a complement to @jnmonette's and @A.Omidi's answers. The best book that covers CP in detail is "Handbook of Constraint Programming" (https://www.amazon.com/Constraint-Programming-...
hakank's user avatar
  • 934
10 votes

What is the difference bewteen CP and MILP approaches in Job Shop Scheduling?

CP is not a subset of MILP. They are separate modeling/solving paradigms whose domains of application overlap. Both can solve for optimal solutions (in CP's case, by incorporating a constraint that ...
prubin's user avatar
  • 39.3k
10 votes
Accepted

Is there an open-source equivalent to LocalSolver?

The simple answer is no. While I haven't used LocalSolver myself, I sell a solver that solves similar types of problems (Octeract Engine) so I get asked this type of question a lot for my own solver. ...
Nikos Kazazakis's user avatar
9 votes

Constraint programming using solver: how to state the time limit of search?

What Nikaza said, and also: problems of this kind often have a large number of solutions that differ only by trivial permutations/relabellings/reorderings. For example, if one worker is assigned 10 ...
G_B's user avatar
  • 1,847
9 votes
Accepted

How to measure model quality in OR-Tools?

Time to solve (to proven optimality) is certainly a good choice. I don't know that I would be excited about number of conflicts. You could look at the ratio of objective value on that problem ...
prubin's user avatar
  • 39.3k
9 votes
Accepted

CP-SAT ortools - Is there any complete list of possible/available StringParameters for the CpSolver?

As many things in Google, OR-Tools uses Protocol Buffers to serialize data. Here's a list of all .proto files in OR-Tools: https://github.com/google/or-tools/...
Stradivari's user avatar
  • 1,414
9 votes
Accepted

Mixed integer programming vs Constraint programming

I'm not sure that talking about a comparison of MIP models and CP models makes sense, in part because I think that CP models tend to be solver-specific. MIP models tend to have a standard set of "...
prubin's user avatar
  • 39.3k
8 votes
Accepted

What is the standard practice in Constraint Programming modeling?

at https://www.slideshare.net/PhilippeLaborie/an-introduction-to-cp-optimizer you may find some information about RCPSP with Linear programming and constraint programming. Plus https://tidel.mie....
Alex Fleischer's user avatar
8 votes

To which area does constraint programming belong?

Regarding your question “The question is now to what kind of field of operations research CP belongs”, I will say that CP is not a subfield of operations research, but it is another field, closely ...
Stefano Gualandi's user avatar
8 votes
Accepted

Precedence Constraint in OR-Tools

What you want is: AddLessOrEqual(LinearExpr(starts[j]).AddConstant(durations[j]), starts[succ[j][s]]) You might also want to take a look at the examples (ending ...
Stradivari's user avatar
  • 1,414
8 votes

How can I optimize this integer programming constraint problem without running out of memory?

Be sure that your code reaches the getSolutions line. As of now, you are not sure that it does. Your Python code is creating more than 3000000 functions! There is a good chance that is what is causing ...
Ggouvine's user avatar
  • 1,877
8 votes

Constraint programming resources

For modeling, I would recommend one of the following coursera courses, taught using the MiniZinc modeling language: https://www.coursera.org/learn/basic-modeling and https://www.coursera.org/learn/...
jnmonette's user avatar
  • 181
8 votes

What are the solvers that give a feasible solution within a given time?

Pretty much all of them. Any solver worth using will support timeouts and what you describe is basically running a solver with a timeout. Solvers that are supposed to compute more than one solution (e....
Nikos Kazazakis's user avatar
8 votes

Modeling in integer programming vs modeling in constraint programming

There are many resources available to learn constraint modelling. When learning about constraint modelling I can recommend the following books: Principles of Constraint Programming by Krzysztof Apt ...
Dekker1's user avatar
  • 225
8 votes

Modeling in integer programming vs modeling in constraint programming

When I started learning CP (coming from IP), one of the first things I discovered is that model elements are less standardized in CP than in IP. An IP model typically contains a polynomial objective ...
prubin's user avatar
  • 39.3k
8 votes

Is there an open-source equivalent to LocalSolver?

To our knowledge, there is no equivalent of Hexaly (formerly LocalSolver) in open source and no equivalent of Hexaly in the market. Hexaly's uniqueness, and thus innovation, comes from the two key ...
Hexaly's user avatar
  • 2,986
8 votes
Accepted

Doubles Round Robin Sorting Algorithm

You can solve this with an integer programming model. I will omit the objective function, since any feasible solution produces a viable schedule. You might give some thought to whether there is a ...
prubin's user avatar
  • 39.3k
7 votes

What is the difference between integer programming and constraint programming?

There were times when the IP and CP communities started to learn about the existence of the other, and initially, people tried to build a list of vocabulary to translate one concept into another. You ...
Marco Lübbecke's user avatar
7 votes
Accepted

Workforce Scheduling problem - Modelling to minimize resources

I assume that each defect requires a specified amount of labor (expressed in worker-hours) to solve, and that each worker contributes one hour of labor for each hour of their shift (no breaks). You ...
prubin's user avatar
  • 39.3k

Only top scored, non community-wiki answers of a minimum length are eligible