Questions tagged [constraint-programming]

For questions on modeling satisfaction or optimization problems in languages designed for expressing (often high-level) constraints on decision variables.

Filter by
Sorted by
Tagged with
3 votes
0 answers
84 views

Circuit constraints in ortools

I am looking to assign tasks to people. Each successive task should be started after the first one is finished and should be started at the same location as the preceding task. While the time ...
user avatar
3 votes
1 answer
107 views

Mathematically formulating formal problem of a cloud service scheduler

So, I have been tasked to create a formal mathematical description of problem statement on a cloud service scheduler for my team's university project, which is, honestly, a little weird of a thing to ...
user avatar
  • 69
2 votes
1 answer
97 views

opposite of no_overlap constraint in docplex for CP

I am using python for CP solving. I would like to know if there is constraint that does the opposite of no_overlap. This will be like overlap(interval, arr, n) interval - single interval variable arr -...
user avatar
5 votes
1 answer
84 views

Help modeling grid placement problem

I'm trying to model a grid placement problem to exercise in OR. The problem is defined as: a grid of some dimension (let's say 500x500) N users that need connection. Every user has: a defined ...
user avatar
  • 159
7 votes
4 answers
807 views

is prime? in Operations Research

Is there a way to linearize is prime? in Operations Research? is prime(n) being true if $n$ is a prime number or false otherwise....
user avatar
  • 533
2 votes
0 answers
115 views

SLSQP vs Trust Region Constrained Algorithms

I have gone through scipy constrained algos explanation, however, not much is mentioned about the differences, pros and cons of the 'trust-const' and 'slsqp' methods. I particularly wanted to know ...
user avatar
  • 129
4 votes
2 answers
446 views

What is the newest MIP and CP solver?

What is the newest MIP or CP solver (which is model based exact solver)? I want to follow and wonder developments on solvers. But finding new developed solvers (experimental, academic, commercial etc.)...
user avatar
  • 746
7 votes
2 answers
168 views

Why most of constraint solvers do not support optional intervals?

Optional interval is a great idea of optional interval/task that can be active or inactive based on boolean variable. I found it very useful in complex scheduling problems. It was introduced in IBM Cp ...
user avatar
  • 171
1 vote
1 answer
197 views

Custom lazy callback constraints using Google OR-Tools linear solver?

Is it possible to implement custom lazy callback constraints using OR-Tool's base linear solver? Through Google's docs, I've seen their TSP examples using the constraint solver ...
user avatar
3 votes
1 answer
69 views

Optimize parametric Log-Likelihood with a Tree

