Questions tagged [constraint-programming]
For questions on modeling satisfaction or optimization problems in languages designed for expressing (often high-level) constraints on decision variables.
28
questions with no upvoted or accepted answers
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
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
0
answers
148
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}_{...
- 1,133
5
votes
0
answers
40
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.
...
- 481
4
votes
0
answers
101
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+...
3
votes
0
answers
437
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 ...
3
votes
0
answers
155
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, \\& ...
- 215
3
votes
0
answers
187
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$ ...
- 131
2
votes
0
answers
94
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 ...
- 21
2
votes
0
answers
58
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 ...
- 33
2
votes
1
answer
91
views
Rearrange 'x' piles of items into eight possible locations/bins based on item colour and length
I have an optimisation problem that I believe is a variant of the 'bin packing problem with precedence', but I'm unsure of if that is the correct paradigm to work with and I'm not having a huge amount ...
- 21
2
votes
0
answers
64
views
Multi-objective optimization with known variable dependencies (via a graph) -- what is this called?
Suppose that I am trying to solve a standard multi-objective optimization problem:
$$
\min_{
\begin{array}{c}
\textbf{x} \in S
\end{array}
}
\left [ f_1(\textbf{x}),f_2(\...
- 121
2
votes
0
answers
65
views
Assignment/scheduling how to formulate considering job time and job cost
I have the following problem that I do not know how to formulate.
There are a fixed number of workers $w_i \in W$ for $i \in [1…N]$.
Also, there are a fixed number of jobs that must be assigned to ...
- 169
2
votes
0
answers
67
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 ...
- 232
2
votes
0
answers
137
views
Multiple Depot/Crew Office Bus Driver Scheduling Modelling
I'm working on Bus Driver Schedule with multiple add-on constraints that are complex and hence trying to figure out how this can be achieved.
Reference of Bus Driver Scheduling using OR-Tools:-
https:/...
- 21
2
votes
0
answers
89
views
Consistency Level of Constraints
Recently I started using CP and translated my first MIP model into a CP model with the IBM CP Optimizer. Lately I was confronted with a question I could not answer:
"What is the consistency level ...
- 93
2
votes
0
answers
80
views
Finding Optimal Route using different Paths
I have a list of paths e.g. path 1 takes you from point A to B. A person needs to complete 5 of such paths.
$$Route1 = path1 + ...
- 205
2
votes
0
answers
175
views
Operation hours optimization for circular schedule
Here is my problem. A store has X = 15 electical devices with the ability to work non-stop, fully charged, up to 8 hours. Their battery charge lasts 2 hours and the operating hours of the store differ ...
- 315
2
votes
0
answers
65
views
Algorithm for Trainyard Marshall optimization problem
The problem I am trying to solve is the 2014 RAS problem. The link is the following
The problem
Trains come to the humpyard where each compartment of a train gets humped or disassembled and then each ...
- 21
1
vote
1
answer
129
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 ...
- 11
1
vote
0
answers
98
views
Minimizing total number of banners used in the cover buildings problem modelled
I was watching a video about Google OR-Tools where they were solving this cover building problem from Codility challenges using constraint programming.
In short, you have a list of building heights, e....
- 111
1
vote
0
answers
93
views
Question on quadratically constrained quadratic program
If the constrained optimization problem is a quadratically constrained quadratic program of the form \begin{align}\min&\quad x^HQx-a(x+x^H)+b|z^Hx|^2\\\text{s.t.}&\quad\|x\|^2\le1\end{align} ...
- 19
1
vote
0
answers
202
views
Fixed cost associated to SlackVar(waiting time cost) [CVRPTW]
I'm modeling a CVRPTW with some features:
Each type of vehicle has a cost per km and a fixed cost per trip. To calculate these costs, I am using these methods for this:
...
- 111
0
votes
0
answers
53
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 ...
- 151
-1
votes
1
answer
209
views
[OR-Tools][CP-SAT] Implement an indicator function in a constraint
Good morning ! I would like to implement this constraint using CP-SAT (see image below).
x_i,j is a boolean variable, a and b are given. The problem is that I don't know how to implement the ...
