Questions tagged [constraint-programming]
For questions on modeling satisfaction or optimization problems in languages designed for expressing (often high-level) constraints on decision variables.
161
questions
41
votes
3
answers
12k
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 ...
- 2,398
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?
- 2,013
19
votes
1
answer
466
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,...
- 1,006
19
votes
3
answers
420
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 ...
- 4,673
18
votes
2
answers
319
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 ...
- 181
14
votes
2
answers
527
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 ...
- 3,396
11
votes
4
answers
568
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 ...
- 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 ...
- 163
11
votes
1
answer
367
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 ...
11
votes
1
answer
479
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 ...
- 111
10
votes
2
answers
558
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 ...
- 2,140
10
votes
1
answer
1k
views
Floating points in ORtools
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 $...
10
votes
1
answer
273
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, ...
- 131
9
votes
3
answers
475
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 ...
- 343
9
votes
3
answers
745
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 ...
- 937
9
votes
1
answer
616
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.
- 567
9
votes
2
answers
513
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"),
...
- 193
9
votes
1
answer
592
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 ...
- 1,133
9
votes
1
answer
265
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{ ...
- 1,414
8
votes
3
answers
890
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 ...
- 943
8
votes
1
answer
454
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 ...
8
votes
1
answer
205
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 ...
8
votes
1
answer
504
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 ...
- 183
8
votes
2
answers
871
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 ...
- 1,208
8
votes
1
answer
191
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.
...
- 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, ...
- 1,133
7
votes
2
answers
868
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
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, ...
7
votes
2
answers
368
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 ...
- 171
7
votes
4
answers
951
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
7
votes
2
answers
373
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
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.
...
7
votes
2
answers
281
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 ...
- 295
7
votes
1
answer
481
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 ...
- 2,086
7
votes
2
answers
627
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 ...
- 343
7
votes
0
answers
76
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
...
- 87
6
votes
1
answer
467
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 ...
- 245
6
votes
1
answer
582
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, ...
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 \\
...
- 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 ...
6
votes
1
answer
382
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 ...
- 75
6
votes
0
answers
89
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)$ ...
- 93
6
votes
0
answers
217
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 ...
6
votes
0
answers
156
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 ...
6
votes
0
answers
431
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 ...
- 61
5
votes
4
answers
939
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 ...
- 81
5
votes
2
answers
345
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, ...
5
votes
3
answers
461
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
5
votes
3
answers
361
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 ...
- 95
5
votes
2
answers
604
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, ...
- 1,414