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
10 votes
4 answers
338 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 ...
1 vote
1 answer
53 views

Traversing a list data dynamically in Pyomo Abstract Model

In my PYOMO abstract model, I am reading my data file and storing some specific attributes in a list say demand=[]. I am reading the data file as follows: ...
3 votes
1 answer
70 views

Creating constraints dynamically in pyomo abstract model

I have a networkX graph with few nodes and these nodes have attributes such as "demand". ...
2 votes
1 answer
131 views

RAM overflow when scheduling 1000+ intervals

Due to the answers to this and this questions, I was able to find the optimal solution for scheduling problem. However, if there are many tasks that must be scheduled, e.g. 1000+, then the solver ...
2 votes
1 answer
90 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 ...
2 votes
0 answers
50 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 ...
3 votes
2 answers
56 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: ...
3 votes
1 answer
152 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 (...
7 votes
2 answers
818 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
2 votes
0 answers
43 views

How to add a cut to avoid previously found solution? [duplicate]

I do have a MILP problem. The decision variables are Integer ones. Let's call them $x_i$ and i $\in \{0,1,2,3,...,N \}$ I do want to find all distinct solutiuons for this problem. The problem is ...
3 votes
2 answers
392 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 ...
2 votes
1 answer
126 views

Software for Feasibility Problems

I face a feasibility problem of type $$ c_i(\boldsymbol x) \leq 0, i = 1, \dots, \mathcal{I} \\ c_e(\boldsymbol x) = 0, e = 1, \dots, \mathcal{E} $$ where $\mathcal{I} + \mathcal{E} \gg \text{dim}(\...
  • 297
2 votes
1 answer
90 views

Finding Diverse Paths using Constraint Programming

I am working on a graph problem and want to find some link-disjoint paths between given node pairs. I was wondering if there is an efficient way to achieve this in CP. I checked OR-Tools (routing and ...
6 votes
0 answers
74 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)$ ...
2 votes
0 answers
53 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 ...
3 votes
0 answers
187 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 ...
4 votes
1 answer
140 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 ...
  • 79
2 votes
1 answer
114 views

opposite of no_overlap constraint in docplex for CP

I am using python for CP solving. I would like to know if there is constraint that does the opposite of no_overlap. This will be like overlap(interval, arr, n) interval - single interval variable arr -...
5 votes
1 answer
88 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 ...
  • 159
7 votes
4 answers
858 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....
  • 533
2 votes
1 answer
459 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 ...
  • 129
4 votes
2 answers
576 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.)...
  • 746
7 votes
2 answers
213 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 ...
  • 171
1 vote
1 answer
319 views

Custom lazy callback constraints using Google OR-Tools linear solver?

Is it possible to implement custom lazy callback constraints using OR-Tool's base linear solver? Through Google's docs, I've seen their TSP examples using the constraint solver ...
3 votes
1 answer
70 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{...
  • 31
1 vote
0 answers
63 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
2 votes
1 answer
102 views

Adding a variable makes the model unsatisfiable in MiniZinc

I have the following model. ...
  • 225
0 votes
0 answers
194 views

OR-Tools addElement constraint

I am just not able to grasp how can I use the addElement constraint of OR-Tools. I am trying to model the following constraint written in MiniZinc: ...
  • 119
2 votes
1 answer
63 views

How to model a cumulative resource constraint with same family condition?

Assume that we have 3 tasks to schedule : $x_{a1}, x_{a2}, x_{b3}$. They all use the same cumulative resource : $r_1$. Each activity increases $r_1$ by $1$ at it starts time and decreases $r_1$ by $1$ ...
2 votes
1 answer
123 views

Scheduling when task duration longer than working interval

I'm trying to modify the job shop example for CP-SAT solver. (https://developers.google.com/optimization/scheduling/job_shop) I'm limited to 8 hours working day, So I defined a list of NewIntervalVar()...
2 votes
1 answer
358 views

Set value based on if other variable is in specific range

I have the following problem. number_of_machines is controlled by other constraints. I need to set line variable to specific value based on "range" ...
2 votes
1 answer
46 views

ILOG CPOptimizer soft constraints (multiple solves reusing searched space)

I'm trying to feed information retrieved from my neural network to my CP model to help narrow down the search on big instances of my problem. However, I also want to remove the additional imposed ...
  • 121
3 votes
0 answers
98 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, \\& ...
8 votes
2 answers
482 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 vote
1 answer
100 views

Dual of quadratic program with linear objective

Let $c$ and $k$ be element-wise positive $n\times 1$ vectors and let $A$ be a element-wise positive and positive-definite matrix. Consider the optimization problem \begin{align} \max_{p\in\mathbb{R}^n}...
1 vote
1 answer
67 views

Print Intermediate Solutions of Scheduling Problem and tackling FLAGS in jupyter notebook

I tried this code and it goes on and I'm clueless when it'll end so I manually interrupt it. Is there any way we can see intermediate solutions that are feasible solutions and can we limit time or ...
2 votes
0 answers
118 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:/...
4 votes
1 answer
136 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$...
  • 43
2 votes
0 answers
79 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
3 votes
2 answers
187 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 ...
5 votes
1 answer
325 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 ...
5 votes
1 answer
269 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 ...
-4 votes
1 answer
172 views

Multiple If else constraints in Mixed integer programming

How to formulate the following as constraints in MILP? a[0][0] = y, if x[0]= 0, a[0][0] = 0, if x[0] != 0, . . . . a[i][j] = b[i][j-1] + y, if x[j]=i, a[i][j] = a[i][j-1], if x[j] != i, ... . . . b[0]...
  • 125
2 votes
1 answer
168 views

OR-Tools, How to avoid dividing by zero

Problem: There is an order to fabricate some products of total number, let's say 200 (all products are the same). We have some number of factories, let's say 5. Every factory has different number of ...
5 votes
4 answers
634 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 ...
  • 61
4 votes
1 answer
425 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 ...
4 votes
2 answers
655 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 ...
2 votes
2 answers
113 views

Scheduling: Tasks changing the state of the executing machine

I have a scheduling problem in which machines consume their battery when executing tasks and charge their battery when not executing tasks. A single task has to be executed in one go (no recharging ...
  • 123
0 votes
1 answer
58 views

What is a good approach to deciding which jobs (from a list of HPC jobs) should be ran locally vs. on the cloud given time & cost constraints?

Cloud computing has transformed the landscape of compute operations. Of course, there are still many labs/businesses with local, large-scale compute clusters. For those businesses who keep the ...
  • 9
3 votes
2 answers
239 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. ...