Questions tagged [integer-programming]
For questions about mathematical optimization problems involving binary or general integer variables.
20
questions with no upvoted or accepted answers
12
votes
0answers
161 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&\...
9
votes
0answers
73 views
What to do with cuts (constraints) when a fixation is contrary to a RHS in a ILP / LP relaxation?
I am trying to understand an algorithm in a paper by Crévits et al. (2012)1 (see algorithm 2, the cuts I'm referring to are from the reduced costs). It uses a series of successive cuts on a linear ...
8
votes
0answers
87 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 ...
6
votes
0answers
114 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$ ...
5
votes
0answers
80 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 ...
5
votes
0answers
140 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$....
5
votes
0answers
77 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 ...
5
votes
0answers
78 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 ...
4
votes
0answers
63 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 ...
3
votes
0answers
58 views
Optimal Seat Allocation Problem
I have to do an operations research assignment based on optimal seat allocation. The problem goes something like this. There are 5 rooms in an office each with a separate seating capacity. We now have ...
3
votes
0answers
50 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
0answers
38 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 ...
3
votes
0answers
61 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 ...
3
votes
0answers
32 views
Linear functions in Lenstra's algorithm
I had asked this question at MathOverflow and was pointed here.
I'm working on implementing Lenstra's algorithm. At the bottom of p.5 (at "construct $n+1$ linear functions"), he says to ...
2
votes
0answers
66 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}_+$ ...
2
votes
0answers
99 views
How develop a branch and bound algorithm for integer programming with black box objective function?
The problem here described was taken from a university exercitation session.
A serial production line is made of $K$ workstations: one kind product is manufactured by this line and has to be processed ...
2
votes
0answers
93 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 ...
2
votes
0answers
144 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 ...
1
vote
0answers
26 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\...
1
vote
0answers
34 views
Interger programming using gray encoding
Could anyone suggest me a tool or library which takes an integer programming problem written in DOCPLEX or CVXPY as input and outputs the equivalent problem using Gray binary encoding? I am happy to ...
