Operations Research Beta

Questions tagged [integer-programming]

Ask Question

For questions about mathematical optimization problems involving binary or general integer variables.

18 questions with no upvoted or accepted answers
Newest
Active
Bountied
Unanswered
Filter by
Sorted by
Tagged with
12
votes
0answers
150 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
69 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
81 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
109 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
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
73 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
77 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
46 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
36 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
59 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
29 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
64 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
95 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
84 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
133 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
33 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 ...
-4
votes
0answers
67 views

maximizing paid time off

A friend of mine is trying to optimize his use of paid time off using IP/BP and I thought maybe you would be able to help (see below). John Doe works only on business days and loves to travel in his ...