36 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 ...
user avatar
  • 834
27 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 ...
user avatar
  • 2,042
21 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 ...
user avatar
  • 28.8k
17 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 ...
user avatar
  • 1,502
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 ...
user avatar
  • 541
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): ...
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 ...
user avatar
  • 2,609
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 ...
user avatar
  • 2,809
11 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 ...
user avatar
  • 2,030
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.
user avatar
  • 21.7k
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 ...
user avatar
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 ...
user avatar
  • 28.8k
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 "...
user avatar
  • 28.8k
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....
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 ...
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 ...
user avatar
  • 1,384
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 ...
user avatar
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....
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 ...
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 ...
user avatar
  • 28.8k
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 ...
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 ...
user avatar
  • 28.8k
7 votes

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

I really liked the "Discrete Optimization" course at coursera - not sure if they still run it.
user avatar
7 votes

TSP problem: traveller does not visit all nodes - Google OR-tools

(already answered on S.O. ) You should have a look at Jobshop scheduling example with transitions In particular, it maintains a graph of direct successor between tasks on the same machine.
user avatar
7 votes
Accepted

Constraint Programming OR-Tools finding Matrix Combinations

You get the same result $2^{\operatorname{len}(y)}$ times because $y_i$ is not constrained. You can see that by adding this to your callback: ...
user avatar
  • 1,384
7 votes
Accepted

Interval variables in MIP

There is no single entity in MIP modeling that is a direct analog of an interval variable. The general MIP approach is as follows: discretize the time domain (which is inherent in CP models using ...
user avatar
  • 28.8k
7 votes

Floating points in ORtools

In many of its solvers, OR-Tools only accept integers (see Laurent Perron's comment below). Something like that: ...
user avatar
  • 511
7 votes
Accepted

Cumulative Constraint OR-Tools

If you look at OR-Tools: CumulativeConstraint, AddCumulative takes a variable as argument, so if it is constant, create a variable with a fixed domain. It returns ...
user avatar
7 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/...
user avatar
  • 1,384
7 votes

Are there some benchmark problems for CSP Solvers?

Here's one: CSPLib: A problem library for constraints
user avatar
  • 21.7k

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