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
41 votes
3 answers
13k views

How to select a Constraint Programming Solver

I would like to clarify that I am absolutely not an expert when it comes to constraint programming (I happen to use it when it seems to be the right tool for the right job). It is my understanding ...
Renaud M.'s user avatar
  • 2,418
29 votes
3 answers
7k views

What is the difference between integer programming and constraint programming?

At first glance both approaches appear to be very similar. What are the major differences between integer programming and constraint programming?
YukiJ's user avatar
  • 2,023
19 votes
1 answer
490 views

Combinatorial Optimization: Metaheuristics, CP, IP -- "versus" or "and"?

"Recently" someone asked on Twitter whether "people still use genetic algorithms for integer programs". The "majority answer", i.e., 1 out of 1, was: "Yes" . So,...
fbahr's user avatar
  • 1,026
19 votes
3 answers
436 views

AI gets a lot of attention these days. Does constraint optimization get more attention, too? Why (not)?

Looking at the news as well as at content of tech conferences, I think it is fair to say that AI is getting a lot of attention -- one might even call it an AI hype (like in the 80's). Plenty of ...
Geoffrey De Smet's user avatar
18 votes
2 answers
326 views

Mathematically creating the 'perfect' permutation for reservations in a hostel

I am working at a hostel which uses a reservation system for each room and the beds in the room (e.g. $14$ beds in one room, bed numbers $1-14$.) When we get bookings for multiple people, we assign ...
JRogers97's user avatar
  • 181
14 votes
2 answers
558 views

How to implement a custom global constraint in IBM's ILOG CP optimizer

How do you implement a custom, global constraint in CP Optimizer? This is not a trivial thing to do, as CP Optimizer does not ship any examples of a custom constraint, and the documentation is very ...
Joris Kinable's user avatar
11 votes
4 answers
590 views

Good resources for solving techniques (Metaheuristics, MILP, CP etc)

I want some resources (tutorials, online courses, lecture notes, articles, books, etc.) to learn the different techniques to solve OR problems (metaheuristics, CP, MILP, etc). It would be better if ...
Cloud's user avatar
  • 111
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 ...
Kathryn Twomey's user avatar
11 votes
1 answer
396 views

Algorithm for workforce scheduling for call volumes

I am trying to solve a workforce scheduling and optimization problem. Available data: daily level forecasted call volumes, shift schedules, resource utilization at the aggregate level, AHT at ...
Lalitha Sundar Iyer S's user avatar
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 ...
Connor's user avatar
  • 111
10 votes
2 answers
580 views

What is the standard practice in Constraint Programming modeling?

I know some general concepts regarding Constraint Programming (e.g., the ones explained in this answer). I am interested in learning how to formulate a combinatorial optimisation problem as a ...
rasul's user avatar
  • 2,150
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 $...
Diego R. Troncoso's user avatar
10 votes
1 answer
286 views

RCPSP minizinc model

I'm working on a resource‐constrained project scheduling problem (RCPSP) in Minizinc but I have problems with the running times when the dataset is big (like 400 jobs, 2 resources, 1,000 precedences, ...
Clopen's user avatar
  • 131
9 votes
3 answers
526 views

To which area does constraint programming belong?

The problem I solved is a flow-shop scheduling problem with parallel machines. I solved it with the IBM ILOG CPLEX Optimization framework. There I used the constraint programming (CP). The question ...
Tobias M.'s user avatar
  • 343
9 votes
3 answers
1k 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 ...
Joffrey L.'s user avatar
9 votes
3 answers
819 views

Interval variables in MIP

In Constraint Programming it is possible to use interval variables to represent intervals of time during which something happens (see here), usable in scheduling problems, for example. Is there ...
Libra's user avatar
  • 937
9 votes
1 answer
628 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.
Best_fit's user avatar
  • 567
9 votes
2 answers
570 views

Which MiniZinc-compatible solvers are best suited for floating decision variables and non-linear constraints?

We are working on a production scheduling problem that has both discrete ("how much to produce from good x and where") and continuous elements ("keep the workload of a production site below 0.7"), ...
ks.and1's user avatar
  • 193
9 votes
1 answer
612 views

TSP problem: traveller does not visit all nodes - Google OR-tools

Context: I am dealing with a kind of scheduling problem, in which I have a set of tasks and machines. All tasks must be assigned to machines (not necessary all of them). In addition to that, I must ...
campioni's user avatar
  • 1,133
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{ ...
Stradivari's user avatar
  • 1,414
8 votes
1 answer
485 views

Precedence Constraint in OR-Tools

I'm trying to write this constraint in C++ and add it to my model (addLessOrEqual): $$\text{start}_{i}+\text{duration}_{i}\le\text{start}_{j}$$ for an $(i,j)$ arc ...
Diego R. Troncoso's user avatar
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 ...
Lalitha Sundar Iyer S's user avatar
8 votes
1 answer
549 views

Minizinc: How to use a predicate in an assert statement?

Trying to use minizinc builtins to do some basic validation of data inputs but I get a type error ...
Eugene's user avatar
  • 183
8 votes
2 answers
945 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 ...
Matheus Diógenes Andrade's user avatar
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. ...
Blackhole's user avatar
  • 235
7 votes
3 answers
1k views

Constraint programming using solver: how to state the time limit of search?

Could someone give additional explanations about the TimeLimit of CPLEX for CPO? I am using CPLEX to solve a problem of assignment and scheduling in which each task needs to be assigned to a worker, ...
campioni's user avatar
  • 1,133
7 votes
2 answers
882 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 $...
Vogtster's user avatar
  • 205
7 votes
1 answer
1k views

How to use the least number of colours to colour different routes of a bus route such that no two intersecting routes will have the same colour

I would like to know of a method in which if provided say 10 routes with details regarding which route intersects with which another route, we can use the least number of colours to colour the routes, ...
Burhanuddin Samiwala's user avatar
7 votes
2 answers
434 views

Are there some benchmark problems for CSP Solvers?

I am building my own CSP solver with simple backtracking, AC3 filtering and variable/value ordering heuristics. It supports non binary constraints. I've done some good progress and I'd like to ...
yannicuLar's user avatar
7 votes
4 answers
969 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....
JKHA's user avatar
  • 679
7 votes
2 answers
435 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 ...
gregy4's user avatar
  • 189
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. ...
The Random Forum Guy's user avatar
7 votes
2 answers
289 views

CPLEX CP Optimizer Java API function missing

I can not seem to find the needed functions to model the following problem through the Java API (CP Optimizer): a machine that has downtime and sequence-dependent setup times, with the extra ...
Maarten's user avatar
  • 295
7 votes
1 answer
504 views

Can docplex (module for Constraint Programming optimizer CPLEX for Python) read .lp or .mps file?

I want to solve a problem with docplex.cp (module for Constraint Programming optimizer CPLEX for Python), and the problem is available in ...
Mostafa's user avatar
  • 2,104
7 votes
2 answers
649 views

CP Framework/Solver for .Net Core

First I want to say that I'm very new to this field. As far as I understand it, there are two different ways to use a Constraint Programming (CP) Solver: Using the API from the Solver itself. For ...
Tobias M.'s user avatar
  • 343
7 votes
0 answers
79 views

Which Constraint solver is extensible to CSP algorithms?

I am novice to constraint programming and I need to implement the following algorithms. Backtacking Conflict-based backjumping AC partial lookahead MAC Forward checking Forward checking + dom ...
Cecelia's user avatar
  • 87
6 votes
1 answer
500 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 ...
Ibrahim Amer's user avatar
6 votes
1 answer
779 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
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 ...
rsella's user avatar
  • 169
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 \\ ...
Georgios's user avatar
  • 1,193
6 votes
1 answer
2k views

assigning values to IntVar if and only if BoolVar, else zero [or-tools]

If I have an IntVar s[j] stored in a vector s, is it possible to iterate for (a period of ...
Diego R. Troncoso's user avatar
6 votes
1 answer
433 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 ...
Shinra_SGr's user avatar
6 votes
0 answers
94 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)$ ...
Jin Kazama's user avatar
6 votes
0 answers
226 views

OptionalIntervalVar enforced but not working OR-TOOLS

I'm using OptionalIntervalVar and then maximizing the starts. The optimal solution is not affecting the other variables that creates the ...
Diego R. Troncoso's user avatar
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 ...
Diego R. Troncoso's user avatar
6 votes
0 answers
442 views

How to make constraints satisfy disciplined convex programming guidelines?

How do I turn my convex constraints (described below) into constraints that are DCP so that I can solve them in CVXPy? Is there some ``cheat sheet'' of standard tricks? I'm trying to implement the ...
Dupin's user avatar
  • 61
5 votes
4 answers
1k 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 ...
bsha's user avatar
  • 81
5 votes
2 answers
428 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
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 ...
Blackhole's user avatar
  • 235
5 votes
3 answers
373 views

How can I optimize this integer programming constraint problem without running out of memory?

I am trying to run this constraint problem but the memory runs out, $$S_{i}$$ are 1975 Students that need to be assigned to one of 188 teacher assistants classes, each teacher assistant has to chose a ...
jeroaranda's user avatar