Questions tagged [constraint-programming]
For questions on modeling satisfaction or optimization problems in languages designed for expressing (often high-level) constraints on decision variables.
16
questions
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
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
3
votes
1
answer
266
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 (...
- 75
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
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
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
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
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
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
482
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: $...
- 1,193
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, ...
3
votes
2
answers
259
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 ...
- 39
2
votes
1
answer
362
views
CP-SAT solver doesn't use all space available for scheduling
This problem is a continuation of this problem. The issue here is the solver doesn't use the whole space available for the scheduling and thus some jobs are not being scheduled. For example: we need ...
- 75
2
votes
2
answers
360
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 ...
- 273
1
vote
1
answer
164
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?
- 19
1
vote
3
answers
424
views
How can I linearize this IF-THEN constraint?
Let
$P_{t,u}; t=1,2,\ldots,T, u=1,2,\ldots,U$ be known values
$\alpha$ is also a known parameter
$X_{t,u}$ an optimization variable
I have the following constraint: IF $P_{t,u}\geq\alpha$, THEN $X_{...
- 2,211