Suppose there are some objects with features, and the target is parametric density estimation. Density estimation is model-based. Parameters are obtained by maximizing log-likelihood. $$\operatorname{...
user avatar
  • 31
1 vote
0 answers
54 views

Minimizing total number of banners used in the cover buildings problem modelled

I was watching a video about Google OR-Tools where they were solving this cover building problem from Codility challenges using constraint programming. In short, you have a list of building heights, e....
user avatar
  • 111
2 votes
1 answer
85 views

Adding a variable makes the model unsatisfiable in MiniZinc

I have the following model. ...
user avatar
  • 225
0 votes
0 answers
141 views

OR-Tools addElement constraint

I am just not able to grasp how can I use the addElement constraint of OR-Tools. I am trying to model the following constraint written in MiniZinc: ...
user avatar
  • 119
2 votes
1 answer
56 views

How to model a cumulative resource constraint with same family condition?

Assume that we have 3 tasks to schedule : $x_{a1}, x_{a2}, x_{b3}$. They all use the same cumulative resource : $r_1$. Each activity increases $r_1$ by $1$ at it starts time and decreases $r_1$ by $1$ ...
user avatar
2 votes
1 answer
100 views

Scheduling when task duration longer than working interval

I'm trying to modify the job shop example for CP-SAT solver. (https://developers.google.com/optimization/scheduling/job_shop) I'm limited to 8 hours working day, So I defined a list of NewIntervalVar()...
user avatar
2 votes
1 answer
258 views

Set value based on if other variable is in specific range

I have the following problem. number_of_machines is controlled by other constraints. I need to set line variable to specific value based on "range" ...
user avatar
2 votes
1 answer
44 views

ILOG CPOptimizer soft constraints (multiple solves reusing searched space)

I'm trying to feed information retrieved from my neural network to my CP model to help narrow down the search on big instances of my problem. However, I also want to remove the additional imposed ...
user avatar
  • 121
3 votes
0 answers
71 views

Convex Optimization Problem with norm inequality constraint

Consider the following optimization problem: \begin{align} \inf_{x,y}&\quad(x-x_0)^\top A(x-x_0) + (y-y_0)^\top B(y-y_0) \\\text{s.t.}&\quad x^\top a\geq0,\\ & \quad y^\top b\geq0, \\& ...
user avatar
8 votes
2 answers
377 views

VRP through constraint programming

I am with a problem that consists of determining whether a VRP instance is feasible, this question is a continuation of an older thread. In order to do it, I was thinking of using Constraint ...
user avatar
1 vote
1 answer
97 views

Dual of quadratic program with linear objective

Let $c$ and $k$ be element-wise positive $n\times 1$ vectors and let $A$ be a element-wise positive and positive-definite matrix. Consider the optimization problem \begin{align} \max_{p\in\mathbb{R}^n}...
user avatar
1 vote
1 answer
63 views

Print Intermediate Solutions of Scheduling Problem and tackling FLAGS in jupyter notebook

I tried this code and it goes on and I'm clueless when it'll end so I manually interrupt it. Is there any way we can see intermediate solutions that are feasible solutions and can we limit time or ...
user avatar
2 votes
0 answers
112 views

Multiple Depot/Crew Office Bus Driver Scheduling Modelling

I'm working on Bus Driver Schedule with multiple add-on constraints that are complex and hence trying to figure out how this can be achieved. Reference of Bus Driver Scheduling using OR-Tools:- https:/...
user avatar
4 votes
1 answer
129 views

How do I formulate constraints that check if a parameter is between certain values, using binary variables?

I have $3$ parameters $a_1,a_2,a_3$ and a variable $d$ and $3$ binary variables $b_1,b_2,b_3$ and a "result" variable $s$. How do I model constraints so that: If $d$ is between $0$ and $a_1$...
user avatar
  • 43
2 votes
0 answers
78 views

Consistency Level of Constraints

Recently I started using CP and translated my first MIP model into a CP model with the IBM CP Optimizer. Lately I was confronted with a question I could not answer: "What is the consistency level ...
user avatar
  • 83
3 votes
1 answer
151 views

Extracting CNF representation of my problem from SAT solver

As I know, any SAT solver such as or-tools or cplex cp optimizer converts a given problem to CNF form in the first place. Is it possible to extract the resulting CNF representation from or-tools or ...
user avatar
5 votes
1 answer
295 views

Solving Quadratically Constrained Quadratic Program with Cross Product Terms Only

I'm totally new to the world of optimization and I have an optimization problem that I think it can be formulated as Mixed Integer Quadratically Constrained Quadratic Program (QCQP) but I'm not sure ...
user avatar
5 votes
1 answer
224 views

Solver Recommendation : Discrete Variables and Quadratic Constraints

I would like some solver recommendations to solve a problem with boolean/integer variables, mostly linear constraints but also some quadratic constraints. I also have an objective to minimize which is ...
user avatar
-4 votes
1 answer
143 views

Multiple If else constraints in Mixed integer programming

How to formulate the following as constraints in MILP? a[0][0] = y, if x[0]= 0, a[0][0] = 0, if x[0] != 0, . . . . a[i][j] = b[i][j-1] + y, if x[j]=i, a[i][j] = a[i][j-1], if x[j] != i, ... . . . b[0]...
user avatar
  • 125
2 votes
1 answer
156 views

OR-Tools, How to avoid dividing by zero

Problem: There is an order to fabricate some products of total number, let's say 200 (all products are the same). We have some number of factories, let's say 5. Every factory has different number of ...
user avatar
5 votes
4 answers
582 views

How to visit a subset of network nodes in a single trip?

I have a connected network where I want to visit a set of destinations which may require visiting intermediate nodes as well because there may be no direct edge between source and destination nodes. I ...
user avatar
  • 61
4 votes
1 answer
385 views

Is there any automatic way to spot contradictory constraints in linear programming?

Let's have the following trivial linear program: \begin{align}\max&\quad z=20A+30B\\\text{s.t.}&\quad A\le60\\&\quad B\le50\\&\quad A+2B\ge220\\&\quad A,B\ge0\end{align} It's easy ...
user avatar
4 votes
2 answers
536 views

Scheduling optimisation constraint on consecutive shifts & consecutive night shifts (`python`)

I am trying to write a program to schedule a team of 8 individuals into shifts. I want to know how to model that every individual must get at least one night shift break, and must not work two ...
user avatar
2 votes
2 answers
109 views

Scheduling: Tasks changing the state of the executing machine

I have a scheduling problem in which machines consume their battery when executing tasks and charge their battery when not executing tasks. A single task has to be executed in one go (no recharging ...
user avatar
  • 123
0 votes
1 answer
56 views

What is a good approach to deciding which jobs (from a list of HPC jobs) should be ran locally vs. on the cloud given time & cost constraints?

Cloud computing has transformed the landscape of compute operations. Of course, there are still many labs/businesses with local, large-scale compute clusters. For those businesses who keep the ...
user avatar
  • 9
3 votes
2 answers
226 views

Modeling in integer programming vs modeling in constraint programming

I have some experience with linear and integer programming modeling (I read Model Building In Mathematical Programming by Williams). Now I am trying to learn how to model with constraint programming. ...
user avatar
2 votes
1 answer
556 views

Python, Google OR-Tools, OnlyEnforceIf() method

I am trying to solve a basic puzzle by using Google OR-Tools, this is my first try with OR-Tools and I am trying to learn. I completed almost everything and was ready to conclude the program until I ...
user avatar
0 votes
2 answers
243 views

How can I formulate this specific if-then constraint?

IF $\sum\limits_d X_{i,d}\ge6$ THEN $Y_i = 1$ (strictly) AND IF $\sum\limits_d X_{i,d}<6$ THEN $Y_i = 0$ (strictly) $X$ and $Y$ are binary variables. What I'm actually trying to do is to charge the ...
user avatar
  • 21
1 vote
1 answer
121 views

Constraint programming and scheduling issues

I have a constraint problem that I need to resolve, but I did not how know to model the problem: I have 11 employees, I will name them from $a$ to $k$: $\{a,b,c,d,e,f,g,h,i,j,k\}$. I have a small ...
user avatar
2 votes
1 answer
853 views

How to know which constraint in CP-SAT did not meet the feasibility gap

Is there any systematic way to retrieve some information on the constraint that caused infeasibility in Or.Tools CP-SAT? ...
user avatar
  • 117
2 votes
1 answer
104 views

How to model a set of integer variables getting assigned different values than another set of integer variables

Assume we have variables $x_1, x_2, x_3, x_4$ that each can belong to $\{1,2,...,10\}$. How can we model a constraint that variables $x_1, x_2$ get assigned different values than $x_3, x_4$? Because ...
user avatar
  • 117
2 votes
3 answers
347 views

How to model two variables to NOT to belong to the same set partition using Constraint Programming

Assume we have two variables $x,y \in S$ where $S=\{1,2, \dots, 1000\}$. Also, we are given a partition of set $S$ as: $S_1 = \{1,2, \dots, 249\}$ $,S_2 = \{250, \dots, 499\}$ $,S_3 = \{500, \dots, ...
user avatar
  • 117
-2 votes
1 answer
111 views

Any references to the ROADEF 2020 Challenge?

The problem description of the challenge is given here. Does anyone has some references to similar problem. I would like to participate but I don't know where to start.
user avatar
  • 567
9 votes
1 answer
505 views

Adding a constraint in constraint programming

Is it true that the more we add constraint to a constraint programming solver the more efficient it will be? How does this compare to adding constraints in integer programming solvers.
user avatar
  • 567
3 votes
2 answers
710 views

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

What are the solvers that take the maximal computation time as a parameter and gives the best found feasible solution within this time.
user avatar
  • 567
2 votes
1 answer
91 views

Looking for a similar optimization problem

I want to know if there is any already defined problem that could give me a hint on how should I approach the following task. There are N tasks that should be accomplished, each task requires ...
user avatar
1 vote
3 answers
335 views

How can I linearize this IF-THEN constraint?

Let $P_{t,u}; t=1,2,\ldots,T, u=1,2,\ldots,U$ be known values $\alpha$ is also a known parameter $X_{t,u}$ an optimization variable I have the following constraint: IF $P_{t,u}\geq\alpha$, THEN $X_{...
user avatar
3 votes
1 answer
88 views

Integer decision variables as index

The following problem has only two integer variables; however, they appear in the index of the parameters. Appreciate it if anyone has any efficient idea to transform it into a canonical integer ...
user avatar
8 votes
3 answers
445 views

Constraint programming resources

I am looking for resources to learn constraint programming. I will divide the resources I am looking for in three types: Modeling Is there resources (books, articles, courses, etc.) that are ...
user avatar
3 votes
1 answer
245 views

Mixed integer programming vs Constraint programming

I see that certain studies are comparing MIP and constraint programming (CP) performances. And generally, they claim that CP outperforms MIP. But I believe that it is not completely true. Because ...
user avatar
  • 746
2 votes
0 answers
71 views

Finding Optimal Route using different Paths

I have a list of paths e.g. path 1 takes you from point A to B. A person needs to complete 5 of such paths. $$Route1 = path1 + ...
user avatar
  • 205