Skip to main content

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
2 answers
57 views

Constrained optimization with heuristic algorithm in actual production

In a real production problem, if you decide to use a heuristic algorithm (such as GA), what are the mainstream methods to deal with constraints in constraint optimization? I mean, I knew that there ...
CangWangu's user avatar
2 votes
1 answer
63 views

choose constraint from IIS to build penalty function

Suppose I have a single objective optimization model whose constraints are all composed of linear equations and linear inequalities, and now that it is proven to be infeasible in a calculation using ...
CangWangu's user avatar
3 votes
2 answers
817 views

How to avoid similar solutions?

I have a problem like this $x_1 +x_2 +x_3 =10$ let's assume $0 \leq x_i \leq 10$ It is obvious that this problem has more than one solution For example : Solution 1 : $x_1 =0 , x_2= 1 , x_3 =9$ ...
Optimization team's user avatar
2 votes
1 answer
131 views

Priority based demand fulfilment in Linear Constraint

Say I have 3 sources. D1, D2, D3. their capacity is 100, 200, 400. I want to create some constraints such that First D1 is depleted then D2 and then D3. But the catch is you cant use min or max ...
kunal chakraborty's user avatar
1 vote
1 answer
57 views

DOCPLEX Job Shop Scheduling In With Downtime

I am scheduling tasks (audits) to machines (auditors) with machine skills and planned downtime as considerations. I am using the docplex package in Python and ...
Jacob Vandergriff's user avatar
0 votes
3 answers
107 views

How do I convert Integer Programming to Constraint programming?

