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 ...
- 904
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 ...
- 2,098
22
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 ...
- 37.5k
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 ...
- 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 ...
- 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):
...
- 3,352
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 ...
- 2,910
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
...
- 2,907
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 ...
- 2,080
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.
- 29.8k
11
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}^...
- 12.8k
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 ...
- 37.5k
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.
...
- 11.9k
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 ...
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 ...
- 37.5k
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 "...
- 37.5k
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....
- 3,980
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 ...
- 1,740
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 ...
- 1,404
8
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/...
- 1,404
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 ...
- 1,797
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....
- 11.9k
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 ...
- 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 ...
- 37.5k
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 ...
- 37.5k
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 ...
- 5,889
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 ...
- 37.5k
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.
- 4,685
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.
- 2,568
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:
...
- 1,404
Only top scored, non community-wiki answers of a minimum length are eligible