Questions tagged [integer-programming]
For questions about mathematical optimization problems involving binary or general integer variables.
344
questions
1
vote
0
answers
20
views
Continuous optimization with a Euclidean TSP objective
I am trying to solve a problem of the form $$\min_{x_1,\dots,x_n} f(x_1,\dots,x_n)$$ subject to a constraint that $\mathrm{length}(\mathrm{TSP}(x_1,\dots,x_n))\leq c$, where $x_1,\dots,x_n$ are all ...
- 129
1
vote
1
answer
104
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 ...
- 1,885
-1
votes
2
answers
100
views
Need help with integer programming exercise
This is an exercise from Wolsey that I can't solve. Show how to go from Equivalence (1) to (2) and from Equivalence (2) to (3):
$$
\begin{align}
X &= \{ x \in \{0, 1\}^4~\mid~97x_1 + 32x_2 + ...
- 30.5k
4
votes
1
answer
306
views
Optimization problem with the Harmonic number
I have an optimization problem:
\begin{align*}
\text{ minimize } \sum_{i=1}^n H(x_i)
\\
\text{ subject to } Ax \geq b, x\geq 0, x\in \mathbb{Z}^n
\end{align*}
where $H(n)$ is the $n$-th Harmonic ...
- 30.5k
1
vote
0
answers
97
views
Applications of Knapsack and Cutting Stock in Pure Math
I'm giving a seminar to PhD students in pure math, and one of the things I'd like to do is show that more applied optimization can also make its way into pure Mathematics. As for classical problems, I'...
- 534
1
vote
1
answer
76
views
Maximizing sum of probabilities with variable distributions
Suppose $\\{X_i\\}$ are binary decision variables and $\\{A_j\\}$ are Skellam random variables with $(\mu_1, \mu_2) = (\sum_i b_{i} X_i, c_j)$. Here, $b_i, c_j \in \mathbb{R}^{\geq 0}$ are constants. ...
- 61
0
votes
2
answers
63
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
110
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,208
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.5k
1
vote
0
answers
84
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
151
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,450
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
231
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,208
-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,342
7
votes
3
answers
731
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,342
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
203
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
145
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,343
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,343
1
vote
1
answer
74
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.5k
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
54
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
129
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
103
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
114
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
115
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
57
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
250
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.5k
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.5k
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
118
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.5k
2
votes
1
answer
128
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,343
3
votes
2
answers
372
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
249
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,046
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
211
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
157
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.9k
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,673
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,450
1
vote
1
answer
134
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.9k
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,598
0
votes
1
answer
65
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,343