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
30
votes
3answers
6k 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 ...
22
votes
3answers
3k 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?
18
votes
1answer
263 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, my follow-up question is: With all ...
18
votes
3answers
367 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 ...
18
votes
2answers
271 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 ...
14
votes
1answer
240 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 ...
11
votes
4answers
409 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 ...
11
votes
1answer
267 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 ...
10
votes
2answers
411 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 ...
10
votes
1answer
432 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 ...
10
votes
1answer
171 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, ...
10
votes
1answer
199 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 ...
9
votes
3answers
304 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 ...
9
votes
3answers
456 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 ...
9
votes
1answer
488 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 $...
9
votes
1answer
163 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{ ...
8
votes
3answers
259 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 ...
8
votes
1answer
423 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.
8
votes
2answers
155 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"), ...
8
votes
1answer
205 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
1answer
126 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
1answer
215 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 ...
8
votes
1answer
151 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. ...
7
votes
3answers
554 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, ...
7
votes
1answer
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
1answer
473 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
2answers
188 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 ...
7
votes
1answer
311 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 ...
7
votes
2answers
317 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 ...
7
votes
0answers
64 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 ...
6
votes
2answers
108 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 ...
6
votes
1answer
514 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 \\ ...
6
votes
0answers
114 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
0answers
118 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
0answers
241 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 ...
5
votes
3answers
189 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 ...
5
votes
2answers
356 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, ...
5
votes
1answer
612 views

Cumulative Constraint OR-Tools

I'm trying to solve an rcpsp model. I can't find documentation for the AddCumulative function of OR-Tools. How should this function be used? I want to write this ...
5
votes
2answers
230 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: $...
5
votes
1answer
497 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 ...
5
votes
1answer
154 views

Precedence constraints using binary variables - DOCPLEX

I would like to establish a precedence constraint to ensure the precedence relation of tasks. I have a set of tasks available, but required tasks are not always the same. It means, the tasks executed ...
5
votes
0answers
80 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+...
5
votes
0answers
52 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}...
5
votes
0answers
33 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. ...
4
votes
4answers
375 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 ...
4
votes
1answer
294 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
1answer
96 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 ...
4
votes
1answer
180 views

How exactly does OptionalIntervalVar work in OR-Tools?

I created OptionalIntervals for a number of tasks: ...
4
votes
1answer
104 views

Constraint programming in OPL: intervals covering time slots

I am trying to model the following: There is a shop open from xx AM to yy PM. In each 30 min time slot, there have to be demand[timeSlot] = x employees present. E.g. the shop is open from 08am to ...
4
votes
1answer
89 views

How to convert non-normal probabilistic constraints to deterministic ones for mathematical modelling?

I am working on a chance-constrained optimisation model that takes into account uncertainty. I am aware of how to convert constraints that are of a probabilistic nature into the equivalent ...