# Tag Info

## Hot answers tagged constraint-programming

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 ...

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

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 (...

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

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 ...

6

If "total duration" means sum of durations, this is called the generalized assignment problem. If "total duration" means maximum of durations, this is called the bottleneck generalized assignment problem. You might also find something useful by searching for makespan minimization.

6

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/advanced-modeling For knowing how a solver works, I can recommend the slides of the course "Combinatorial Optimisation and Constraint Programming" at ...

6

To be clear, you have a set $S$ of nodes of a graph $G=(V,A)$, with $S\subseteq V$, which must be visited. There is a special node $O$, which must be the starting point of a tour. A tour visiting the nodes in $S$ starting from $O$ (but not returning to $O$) at minimum length must be found? If that is the case, I think the easiest way is to compute an all-...

5

Let $E$ be the set of employees, and let $P$ be the set of periods. For $e\in E$ and $p\in P$, let binary decision variable $x_{e,p}$ indicate whether employee $e$ goes to the company in period $p$. Let $G$ be the set of groups that must go together at least once, and for $g\in G$, let $E_g \subseteq E$ be the set of employees in group $g$. For $g\in G$, ...

5

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-Foundations-Artificial-Intelligence/dp/0444527265). However, it's from 2006 so it don't discuss the more recent development in CP, such as lazy clause generation ...

5

Constraint programming in its essence can be used to solve mixed-integer programming problems but, not for all cases is efficient. It is frequently used in the scheduling problems to solve the large scale models in which, using BIP/MIP is a bit complicated and need some special methods like decompositions. For more details, would you see this or this useful ...

5

Because $P_{t,u}$ and $\alpha$ are known constants (not decision variables), no linearization is needed. In a modeling language, it would look like this: con Mycon1 {t in 1..T, u in 1..U: P[t,u] >= alpha}: X[t,u] = 1; con Mycon2 {t in 1..T, u in 1..U, tp in 1..T diff {t}: P[t,u] >= alpha}: X[tp,u] = 0; Some languages support this equivalent ...

5

Shameless plug: I recently gave a webinar on diagnosing infeasibility. Here's what your example looks like in SAS: proc optmodel; var A >= 0; var B >= 0; max z = 20*A + 30*B; con c1: A <= 60; con c2: B <= 50; con c3: A+2*B >= 220; solve with lp / iis=true; expand / iis; quit; The resulting IIS contains all three ...

5

If the set $S$ of nodes to be visited is not too large, you can solve $|S|$ shortest path problems with additional constraints imposing a visit to some nodes. With your example, $|S|=|\{A,C \}|=2$ so it is not too bad. 1/ Find the shortest path from $O$ to $A$, while imposing a visit to node $C$. 2/ Then find the shortest path from $O$ to $C$, while ...

5

I assume fab_rate is variable, otherwise you can just test it. You can use temporary variables: non_zero_fab_rate = model.NewIntVar(1, ..) fab_rate_is_zero = model.NewBoolVar(..) model.Add(non_zero_fab_rate == 1).OnlyEnforceIf(fab_rate_is_zero) model.Add(non_zero_fab_rate == fab_rate).OnlyEnforceIf(fab_rate_is_zero.Not()) model.Add(fab_rate == 0)....

5

You just seem to have hidden a long list of constraints of the form $(x_i=j) \Rightarrow \text{equalities}_{ij}$ Introduce a binary matrix $C_{ij}$ with $\sum_j C_{ij}= 1$ and $C_{ij} \Rightarrow \{x_{i} = j, \text{equalities}_{ij}\}$ To model the binary implication you can use big-M modelling, e.g. $-M(1- C_{ij})\leq x_{i} - j\leq M (1-C_{ij})$ and similar ...

4

Here's one way: $$x\not=i \lor y\not=j \text{ for } k\in\{1,2,3,4\}, i\in S_k, j\in S_k$$ Here's another way, using ELEMENT constraints, as suggested by @prubin. The following is SAS code, but maybe OR-Tools has something similar. proc optmodel; set S {k in 1..4} = if k = 1 then 1..249 else if k = 2 then 250..499 else if k = 3 ...

4