/********************************************* OPL 12.10.0.0 Model Author: Shahrukh Creation Date: 10-Apr-2024 at 11:55:50 PM The podrace tournament involves n competitors (where n is even) who all ...
Shahrukh Mohd's user avatar
0 votes
0 answers
61 views

Solving a multi depot multi vehicle capacitated routing problem using global constraints

I have built the model, but at this point, I am not sure how do I ensure that each fighter starts from the assigned depot and comes back to that depot. here is my code. The ...
Shahrukh Mohd's user avatar
0 votes
0 answers
104 views

Need Help for building two constraints in MIP model

Really need help for building two constraints with MIP model, I have written the required information and variable information on the diagram below. The way I think of it now is to use two ...
CangWangu's user avatar
1 vote
1 answer
122 views

Constraint Programming Interview

I'm new in CP. Want to start preparing for my upcoming interviews. What are the questions and topics should I study in CP to get my myself confident?
talkandtalkers's user avatar
0 votes
1 answer
48 views

Circular queue modeling

Let $P$ be a set of discretely interruptible processes/tasks; $T_i \in \mathbb{N}$ be the running time of process $i \in P$; And $\tau \in \mathbb{N}$ be the maximum amount of time a process can use ...
Matheus Diógenes Andrade's user avatar
2 votes
2 answers
109 views

Differentiability of solution of optimization problem with respect to constraint (properties, conditions etc)

Assume you have the following simple constrained optimization problem: $$ \begin{equation} \begin{split} &\min_x f(x) \\ & s.t \quad g(x) = c \end{split} \end{equation} $$ where $f,g$ are both ...
c zl's user avatar
  • 23
1 vote
0 answers
55 views

Tents and trees constraints

I am trying to express the constraints for the 'Tents and trees' puzzle in minizinc but I am a bit stuck... I can express that each tent must be attached to at least one tree That a tree must be ...
user1454590's user avatar
1 vote
0 answers
64 views

Problems for which constraint programming is the state-of-the-art approach

What are examples of problems for which the state-of-the-art approach is constraint programming? Considering either heuristic or exact approaches. I'm looking for specific problems, not just a class ...
fontanf's user avatar
  • 2,623
5 votes
2 answers
219 views

How to combine MIP solver with a CP one?

I am working on the scheduling problem in the class of parallel resource scheduling models. When I have studied some papers regarding that, I see the method that combines an MIP with a CP. The ...
A.Omidi's user avatar
  • 8,960
1 vote
1 answer
186 views

Job Scheduling with Energy Consumption using Linear Programming

I'm looking for some advice for an optimization problem regarding scheduling jobs in a datacenter. So I have a list of jobs and each job has a required time for finishing and a number of cores it has ...
wind.leon's user avatar
0 votes
0 answers
63 views

Multilinear programming over the simplex

Let $\triangle_3 \in \mathbb{R}^3$ be the $3$-simplex. I am solving a series of multilinear programming problems that looks like this: $$\text{Maximize}\sum_{0\leq i, j, k \leq 3} A_{i,j,k} x_i x_j ...
AspiringMat's user avatar
2 votes
0 answers
98 views

log-log regression as reward function in optimization problem

Consider the model $\hat{y}_t = e^{\text{trend} + \text{seasonality}} \prod_k^K x_{k, t}^{b_k}$ where $K$ denotes different investment alternatives. You can think that trend and seasonality are ...
pete lewis's user avatar
1 vote
1 answer
391 views

Discrete point inside a polygon formed by set of vertices

I am working on a problem where I have a set of 2D vertices and a test point. I want to chek whether the test point lies inside ...
Ken Adams's user avatar
3 votes
2 answers
368 views

OR-Tools CP-SAT solver: is it possible to name a constraint like in GUROBI

I try to implement cp model with OR-tools CP-SAT solver. Please, is it possible to name constraints for being able to manage conflict later like for variables: ...
Issouf's user avatar
  • 65
1 vote
2 answers
266 views

How to properly tackle a big model using weak constraints

I'm currently working on a model that has a large number of variables (around 200k), and I don't know what the proper way to handle such a big problem is. One suggestion I got is to use lazy ...
Marco's user avatar
  • 11
2 votes
0 answers
60 views

System Stability constraints formulation

I am working with a system having a massless 2D plane and on that plane there is a rigid object with some mass placed on it. I want to support the plane with wooden sticks such that the system is ...
Ken Adams's user avatar
3 votes
1 answer
67 views

Finding a starting ellipsoid and a minimum volume to approximate a convex optimization problem

Suppose we have a convex optimizatiom program: \begin{align} \min &\quad f_0(x)\\ s.t. &\quad h_i(x) = 0 && i=1,\ldots, p\\ &\quad g_i(x) \leq 0 && i=1,\ldots, m\\ &\...
eden hartman's user avatar
1 vote
1 answer
82 views

How to calculate the duration of a task in each shift?

I am solving a job scheduling problem with three shifts, the duration of all shifts are assumed to be known (and might be equal): The tasks can start from any shift We know the duration of each task ...
Optimization team's user avatar
0 votes
2 answers
37 views

Scheduling next shift such its not within X hours of previous shift

Hey i have this constraint that i am trying to code in python: "scheduling next shift such its not within X hours of previous shift" Given that i have start, end time of each shift and the ...
user12443's user avatar
1 vote
2 answers
70 views

Evaluation of linear expression with docplex based on a solution

For a CpModel using docplex, is there any function to evaluate a linear expression based on the variables values in the final solution? For example, for ...
Nara's user avatar
  • 11
0 votes
1 answer
166 views

Using binary variable or integer variable in Constraint Programming (CP)?

I am trying to solve an assignment problem by Constraint Programming (CP). Let us consider a task assignment problem that have $|M|$ tasks and $|N|$ machines, each task has different processing time ...
Penghui Guo's user avatar
2 votes
2 answers
406 views

Scheduling to minimize total "wait to start" time

I have a scheduling problem I am trying to work through. As I was outlining the problem, I realized it is probably of a known problem type, but I am unsure of what keywords to search for or what ...
Ike348's user avatar
  • 343
1 vote
1 answer
98 views

Modelling Optimal Sorting Networks

I am trying to find sorting networks having the optimal depth or optimal number of comparators by generating $2^n$ binary sequences where $n$ is the channel size. The main variables in my model are as ...
watchdogs132's user avatar
-1 votes
1 answer
72 views

How to set an objective to minimize the variance in ratio of allocation

I am trying to write a model where I have to distribute fractions of rent from properties to loans. The objective is to distribute the rents as equally as possible given the loan balance. Say there ...
Ashok Khatri's user avatar
3 votes
2 answers
249 views

how to count the number of values that are greater than zero in OR-Tools

I am using OR-Tools for an employees scheduling problem. I have a dictionary that is defined as an IntVar, where such dictionary contains the number of hours that will be assigned to each employee, ...
luca_dix's user avatar
3 votes
3 answers
150 views

Constraint programming problem with matrix of integers

I am trying to solve the following problem. Suppose $A$ is an $m \times n$ matrix of integers with entries in $\{1, \dots, k\}$. There are two kinds of constraints on the entries of this matrix: For ...
TheProofIsTrivium's user avatar
2 votes
1 answer
2k views

What exactly does the AddHint() method in Google OR-Tools' CP-SAT solver do?

I have an optimization problem that I am solving with CP-SAT and I am using the Python interface. Moreover, I know a good feasible solution coming from a heuristic and I want the solver to start its ...
John D's user avatar
  • 199
4 votes
3 answers
503 views

How can I formulate this 'if-then' constraint problem?

I have five integer variables, and I need to write some constraints on them: $x_0$ , $[x_1, x_2, x_3, x_4 ]$. $1 \leq x_i \leq 3$ if $x_0 =1$ then no constraint on $[x_1, x_2, x_3, x_4 ]$ if $x_0 =...
Optimization team's user avatar
-1 votes
1 answer
296 views

[OR-Tools][CP-SAT] Implement an indicator function in a constraint

Good morning ! I would like to implement this constraint using CP-SAT (see image below). x_i,j is a boolean variable, a and b are given. The problem is that I don't know how to implement the ...
Arthursbr's user avatar
1 vote
1 answer
773 views

About circuit constraints in OR - tools

I am trying to implement a scheduling problem to solve with CP-SAT from OR-tools. There, in particular, for every machine I want to add a time transition constraint from every task that is performed ...
John D's user avatar
  • 199
1 vote
1 answer
192 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?
Waldo's user avatar
  • 19
1 vote
1 answer
83 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 ...
guigux's user avatar
  • 113
3 votes
1 answer
658 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 ...
John D's user avatar
  • 199
3 votes
2 answers
152 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 ...
Corey's user avatar
  • 33
1 vote
3 answers
114 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 constraints: 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-...
Kemit4's user avatar
  • 119
6 votes
1 answer
819 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, ...
WoodGuyPurdue's user avatar
1 vote
2 answers
211 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, ...
Hussein Sharadga's user avatar
2 votes
1 answer
506 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}$. ...
OpenAtTheClose's user avatar
2 votes
1 answer
140 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(...
Bohdana Nevierova's user avatar
5 votes
2 answers
449 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, ...
Bohdana Nevierova's user avatar
1 vote
1 answer
174 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 ...
SlowLoris's user avatar
  • 145
2 votes
1 answer
103 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 ...
pholser's user avatar
  • 123
3 votes
2 answers
296 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 ...
SlowLoris's user avatar
  • 145
2 votes
1 answer
100 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 ...
endeavor's user avatar
  • 145
1 vote
1 answer
204 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 ...
madhatter5's user avatar