Questions tagged [integer-programming]
For questions about mathematical optimization problems involving binary or general integer variables.
339
questions
1
vote
1
answer
87
views
Benchmark problems for Benders Decomposition
we are implementing a scheduling model using Benders Decomposition. Does someone know of any existing implementation of Benders or any repositories that contain continuous or integer problems solved ...
- 702
0
votes
2
answers
60
views
What is the best way to constrain a binary matrix so that at most one row has positive values?
I have a binary variable $x_{i,j}$ for $i\in\{1,\ldots,m\}$ and $j\in\{1,\ldots,n\}$ and the constraint is to have at most one row that has ones. I wrote this as: $$x_{i,j}+x_{i',j'}\leqslant1,\forall ...
- 622
1
vote
1
answer
108
views
How to linearize the following constraints
Given the following two expressions:
$ x - \frac{1}{T}\sum_{i} y_{i}$
$ x - \frac{1}{Q}\sum_{i} \beta_{i} y_{i}$
where $x \in \mathbb{Z}_{+}$, $y \in \mathbb{R}_{+}$, and $T$, $Q$ and $\beta_{i}$ ...
- 1,885
0
votes
0
answers
33
views
Stationarity conditions for IPs
Let's consider the following (MQ)IP:
$\min x^T Q x$
s.t. $g(x) \geqslant 0$
$x_i \in \mathbb{Z}$ $i \in I$
By ignoring the integrality constraints we end up with the QP:
$\min x^T Q x$
s.t. $g(x) \...
- 1,198
1
vote
0
answers
262
views
Deriving a valid inequality
Given a set of facilities $I$ and days $J$, each facility $i \in I$ has a capacity of $C_i$, and a set of days $J$ where in each day $j \in J$ there's a total demand of $q_j$ that can be satisfied by ...
- 111
0
votes
2
answers
215
views
How to identify constraints that make problem not solvable in polynomial time?
I am reading this paper, available for free viewing, which contains an example of job shop scheduling, shown below.
The details of the variable definitions, etc., can be found in the paper, but it's ...
- 30.3k
1
vote
0
answers
83
views
Optimize cherry picking runs
I am trying to optimize a cherry picking procedure on 96-well microplates. The plates are 12X8 (12 columns, 8 rows). We pass a command file that has many lines like this to a robot:
...
- 111
1
vote
2
answers
149
views
Linearizing if else conditions in ILP
We are given three binary indicator variables $X_{ij}, Y_{jk}$ and $Z_{jl}$. Write linear constraints such that,
a) if $X_{ij}$ is equal to 1, then for that $j$ when $X_{ij} = 1$, exactly one $Y_{jk} =...
- 8,382
1
vote
1
answer
100
views
Constraints to avoid disjointed solutions in a MIP
Given an directed graph $G= (N,E)$, where $N$ is the set of nodes and $E$ is the set of all edges, each associated with a direction. $G$ is a connected graph but not necessarily a complete graph.
A ...
CommunityBot
- 1
3
votes
2
answers
228
views
Binary Integer Programming Problem - Enforce Zeros on Certain Groups
I'm working on a binary integer programming problem using pulp. I have a vector X = [x_1, x_2, x_3, . . . , x_n]. I have enforced a number of simple constraints. I ...
- 1,198
-1
votes
2
answers
181
views
How do I optimize this problem where the constraints and objective are variable?
Problem Definition:
Pa = Constant
Pb = Constant
Vmax_a = Constant
Vmax_b = constant
Objective Function:
...
- 5,341
7
votes
3
answers
730
views
Binary logical constraint dependent on indices
I don't know if I can ask this here, but I've been pulling my hair out trying to think of how to represent this in constraints.
I have two sets of binary variables: $X_t$ and $Y_{it}$. So, I want to ...
- 5,341
2
votes
0
answers
30
views
Maximizing value of nodes visited in fixed time
Consider the following three problems. The first is intended to be a simplification of the second that might be amenable to solution methods the second is not amenable to.
First problem: Assume we ...
3
votes
1
answer
200
views
Graph coloring problem redundant constraints
Say the edges of a 4 nodes graph are 0 1, 1 2 and 1 3.
The solution to the colouring problem ...
- 3,396
1
vote
2
answers
138
views
Efficient ways to do pairwise/multiplicative variables in integer linear programming on PuLP / Python
I'm trying to formulate an LP that is in essence a variant of the sudoku problem, and I've repurposed the code from https://coin-or.github.io/pulp/CaseStudies/a_sudoku_problem.html.
The differences ...
- 3,328
0
votes
2
answers
54
views
ILP constraint conditional on a value of a variable
If $X_{ijklm}$ are Boolean Variables, where $i,j,k,l,m$ range from $1$ to $n$, then write an ILP constraint to ensure that for each value of $k$, either all the $jth$ variables are set to $0$ or all ...
- 3,328
1
vote
1
answer
72
views
Setting constant values in constraints depending on actual values of variables
We have a set of constraints in an ILP of the following form :
$ \gamma (X_{11} + X_{12} + X_{13}) \leq C_1$ where $X_{ij} \in \{0,1\}$ and the value of $\gamma$ is going to depend on the actual value ...
- 30.3k
19
votes
6
answers
7k
views
When to use indicator constraints versus big-M approaches in solving (mixed-)integer programs
Various optimization modeling languages and solvers allow for both indicator constraints (see for example here, here and here) and traditional binary variable and big-M approaches can be used to model ...
- 21
2
votes
0
answers
74
views
When do two integer linear programs yield the same solution?
This question is cross-posted from math stack exchange
An illustrative example
Consider an integer linear program $\min -2x_1 + x_2$ subject to $x_1 - x_2 \leq 3$ and $x_1 + x_2 \leq 10$ and integer $...
- 121
-1
votes
1
answer
53
views
does mTSP/CVRP always minimize number of vehicles used?
Context:
I was working on some VRP solvers and realized that tractability deproved when I added Fixed Cost for each vehicle (in an attempt to reduce number of vehicles used).
Questions:
1-
Due to the ...
- 63
2
votes
1
answer
127
views
Conditional constraints in MILPs
I want to understand how to represent iff constraints in MILPs. For example, I want to represent the following as the constraints of a MILP
$$ c = \begin{cases} 1 &\text{if } d \geq e \\ 0 & \...
- 12.9k
0
votes
2
answers
102
views
Assignment problem with multiple precedence constraints
Objective and short problem description
The objective is to load as many passenger vehicles as possible on an auto-train. The train consists of multiple wagons with two levels each. The wagons are ...
1
vote
1
answer
110
views
Anytime solver for integer linear program
One approach to solving NP-hard problems is to use an anytime algorithm: an algorithnm that starts with a heuristic solution and keeps improving it towards the optimum, and when it is stopped, it ...
- 11.9k
0
votes
1
answer
81
views
Simulating an integer quadratic knapsack problem
I am trying to simulate the following quadratic integer program using $\textsf{cvxpy}$:
$$ \begin{array}{ll} \underset {x_1, \dots, x_K} {\text{minimize}} & \displaystyle\sum\limits_{i=1}^{K}\frac{...
- 1,885
3
votes
2
answers
386
views
How to model a binary variable?
I am trying to find a constraint for the following relationship, but am failing a bit at it right now. I want to find a linear constraint that does the following. The binary variable $switch_{ot}$ is ...
1
vote
1
answer
113
views
Rational LP, its Rational solution and a minimum precision
Suppose we have an LP with rational coefficients.
To my knowledge, this implies that the optimal solution to that LP is also rational. In other words, every variable may be written as:
$$x_{i}^{\star} ...
- 1,347
0
votes
0
answers
56
views
How do I solve this non-linear optimisation problem based on simulations?
I have an optimisation problem that is essentially a knapsack problem with a non-linear objective.
I have an input dataframe that contains a row for each item, each item has columns defining its mean ...
- 31
0
votes
1
answer
226
views
How to formulate an MIP so that a binary variable is 0 or 1 depending on whether another variable is nonzero?
I have a binary indicator variable $i \in \{ 0, 1 \}$ and an integer variable $c \in \mathbb{Z}$.
I am trying to come up with a formulation in which $i = 0$ if $c = 0$ and $i = 1$ if $c \neq 0$.
...
- 30.3k
3
votes
0
answers
104
views
Number of Subtour Elimination Constraints for ATSP (DFJ Formulation)
In the DFJ formulation of the symmetric TSP, the subtour elimination constraints are typically written as:
$$\sum_{\{i,j\} \in E: \ i \in S, j \notin S} x_{ij} \geq 2, \qquad \forall S \subset V, \; 3 ...
- 30.3k
3
votes
2
answers
100
views
How to model if-then?
$i$ is a set $1$ to $n$.
$j$ is a set $1$ to $m$.
$j$ and $k$ are from the same set such that $j\neq k$.
$c_{ij}$ is a parameter.
$x_{ij}$ is a binary variable.
How to model: If
$$c_{ij}\cdot x_{ij} \...
CommunityBot
- 1
2
votes
2
answers
73
views
How to model this?
$i$ is a set $1$ to $n$.
$j$ is a set $1$ to $m$.
$j$ and $k$ are from the same set such that $j\neq k$.
$c_{ij}$ is a parameter.
$x_{ij}$ and $y_{j}$ are binary variables.
How to model: If
$$c_{ij}\...
CommunityBot
- 1
0
votes
4
answers
117
views
What is the greatest possible number of tables that could be occupied by just 1 person?
A restaurant has a total of 16 tables, each of which can seat a maximum of 4 people. If 50 people were sitting at the tables in the restaurant, with no tables empty, what is the greatest possible ...
- 30.3k
2
votes
1
answer
127
views
Conditional constraint for binary
Could you please check where I might be wrong?
Task is:
If $z=1$, then either $x=1$ or $y=1$
My approach:
If $z=1$, then $x+y=1$
$\implies x+y\le1$
$\implies x+y\ge1$
If $z=0$, then $x+y\ge0 - M\cdot(...
- 1,885
0
votes
3
answers
46
views
Maintaining Pair Preference that is neutral at outset
I am trying to model a job-shop scenario where - given a certain number of workers (W) and parts (P) such that P>W - each worker spends each shift (k) working on a specific part. Due to reasons of ...
- 3,328
3
votes
2
answers
368
views
How to model this binary constraint?
I have an optimization problem that has a variable in the matrix form. The variable is a binary matrix. It has size $M \times N = 10 \times 50$ where $M$ is the number of machines and $N$ is the ...
- 107
3
votes
3
answers
248
views
Equivalence between constraints in ILP
Let's have binary variables $x$ and $y$. I'd like to define a helping binary variable $z$ such that
$$ z = 1 \; \;\; \mathrm{iff} \; \; \; x + y = 2.$$
If I wanted to express the equivalence between ...
- 1,036
1
vote
1
answer
66
views
how to minimize the distance to the final points with incomplete information?
Suppose we have a transportation problem similar to pickup and delivery problems. So, we have a set of drivers and a set of passengers. each passenger has predefined origins and destinations. I'd ...
- 177
11
votes
1
answer
209
views
Automatic detection of SOS variables and constraints
We've been working on a new feature for Octeract Engine, namely to automatically extract SOS structure from a model and then exploit it.
While the literature is quite rich on what to do with SOS once ...
- 184
2
votes
3
answers
156
views
Is there any "not bad" algorithm that can solve the minimax problem in 0/1 integer programming?
As title, recently I got a minimax problem, after formalizing, the model is like this.
$$\text{minimise } \max_{k \in K} \sum_{i \in I} b_{i,k} \cdot f_i$$
such that: $$ \forall i \in I,\, \sum_{k \in ...
- 37.8k
1
vote
2
answers
74
views
How to tackle online scheduling problems?
In scheduling problems, one usually has different options as objective functions (makespan, tardiness, etc). However, for any such type of scheduling problem one can consider an online version of it ...
- 4,697
1
vote
2
answers
74
views
Fixing binary variables in an Binary Integer Program
I have a Binary Integer Program with two binary decision variables and additionally have an expected solution. At the time of execution of this program I expect the parameters to change slightly. I am ...
- 8,382
1
vote
1
answer
128
views
Solver for Flexible Job Shop Scheduling Problem
I have a FJSSP that I would like to solve. However, the jobs in this problem have deadlines and in addition there are setup times between two jobs. Because of this, my objective function is not just ...
- 37.8k
1
vote
1
answer
243
views
multi-commodity flow vs integer programming
A theater center needs to select which shows to broadcast in one of its rooms for a given day. There are three options available: short films that last about 1 hour, movies that last about 2 hours, ...
- 113
9
votes
3
answers
2k
views
Open source MILP solver for quick “good enough” solution
I have a problem that I have already posted elsewhere in OR.stack, but the question is focused around a large binary MILP (about 1 million decision variables). Ultimately, I am more time constrained ...
- 2,588
0
votes
1
answer
64
views
Maximization problem with preferences on variables
Consider the following trivial, theoretical model:
$$
\max x+2y+3z \qquad s.t.
$$
$$
x \leq b_x
$$
$$
y \leq b_y
$$
$$
z \leq b_z
$$
$$
x+y+z = 1
$$
$$
x,y,z \in \{0, 1\}
$$
and $b_x$, $b_y$ and $b_z$ ...
- 3,328
2
votes
1
answer
145
views
Reduced cost fixing for binary programs
Consider the binary program
$$ \min_{ x \in \{0,1\}^N } \left\{ c^T x \mid Ax \leq b \right\}$$
where $A$ and $b$ are real matrices with appropriate dimensions. I am interested in solving large binary ...
- 3,046
0
votes
0
answers
56
views
Gamma uncertainty in the RHS of a constraint
I am new to the concept of robust optimization.I am trying to formulate the robust variation of a Binary Integer Program. Suppose we have a constraint of the form $\sum{x_{i,j}} \geq b_j$ for $ i \in ...
- 1,268
1
vote
2
answers
235
views
Google CP-SAT Infeasible ILP for Large Problem Area
I am trying to generate a shortest path between source and sink in a square grid of cells. I am using the Google CP-SAT solver ...
- 2,588
1
vote
1
answer
151
views
Modeling Multi-Agent Collision in Google CP-SAT Solver
I would like to implement a solution for Multi-Agent Pathfinding Problem using Google's CP-SAT Solver.
How do I implement the constraint that prohibits 2 or more agents from occupying the same cell at ...
- 2,588
2
votes
0
answers
35
views
Recoverable Robustness for an optimization problem
I am relatively new to the concept of recoverable robustness. I am researching the robust version of an optimization problem. I currently have methods to address the problem with perfect knowledge. ...
- 392