Questions tagged [integer-programming]
For questions about mathematical optimization problems involving binary or general integer variables.
45
questions with no upvoted or accepted answers
14
votes
1
answer
291
views
Integrality gap in bilevel binary linear programming problem
I have a bilevel max-min optimization problem over binary variables, with constraints expressed using linear inequalities. The inner (minimization) problem is
$$
\begin{alignat}2
\min\limits_x&\...
- 299
6
votes
0
answers
124
views
Characterization for total dual integrality
A problem I study reduces to whether the polyhedron $P=\{\mathbf{x}\mid A\mathbf{x}=\mathbf{1}, \mathbf{x}\geq0\}$ is integral ($A$ is a matrix with coefficients in $\{0,1\}$). I know that the ...
- 137
6
votes
0
answers
86
views
How to communicate number of integer combinations to a user
I'm working on a nifty little feature for our next release, i.e., to print the number of possible integer combinations left during branch and bound.
This is really handy for the user because they ...
- 11.9k
6
votes
0
answers
123
views
Help in solving resource allocation optimization problem
I've been pondering on this question for some work optimization, and I need some help in being directed to the right direction.
I have multiple customers that require an amount of $X$, $Y$ and $Z$ ...
- 61
5
votes
0
answers
88
views
Bounding the size of the dual solution
Given an primal optimization with bounded feasible set: $\max \{cx: Ax \leq b\}$.
The feasible region of the dual is $D = \{y:y^\top A = c^\top, y \geq 0\}$.
If the primal feasbile region is a ...
- 3,635
5
votes
0
answers
147
views
When is there at least an integral point in a polyhedron?
This problem comes from a problem of economics. Let $x\in [0,1]^n$. $\{x_1,x_2,\ldots,x_n\}$ is partitioned into ${S_1, S_2,\ldots,S_k}$ such that $\sum_{x_i\in S_j}x_i\leq 1$ for each $1\leq j\leq k$....
- 137
5
votes
0
answers
170
views
Are there any good models for min-max vehicle routing problem?
I am trying to model a min-max VRP problem with multiple delivery vehicles and I have come up with a model using branch and cut but I do not think it is strong enough as it takes lot of time to ...
- 253
4
votes
0
answers
71
views
Continue on "Is there a known MILP to schedule routes after routes are made"
I have made some progress on my previous question (Is there a known MILP to schedule routes after routes are made).
I have derived the sets of the problem, which are:
1) Itineraries of vehicle: $i \in ...
- 483
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 ...
- 31
3
votes
0
answers
87
views
Minimize total cost to buy unique products over timespan
I am looking for some guidance on how to better state my problem formally and practically (e.g., relevant Python libraries).
Let's assume I have a set of $X$ unique products to buy. I have $Y$ days in ...
- 31
3
votes
0
answers
98
views
Polynomial Time Solution For a Mixed-Integer Linear Programming Specific Case
Consider the following mixed-integer linear programming (MILP):
\begin{equation*}
\begin{array}{ll@{}ll}
\text{maximize} & 1 & \\
\text{subject to}& x_{i} \geq 0, &i=1 ,\dots, m\\
...
- 173
3
votes
0
answers
166
views
How to linearize a max min objective function?
Let us suppose that I have a $\max \min$ objective function that only depends on one set of variables:
$\underset{x}\max \underset{y}\min dy$
Associated with the linear set of constraints and right ...
- 583
3
votes
0
answers
81
views
Flexible Job Shop with Preemption
I'm trying to solve a flexible job shop problem variant that has precedence constraints on jobs along with a few other issues. We have a MIP formulation and also a simulated annealing algorithm to ...
3
votes
0
answers
87
views
How to find all covers and minimal covers?
Consider a constraint of type
$$c_1x_1+c_2x_2+\cdots+c_nx_n\leq C$$
with $x_i$ binary.
We call a cover a subset of the $n$ indices such that the sum of the corresponding coefficients is higher than ...
- 1,641
3
votes
0
answers
71
views
Theoretical aspect of using extended formulation
If I can show a polyhedron Y is an extended formulation of polyhedron X and every extreme point in Y is integral, does that automatically imply the projection of Y onto the variable space of X gives ...
- 31
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 ...
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
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
2
votes
0
answers
68
views
Multi Commodity VRP Time Windows Paper
I have been wondering is there any paper that who discuss multi commodity with four index/indices like this formulation below:
$$
\begin{gathered}
\sum_{k} \sum_{c} F_{j, j, c, k}=1 \quad \forall j \\
...
- 593
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
53
views
How to construct a restriction for a blending problem that has 2 inputs that are blended, and as result we get 2 outputs?
THE PROBLEM
A refinery has 10 million barrels of type A crude and 6 million barrels of
Type B crude oil. The refinery has 3 plants to produce Gasoline (it makes a profit
of 2 USD / barrel) and Naphtha ...
- 67
2
votes
0
answers
256
views
About combinatorial Benders Cuts
I am solving an OR scheduling problem where I assign the patient to (day,OR) tuple in Master Problem. Once the assignment is made, a subproblem can be solved for each (day,OR) tuple independently ...
- 331
2
votes
0
answers
80
views
What if anything do linear relaxations of "nearby" MILP nodes tell us about other MILP nodes
Assume we are given MILP where $y \in (\mathbb{R}^+)^n$, $x_1, x_2 \in \{0, 1\}$ are the integer variables. It is obvious that this problem when solved via branch and bound has a 2 deep b&b-tree.
...
- 3,975
2
votes
0
answers
122
views
Indicator function for integer variable with inequality constraint
I have $n$ integer variables $\vec{x}$ with the following integer programming problem.
$$
COST = \sum^{n-1}_{i = 0} a_i x_i + \sum^{n-1}_{j=0} b_j I(x_j > 0)
$$
Here, $a_i, b_j \in \mathbb{R}_+$ ...
- 251
2
votes
0
answers
119
views
Condition for an integer program and its linear relaxation to have the same value
Let $A$ be a $(0,1)$-matrix where no row or column is a zero vector, and consider the following optimization programs \begin{align}(1):\min&\quad y\cdot1\\\text{s.t.}&\quad yA\ge w\\&\quad ...
- 21
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
1
vote
0
answers
24
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
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. ...
- 111
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
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
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 ...
- 111
1
vote
0
answers
121
views
Assembly Line Balancing---(Minimizing Cycle Time)
A factory has a four workstations assembly line which produces a bluetooth speaker. This
production requires twelve assembly operations, respecting some precedence constraints. Table
4 indicates the ...
- 21
1
vote
0
answers
56
views
How to avoid complementarity constraints in continuous nonlinear program?
In my two-stage continuous NLP problem, I have a constraint in second stage:
$X_{g,k}$ = $X_{g,0} + a_{g} d_{g} $, if $X_{g,k} \in [X_g^u,X_g^l]$
$X_{g,k} = X_g^u$, if $X_{g,k} \geq X_g^u$
$X_{g,k} ...
1
vote
0
answers
82
views
Bipartite matching
If I have two matrix
$$A = \begin{bmatrix}
1 & 2 \\
2 & 3
\end{bmatrix} $$ and $$B = \begin{bmatrix}
3 & 4 \\
5 & 3
\end{bmatrix} $$
We have to make a matching between $A$ and $B$ ...
- 139
1
vote
0
answers
56
views
Product allocation to vendor according to their demand
Company X has 3 types of products and due to the limited availability of raw materials, the production of products are also limited.
They have partnered with Store A for them to sell their products. ...
- 29
1
vote
0
answers
60
views
Building blocks for unimodular matrices
I read Chapter 19.4 of Schrijver(1986) and get to know that every totally unimodular matrix can be produced by taking operations on network matrices and two certain matrices. I find that some paper ...
- 137
1
vote
0
answers
134
views
How can I set the solution of gurobi to be a multiple of 10 instead of all integers?
For example, the solution for gurobi has two solutions, as follows: [10,20,50,70] [55,79,30,80] I only want to output solutions that contain only multiples of 10. The sample example as follow:
...
- 57
1
vote
0
answers
48
views
Unifying constraint matrices in sparse situations
$\DeclareMathOperator\Set{Set}$
Let
$Set=\{x\in\mathbb Z^{n}:\exists y\in\mathbb Z^m\text{ satisfying } A[x,y]'\leq b\}$
where $A$ has $r=km$ rows and $k=O(1)$.
I am trying to write
$$
Set=\{x\in\...
- 11
1
vote
1
answer
109
views
ILP program to find a centrosymmetric Hadamard matrix
A question in mathoverflow asks if there exists a centrosymmetric Hadamard matrix of order 36.
An $n \times n$ matrix $A = (a_{i,j})$ is centrosymmetric if:
$$a_{i,j} = a_{n-i+1, n-j+1}, \space i=1,\...
- 393
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
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
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 ...
- 392
0
votes
0
answers
64
views
Decision whether to serve the current table now or skip it
Can the following problem be formulated as a LP/IP problem, where an agent (waiter) that has just arrived at a certain table has to decide whether to visit that table now, or skip the current table ...
- 9
0
votes
0
answers
199
views
Check VRP instance is feasibility
Beforehand, this is a very long thread, in case you want to know in advance, to see if this thread's interests match with yours, this thread concerns fast ways of determining whether a VRP instance is ...
- 1,208