For simplicity, I will drop the $i$ subscripts everywhere and instead write $x_d$ for $x_{i,d}$ and $y$ for $y_i$. The linear constraint $$\sum_{d=1}^6 x_d \le 5 + y$$ enforces $$\sum_{d=1}^6 x_d > 5 \implies y=1.$$ You can derive this constraint via conjunctive normal form as follows: $$\left(\land_{d=1}^6 x_d\right) \implies y \\ \lnot\left(\land_{d=1}^... 4 Not yet, see https://github.com/google/or-tools/issues/973 For debugging I would recommend you to divide your constraints into groups so you can activate/deactivate some of them to pin down the infeasibility 4 There are certainly different ways of achieving what you want. Here is how I would proceed: Start by predefining the set of all possible schedules which satisfy your constraints 2,3,4,6. Although there are many, I believe that with your constraints, it may be not too difficult to derive them somewhat automatically. Here is a subset of them in the table ... 3 In OptaPlanner, I'd start from the task assigning example and use a shadow variable to track the remaining battery level of every task. Then a simple constraint can check if it's ok to schedule that task on that machine: from(Task.class) .filter(task -> task.getRemainingBatteryLevel() < task.getRequiredBatteryLevel()) .penalize("Battery", ... 3 If you mean (x_1,x_2)\not=(x_3,x_4), you can enforce this with:$$10(x_1-1) + (x_2-1) \not= 10(x_3-1)+(x_4-1)$$Equivalently:$$10x_1 + x_2 \not= 10x_3+x_4 \tag1$$If instead you meant the four disequalities you listed, you can impose$$(x_1 - x_3)(x_1 - x_4)(x_2 - x_3)(x_2 - x_4)\not=0$$Alternatively, you might consider generating your four ... 3 You can omit constraint 2 because it is dominated by constraint 1. Constraint 6 is not correct. For consecutive days, you want$$\sum_l z_{i,j,k,l}+\sum_l z_{i,j-1,k_2,l}-1\le s_{i,j,k},$$where k\not= k_2. For a day off in between, you want$$\sum_l z_{i,j,k,l}+(1-y_{i,j-1})+\sum_l z_{i,j-2,k_2,l}-2\le s_{i,j,k},$$where k\not= k_2. For two days off in ... 3 Suppose x,y\in\{0,\dots,n\}. I think I would just loop over these (n+1)^2 pairs and keep the best one that satisfies the constraint. But if you insist on integer programming, introduce binary variables x_i and y_i for i\in\{0,\dots,n\}, with the interpretation that d_x=\sum_i d_i x_i and d_y=\sum_i d_i y_i. The problem is to maximize$$\left(\...

3

In OptaPlanner (open source, java), we not just support the traditional approaches such as the solving wall clock time in application.properties: # Terminate solving after 30 seconds. # To run for 5 minutes use "5m" and for 2 hours use "2h". optaplanner.solver.termination.spent-limit=30s or the unimproved wall clock time: # Terminate if ...

3

I think your third constraint should be + 1, not - 1, on the right hand side. As stated, it says you enter destination nodes one time fewer than you exit them. You want to enter one time more. Fixing that will make the optimal solution feasible, but it will not make the model correct. There still remains the possibility of a solution that is not a contiguous ...

3

you could try constraint programming / scheduling within CPLEX and use noOverlap to model the time matrix. In OPL that gives using CP; execute { cp.param.timelimit=10; } {string} nodes={"O","A","B","C","D","E","T"}; tuple edge { key string o; key string d; int time; } {edge} ...

2

This is a maintenance planning problem, here related to the French high-voltage transmission system. By searching for "maintenance planning problem" on the web, you will find a lot of OR literature on the topic. Now, to start, may we advise you to: entirely read the subject of the challenge; read the input data using your favorite programming ...

2

If I got the question correct you don't even need a constraint. You can simply define the lower and upper bounds on your variables $X_{t,u}$ based on the parameters. For instance: x[t,u] = model.addVar(lb = 1 if P[t,u] >= alpha else 0, ub = 1 if P[t,u] >= alpha else 0, vtype="B") If there isn't a $t$ for all $u$ that fulfills \$P_{t,u} \geq \...

2

The problem here is that you are generating way more variables & functions than Pyomo can normally handle. However, I am guessing that you don't strictly need all of them, i.e., it's possible that there is inherent sparsity and/or symmetry in the problem that you are not exploiting. My suggestion would be do add if statements in your definitions to skip ...

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