# Tag Info

32

@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 solvers. MiniZinc first flatten a MiniZinc (.mzn) model to FlagZinc format (.fzn) and there are quite a few CP solvers that supports the FlatZinc format, e.g. Gecode,...

25

... 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 that is well supported, that you understand to some extent, and that is powerful enough (speed and expressiveness) to suit your future needs. Invest your time in ...

21

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 handle (since I have a license for CPLEX and I'm familiar with it)? If CPLEX can handle it, should I consider a heuristic, metaheuristic or constraint solver to ...

16

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 are modeled as a vector of real numbers, some of which are further constrained to take only integer values. The decision vector is constrained to satisfy a ...

14

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 number of exact and approximate algorithms. Specifically, you're trying to find a constructive algorithm for determining the chromatic number. For 10 routes ...

13

The Graph Coloring example shipped with CP optimizer (file: color.cpp in the examples directory): #include <ilcp/cp.h> const char* Names[] = {"blue", "white", "yellow", "green"}; int main(int , const char * []){ IloEnv env; try { IloModel model(env); IloIntVar Belgium(env, 0, 3, "B"), Denmark(env, 0, 3, "DK"), ...

12

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 They use MiniZinc as modeling language.

11

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 the Operations Research communities. According to "Artificial Intelligence, A Modern Approach" by Stuart Russel and Peter Norvig, an early example within ...

11

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 and feeling of the business) to a mathematical optimization model that is solved by constraint programming techniques or integer programming techniques should be ...

11

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.

9

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 tasks that can be done in any order with no change to the objective, then there are 10! = 3628800 solutions that will have exactly the same OF. If another worker ...

9

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 instance to the best known value for that problem instance (across all model variants), given a time limit. A similar ratio of best bounds to best overall bound (by ...

9

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 "features": linear (or maybe convex quadratic) constraints; linear (or maybe quadratic) objective functions; and of course variables (integer or continuous)...

8

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.utoronto.ca/pubs/JSP_CandOR_2016.pdf concludes Comparing the best MIP results with that of CP, results show that MIP performs similarly to CP for smaller ...

8

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 with _sat.cc) to be more familiar with the c++ methods. https://github.com/google/or-tools/tree/master/examples/cpp

8

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 your memory issues. Don't use exec, and create a single timezone function instead with S and TA as additional parameters. You can use a lambda to pass it to ...

8

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.g. MILP, convex & global MINLP, global NLP, stochastic MILP & MINLP) will return the best one by timeout - the rest will typically return garbage if a ...

8

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 is probably the most used constraint programming book that will teach you all the aspects of constraint programming. The book that would most fit your ...

8

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 function and equality/inequality constraints involving polynomial functions (where you are hoping the polynomials are linear or at worst quadratic). Beyond that (...

7

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 related to OR, but it is another field. If you really like to understand the fundamental of Constraint (Logic) Programming, you should read the paper In Pursuit ...

7

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 might look at modeling demand and labor in a cumulative manner. For each hour of the time horizon, total the worker-hours required to fix all defects that must be ...

7

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

7

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: print("y:", [self.Value(y) for y in self._y.values()]) x: 1 for x(1,0) and matrix value:5 x: 1 for x(0,1) and matrix value:1 x: 1 for x(1,2) and matrix value:1 y: [0, 0, 0] x: 1 for x(1,0) and matrix value:5 x: 1 ...

7

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 interval variables); in lieu of a single interval variable, create a binary variable for each possible starting time and add a constraint setting the sum of those ...

7

In many of its solvers, OR-Tools only accept integers (see Laurent Perron's comment below). Something like that: model.Maximize( int(round( sum(np.exp(-delta*s[j])*pro[j] for j in range(n)) )) ) will probably work (I haven't tried), but you might lose some precision. The usual solution is to multiply each value by a power of 10 and divide the result ...

7

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 a CumulativeConstraint with a method to add (IntervalVar, DemandVar) pairs to the constraint. See OR-Tools 7.4: C++ Reference (CumulativeConstraint). Note that the rcpcp solver is implemented in ...

7

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/search?l=Protocol+Buffer The parameters for the CP-SAT solver are listed in the sat_parameters.proto file: https://github.com/google/or-tools/blob/stable/ortools/sat/sat_parameters.proto

7

Here's one: CSPLib: A problem library for constraints

7

The Minizinc constraint programming benchmark models are in Minzinc file format : https://github.com/MiniZinc/minizinc-benchmarks. Each year several CP solvers compete on some problems (see here : Minizinc challenge)

7

For each $i$, let binary decision variable $x_i$ be your desired output[i]. If I understand correctly, you want $x_0=1$, and for each $i<j$, you want $$(x_i,x_{i+1},\dots,x_{j-1},x_j)=(1,0,\dots,0,1)\iff \left(\bigwedge_{k=i+1}^{j-1} (|a_i-a_k|\le 0.0005) \land |a_i-a_j|> 0.0005\right).$$ Because $a_i$ is given, there is no decision to be made. You ...

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