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
1 vote
1 answer
98 views

Linearize conditional constraint

Consider a variable c from the domain {-1,0,1}. I have the following constraint: IF $c = 1 \Rightarrow x = 1 $ ELSE $x = 0$ How do I linearize this constraint?
  • 21
1 vote
1 answer
57 views

Multiplicity-Constraint in Constraint Programming Solvers

I need to solve a CSP with a constraint imposing upper bounds on the multiplicity of variables in a list. More precisely, I need a constraint of the form ...
  • 113
3 votes
1 answer
367 views

Of what size should I expect to be able to solve an integer linear program with Pyomo?

So I am solving a purely integer linear optimization problem with Pyomo on a single computer (core i-5, 12 GB RAM). The problem has around 10000 variables and 300 constraints. For doing this, I am ...
  • 165
3 votes
2 answers
136 views

Vehicle passenger assignment with capacity constraint

Problem Summary To match passengers (the number of passengers) to capacitated vehicles such that the profit is increased. All the vehicles have the same capacity $c$. It is not important to track ...
  • 33
1 vote
2 answers
62 views

If $x_1 \geq 4$ then **one** out of the following three constraints must hold: $x_2 \leq 3, x_3 \leq 4, x_4=5$

How does one linearize the following constaints: If $x_1 \geq 4$ then one out of the following three constraints must hold: $x_2 \leq 3, x_3 \leq 4, x_4=5$. $$x_1 \leq 4 + Mz_1$$ $$x_2 \leq 3 + M(1-...
  • 119
6 votes
1 answer
404 views

Doubles Round Robin Sorting Algorithm

Background: I have a group of 6 guys that get together and play pickleball every week. We play 2v2 and 2 players sit each game. We play 2 sets of 6 games each week (12 total games) - in each set, ...
1 vote
2 answers
99 views

Does the cvxpy replace the max function by MIP formulation under the hood?

Does the cvxpy replace the max function, which is convex, by MIP formulation under the hood when shows up in the constraints (for example, $\max(x,y)\le z$) or in the objective function? In gurobipy, ...
2 votes
1 answer
379 views

If/then constraint formulation

Let's assume we have event $i=1,2,\cdots,k$, denoted as $\text{event}_i$. We know for a fact that $\text{event}_i$ is smaller then $\text{event}_{i+1}$ i.e., $\text{event}_i \leq \text{event}_{i+1}$. ...
2 votes
1 answer
103 views

Conditional constraint for binary

Could you please check where I might be wrong? Task is: If $z=1$, then either $x=1$ or $y=1$ My approach: If $z=1$, then $x+y=1$ $\implies x+y\le1$ $\implies x+y\ge1$ If $z=0$, then $x+y\ge0 - M\cdot(...
5 votes
2 answers
213 views

Binary variable constraint

The task is to ensure that if $x_i = 1$ for at least $k$ of the possible indices $i$ in $\{1,...,n\}$ then $y = 1$, where $k$ and $n$ are parameters, $x$ is a binary variable vector with $n$ elements, ...
1 vote
1 answer
74 views

Simple Constraint Programming Problem: docplex works but equivalent ortools model is infeasible

I have a simple constraint programming model which can be solved using the docplex library, however I am struggling to implement the same model using ...
  • 145
2 votes
1 answer
86 views

Modeling advice: scheduling problem with judged events and "blocks" of judging assignments

I am considering a scheduling problem in which the events are officiated, likely as a MILP problem. I'm getting hung up on how best to model a particular requirement of how the judged events are ...
  • 123
3 votes
2 answers
159 views

Simple Integer Optimization Problem: docplex CP model works but equivalent PuLP+CBC model is infeasible?

I have an integer optimization problem with one constraint per decision variable and no objective function. It can be coded and solved using docplex, however I am ...
  • 145
2 votes
1 answer
87 views

Modify the network model to accommodate multiple vehicles

Given a directed network (or graph) $G = (V,E)$ with each edge $e_{ij}$ having a non-negative cost as the travel time from $i$ to $j$. Each node has an associated demand $d_i$. If the demand is ...
  • 145
1 vote
1 answer
113 views

Assignment problem with constrained number of unique tasks

I have an interesting assignment problem in which I have a cost matrix for workers and tasks, and need to assign each worker to exactly one task to minimize the cost. However, this is all subject to ...
5 votes
3 answers
420 views

Maximize the minimal distance between true variables in a list

I'm using the OR-Tools CP-SAT solver on a list of $n$ boolean variables $x_i$. I'm trying to maximize the minimal distance between two true variables in this list, as illustrated by the following ...
  • 235
2 votes
0 answers
48 views

Multi-objective optimization with known variable dependencies (via a graph) -- what is this called?

Suppose that I am trying to solve a standard multi-objective optimization problem: $$ \min_{ \begin{array}{c} \textbf{x} \in S \end{array} } \left [ f_1(\textbf{x}),f_2(\...
  • 121
3 votes
1 answer
216 views

Unexpected runtime error

I have a model that contains the sets (both ordered and Days also circular): Days and Personnel, and I'm trying to make a restriction run exaclty once per Day for every member of Personnel. I'm using ...
10 votes
4 answers
908 views

Is there an open-source equivalent to LocalSolver?

I have a constraint programming problem that is easy to formulate and solve (with high solution quality) in LocalSolver. However, I would really prefer to use something open source for ...
1 vote
1 answer
77 views

Traversing a list data dynamically in Pyomo Abstract Model

In my PYOMO abstract model, I am reading my data file and storing some specific attributes in a list say demand=[]. I am reading the data file as follows: ...
4 votes
1 answer
144 views

Creating constraints dynamically in pyomo abstract model

I have a networkX graph with few nodes and these nodes have attributes such as "demand". ...
2 votes
1 answer
170 views

RAM overflow when scheduling 1000+ intervals

Due to the answers to this and this questions, I was able to find the optimal solution for scheduling problem. However, if there are many tasks that must be scheduled, e.g. 1000+, then the solver ...
2 votes
1 answer
202 views

CP-SAT solver doesn't use all space available for scheduling

This problem is a continuation of this problem. The issue here is the solver doesn't use the whole space available for the scheduling and thus some jobs are not being scheduled. For example: we need ...
2 votes
0 answers
60 views

Assignment/scheduling how to formulate considering job time and job cost

I have the following problem that I do not know how to formulate. There are a fixed number of workers $w_i \in W$ for $i \in [1…N]$. Also, there are a fixed number of jobs that must be assigned to ...
3 votes
2 answers
59 views

Constrained shift assignment problem using ilogcp solver can´t find an optimal solution

I´ve been trying to solve a contrained assignation problem given a set of constraints based in a real-world problem. I modeled the problem in AMPL as follows: ...
3 votes
1 answer
202 views

Force gaps between tasks, tasks are scheduled within their job's time windows in Jobshop problem

The problem I'm trying to solve is a modification of the original Jobshop problem. The additional constraints are: There is only one machine for all jobs and their tasks. Each job has a priority (...
7 votes
2 answers
839 views

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

So suppose I have integer variables $x_1,x_2,\dots,x_N$ and I enforce that the integer variables are bounded i.e $1 \leq x_i \leq N$ I was interested in posing a constraint so that in the collection $...
  • 205
2 votes
0 answers
46 views

How to add a cut to avoid previously found solution? [duplicate]

I do have a MILP problem. The decision variables are Integer ones. Let's call them $x_i$ and i $\in \{0,1,2,3,...,N \}$ I do want to find all distinct solutiuons for this problem. The problem is ...
3 votes
2 answers
484 views

What is the difference bewteen CP and MILP approaches in Job Shop Scheduling?

My understanding is Constraint programming (CP) is a sub-set of MILP but in MILP we not only try to find a feasible solution (like CP) but also we should optimize an objective function. I do have a ...
2 votes
1 answer
135 views

Software for Feasibility Problems

I face a feasibility problem of type $$ c_i(\boldsymbol x) \leq 0, i = 1, \dots, \mathcal{I} \\ c_e(\boldsymbol x) = 0, e = 1, \dots, \mathcal{E} $$ where $\mathcal{I} + \mathcal{E} \gg \text{dim}(\...
  • 297
2 votes
1 answer
103 views

Finding Diverse Paths using Constraint Programming

I am working on a graph problem and want to find some link-disjoint paths between given node pairs. I was wondering if there is an efficient way to achieve this in CP. I checked OR-Tools (routing and ...
6 votes
0 answers
83 views

Graph coloring problem while counting cliques

Let $G$ be a graph with a set of nodes $V$ and a set of edges $E$. Let $G'$ be a graph with the same set of nodes $V$ but a second set of edges $E'$. For a set of nodes $X\subset V$, we denote $f(X)$ ...
2 votes
0 answers
59 views

Good encoding for grid layout problem

How would you encode the problem given by https://oeis.org/A337663 with an off-the-shelf solver? You need to lay out $n$ ones and $2, 3, ..., m$ on an infinite grid, for $m$ as large as possible. For ...
3 votes
0 answers
351 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 ...
4 votes
1 answer
144 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 ...
  • 79
2 votes
1 answer
167 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 -...
5 votes
1 answer
97 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 ...
  • 159
7 votes
4 answers
900 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....
  • 583
3 votes
1 answer
1k 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 ...
  • 139
4 votes
2 answers
782 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.)...
  • 746
7 votes
2 answers
262 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 ...
  • 189
1 vote
1 answer
436 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 ...
3 votes
1 answer
71 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{...
  • 31
1 vote
0 answers
77 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....
  • 111
2 votes
1 answer
152 views

Adding a variable makes the model unsatisfiable in MiniZinc

I have the following model. ...
  • 225
0 votes
0 answers
302 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: ...
  • 119
2 votes
1 answer
75 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$ ...
2 votes
1 answer
179 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()...
2 votes
1 answer
479 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" ...
2 votes
1 answer
52 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 ...
  • 121