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
5 votes
2 answers
646 views

How to measure model quality in OR-Tools?

After creating my model for a problem, what steps should I take to test if a change in the model is actually helpful or not? In Python, ...
Stradivari's user avatar
  • 1,414
5 votes
2 answers
1k 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.)...
kur ag's user avatar
  • 815
5 votes
1 answer
3k views

Cumulative Constraint OR-Tools

I'm trying to solve an rcpsp model. I can't find documentation for the AddCumulative function of OR-Tools. How should this function be used? I want to write this ...
Diego R. Troncoso's user avatar
5 votes
2 answers
525 views

Formulation of a constraint in a MIP for an element in different Sets

I have an element e $\in E$ with $E$ the set containing all elements e and $e \in Y_i$ with $Y_i \subseteq E$. Each set $Y_i$ has different attributes. $G_j$ is a set of sets and the following holds: $...
Georgios's user avatar
  • 1,193
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
5 votes
1 answer
375 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 ...
campioni's user avatar
  • 1,133
5 votes
0 answers
152 views

How to handle constraints in docplex to states the relation between two variables?

I am using docplex.cp and I need to state the following constraint: $$\sum_{c}(X_p{_w}_{cj}+X_{p+1}{_{w'}}_{cj+1})\leqslant T_w{_{w'}}_{,jj+1} + 1$$ Knowing that the binary variables are: $X_p{_w}_{...
campioni's user avatar
  • 1,133
5 votes
0 answers
42 views

In a binary logistic regression context, how to introduce a constraint to model the dependency between consecutive samples

Imagine we are running a logistic regression to identify opportunities for car sale promotion, using previous promotion campaign's result. Each $y$ is the increase of car sale after the promotion. ...
eight3's user avatar
  • 481
4 votes
3 answers
502 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
4 votes
2 answers
2k 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 ...
Tommy Lees's user avatar
4 votes
1 answer
1k views

How exactly does OptionalIntervalVar work in OR-Tools?

I created OptionalIntervals for a number of tasks: ...
Diego R. Troncoso's user avatar
4 votes
1 answer
596 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 ...
Antonio Piemontese's user avatar
4 votes
1 answer
179 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$...
Koli's user avatar
  • 43
4 votes
1 answer
325 views

Creating constraints dynamically in pyomo abstract model

I have a networkX graph with few nodes and these nodes have attributes such as "demand". ...
Waqas Swati's user avatar
4 votes
1 answer
153 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 ...
el_bulm's user avatar
  • 79
4 votes
1 answer
265 views

Constraint programming in OPL: intervals covering time slots

I am trying to model the following: There is a shop open from xx AM to yy PM. In each 30 min time slot, there have to be demand[timeSlot] = x employees present. E.g. the shop is open from 08am to ...
ORspecialist's user avatar
4 votes
1 answer
467 views

Machine Allocation & optimal Utilization using python

Problem statement: Meet the demand which can be met across 2 facilities each having multiple machines where several components are made. The objective is to find the optimal solution to meet the ...
Shankar Pandey's user avatar
4 votes
0 answers
107 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+...
Diego R. Troncoso's user avatar
3 votes
2 answers
353 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. ...
Approximations's user avatar
3 votes
2 answers
676 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 ...
Optimization team's user avatar
3 votes
2 answers
804 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
3 votes
2 answers
794 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.
Best_fit's user avatar
  • 567
3 votes
1 answer
511 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 ...
kur ag's user avatar
  • 815
3 votes
2 answers
289 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 ...
user856754's user avatar
3 votes
1 answer
306 views

How to write a LP/MIP to mark the items in a time-series list after a fixed delta?

I have a time series list like this. ...
Vinay's user avatar
  • 203
3 votes
1 answer
655 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
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
3 votes
2 answers
294 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
3 votes
1 answer
306 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 ...
Cyrus Roettern's user avatar
3 votes
2 answers
69 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: ...
Cyrus Roettern's user avatar
3 votes
2 answers
310 views

Could DOcplex.CP recognize that it solves the graph coloring minimization problem?

I created a graph coloring DOcplex.CP model inspired by this example. However, I do not know the number of colors in advance. The goal is to minimize the number of colors (i.e., get as close as ...
Alexander Pozdneev's user avatar
3 votes
2 answers
56 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
3 votes
2 answers
248 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
2 answers
263 views

Limit number of switches in employee scheduling problem

Here is a scheduling problem I need to solve. Given the demand for 2 positions in 1 week with 3 shifts per position, I need to allocate the employees accordingly with some extra operational ...
Psyndrom Ventura's user avatar
3 votes
1 answer
195 views

ValidateModel or tools in c++ and proto problems

I'm trying to validate my model, this is the relevant part of my code: ...
Diego R. Troncoso's user avatar
3 votes
1 answer
355 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 (...
Artem Popov's user avatar
3 votes
1 answer
72 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{...
nekrald's user avatar
  • 31
3 votes
1 answer
2k 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 ...
Yiğit Çatak's user avatar
3 votes
1 answer
136 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 ...
Mohammad Namakshenas's user avatar
3 votes
1 answer
317 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 ...
danielcharters's user avatar
3 votes
1 answer
227 views

On what kind of problems a local search may perform better than MIP / CP techniques? [closed]

In combinatorial optimization, on what type of problem a local search may lead to better & quicker solutions than usual mixed-integer programming and constraint programming techniques ? By type ...
Aral's user avatar
  • 63
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
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
3 votes
1 answer
4k 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 ...
V Shreyas's user avatar
  • 139
3 votes
0 answers
463 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 ...
Srikanth Shastry's user avatar
3 votes
0 answers
156 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, \\& ...
Apprentice's user avatar
3 votes
0 answers
198 views

Power of variable or tools

I'm working with OR Tools in Python and I need to define the objective function an expression of the variables. In particular, the objective function is $$\frac{c_j}{1.7^{s_j}}$$ with $c_j$ ...
Clopen's user avatar
  • 131
2 votes
3 answers
608 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, ...
Mahmoud's user avatar
  • 127
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