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
2 votes
1 answer
121 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 ...
0 votes
0 answers
34 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 ...
0 votes
0 answers
55 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 ...
0 votes
3 answers
100 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 ...
1 vote
1 answer
175 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 ...
0 votes
0 answers
102 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 ...
11 votes
4 answers
2k 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
121 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?
8 votes
1 answer
293 views

Workforce Scheduling problem - Modelling to minimize resources

I am working on a scheduling program for a service desk. I want to decide the number of people required to come in at each shift. The data I have is: There are 4 overlapping shifts Arrival pattern at ...
2 votes
2 answers
105 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 ...
3 votes
1 answer
312 views

How to convert non-normal probabilistic constraints to deterministic ones for mathematical modelling?

I am working on a chance-constrained optimisation model that takes into account uncertainty. I am aware of how to convert constraints that are of a probabilistic nature into the equivalent ...
0 votes
1 answer
46 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 ...
10 votes
1 answer
2k views

Floating points in OR-Tools

I'm trying to solve an RCPSPDc model (maximizing the net present value instead of a makespan). The objective function is: $\sum\limits_{j \in \text{Tasks}} e^{-\theta\cdot s_{j}}\cdot p_{j}$, where $...
1 vote
0 answers
54 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 ...
2 votes
1 answer
178 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 ...
1 vote
1 answer
79 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 ...
6 votes
1 answer
116 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 ...
11 votes
1 answer
502 views

Modeling an assignment/scheduling problem to minimize total wait

I have an assignment type problem in which there is a set of students, $S$, and a set of training classes $T$. Each training has a fixed start and end day and can accommodate at most 1 student. In ...
6 votes
1 answer
1k views

Constraint Programming OR-Tools finding Matrix Combinations

As a similar post of mine Find all Combinations of a Matrix I am trying to find matrix combinations with entries $>0$ meaning for a matrix \begin{bmatrix} 0 & 1 & 3 \\ 5 & 2 & 1 \\ ...
6 votes
0 answers
165 views

Modelling issue with precedence constraint in OR-Tools

I'm trying to solve an RCPSPDc model It is infeasible, although Ilog Cplex solves it, so I think I have a modelling issue. I have more constraints but the precedence is the one that makes it ...
3 votes
1 answer
194 views

ValidateModel or tools in c++ and proto problems

I'm trying to validate my model, this is the relevant part of my code: ...
2 votes
1 answer
125 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 ...
8 votes
1 answer
203 views

Strategy for filling a table only slightly dependant on the number of columns

I'm using the OR-Tools CP-SAT solver to fill a table with integers, with various constraints, as illustrated by the x in the following figure. ...
4 votes
0 answers
106 views

Modelling issue with rcpsp and boolean expressions

I'm trying to solve an RCPSPDc problem in OR-Tools with CP-SAT solver. In my RCPSPDc model (with discount rate) i want to set this objective: $$\max_{s}\sum_{j\in J}\text{profit}_{j}\cdot \frac{1}{(1+...
2 votes
1 answer
290 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
0 answers
76 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 ...
5 votes
3 answers
480 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 ...
2 votes
1 answer
667 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" ...
7 votes
1 answer
3k views

CP-SAT ortools - Is there any complete list of possible/available StringParameters for the CpSolver?

I wonder if there is any list of string parameters documented. So far, I only know max_time_in_seconds and num_search_workers. ...
2 votes
1 answer
2k 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? ...
1 vote
2 answers
66 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 ...
6 votes
1 answer
436 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 ...
9 votes
1 answer
292 views

How to tackle large nurse scheduling problem?

I have a nurse-scheduling type of problem with a time span of a year and many employees. Formulation My main variables are: \begin{align}x_{e,t} &= \begin{cases}1 \text{ if employee } e \text{ ...
5 votes
1 answer
370 views

Precedence constraints using binary variables - DOCPLEX

I would like to establish a precedence constraint to ensure the precedence relation of tasks. I have a set of tasks available, but required tasks are not always the same. It means, the tasks executed ...
7 votes
2 answers
436 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 ...
1 vote
0 answers
62 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 ...
5 votes
2 answers
218 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 ...
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 ...
0 votes
0 answers
59 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 ...
1 vote
1 answer
385 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 ...
1 vote
2 answers
251 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 ...
3 votes
2 answers
348 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: ...
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 ...
3 votes
1 answer
66 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\\ &\...
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 ...
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 ...
0 votes
1 answer
160 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 ...
2 votes
2 answers
396 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 ...
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 ...
-1 votes
1 answer
67 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 ...