Questions tagged [integer-programming]
For questions about mathematical optimization problems involving binary or general integer variables.
344
questions
31
votes
3
answers
18k
views
In an integer program, how I can force a binary variable to equal 1 if some condition holds?
Suppose we have a binary or continuous variable $x$, a binary variable $y$, and a constant $b$, and we want to enforce a relationship like
If $x \gtreqless b$, then $y = 1$.
How can we write this ...
- 13.1k
29
votes
3
answers
1k
views
Feeding known lower bounds to solvers
Given an optimization problem that aims at minimizing some objective function, a lower bound that is valid for all feasible solutions, and your solver of choice:
For what theoretical and/or practical ...
- 1,006
29
votes
3
answers
7k
views
What is the difference between integer programming and constraint programming?
At first glance both approaches appear to be very similar.
What are the major differences between integer programming and constraint programming?
- 2,013
20
votes
1
answer
2k
views
What's the difference between Lagrangian relaxation and Lagrangian decomposition?
What is the difference between Lagrangian relaxation and Lagrangian decomposition? Are they the same thing?
- 13.1k
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 ...
- 193
19
votes
1
answer
466
views
Combinatorial Optimization: Metaheuristics, CP, IP -- "versus" or "and"?
"Recently" someone asked on Twitter whether "people still use genetic algorithms for integer programs". The "majority answer", i.e., 1 out of 1, was: "Yes" .
So,...
- 1,006
18
votes
3
answers
1k
views
Variable fixing based on a good feasible solution
Suppose you have a combinatorial optimization problem that is formulated as a mixed integer linear program (minimization). The problem size is denoted $n$ and the expected $n$ is around $100$. The ...
- 2,140
18
votes
3
answers
6k
views
Can an integer optimization problem be convex?
I'm trying to wrap my head around an apparent paradox that I've come across while trying to learn more about optimization algorithms:
On one hand several sources state that convex optimization is ...
- 2,129
17
votes
1
answer
2k
views
Duality in mixed integer linear programs
I know that the standard duality theory for the linear programming problem does not hold for mixed integer linear programming problems. I was wondering why an integer program does not have a dual ...
- 2,140
17
votes
1
answer
348
views
Family of hard instances for Gomory's cutting plane algorithm
Is there a variant of integer programs for which Gomory's cutting plane algorithm demonstrably takes a superpolynomial number of iterations?
- 2,705
16
votes
7
answers
2k
views
Does there exist an aggregation of videos on optimization?
Is there a website or otherwise maintained list of talks regarding mathematical optimization? This would be a big help for the community it seems. I'm most interested in those relating to integer ...
- 161
16
votes
2
answers
2k
views
Divisibility constraints in integer programming
In the study of a certain pure mathematical problem (related to infinite-dimensional Lie algebras) I found myself in a situation where it would be very desirable to be able to solve an integer ...
- 263
15
votes
3
answers
1k
views
How does the search space affect the speed of an ILP solver?
Let us suppose we have an optimization problem which we have modeled as an ILP. Suppose we solve this problem using some set of constraints which restricts the search space. Let us suppose we model ...
- 897
15
votes
1
answer
1k
views
What is quadratization?
In the context of discrete optimization, what exactly does it mean to "quadratize" a function?
The term seems to be used mainly by operations researchers, in my experience.
- 1,268
14
votes
4
answers
654
views
Does this $0-1$ integer program have any speciality?
Given matrix $A \in \{0,1\}^{m \times n}$ and vector $b \in (\mathbb{Z^+})^m$, where $\mathbb{Z^+}$ is the set of positive integers,
$$\begin{array}{ll} \text{maximize} & c^\top x\\ \text{subject ...
- 243
14
votes
2
answers
1k
views
How to choose between high number of binary variables or fewer number of integer (not only 0 and 1) variables in a IP formulation?
When I have to write the formulation of an IP, I usually have the choice between writing $i\times j$ binary variables with two indices such as $ x_{i,j} $ or, writing $j$ integer variables $x_i$.
Is ...
- 151
14
votes
3
answers
2k
views
A variant of the Multiple Traveling Salesman Problem
I am trying to find a reference (or a reformulation) of a variant of the multiple Traveling Salesman Problem, where multiple agents need to visit each vertex in a graph with minimal cost.
Most of the ...
- 143
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
13
votes
3
answers
1k
views
Allocating credit card points
I’m interested in the idea behind this in general, so I thought this would be the best place to post, though I have a practical and semi-urgent need of allocating the points on my credit card towards ...
- 233
13
votes
1
answer
258
views
Symmetry-breaking ILP constraints for square binary matrix
Setup
I have a binary $N \times N$ matrix. The objective is to minimize the number of ones in the matrix, subject to various constraints. This leads to symmetries by rotating 90 degrees and/or ...
- 1,122
12
votes
2
answers
3k
views
In an integer program, how can I “activate” a constraint only if a decision variable has a certain value?
Suppose we have the constraint
$$a_1x_1 + \cdots + a_nx_n \gtreqless b,$$
where $a_i$ and $b$ are constants and $x_i$ are decision variables. Suppose also that we want the constraint to hold if $y=1$ (...
- 13.1k
12
votes
2
answers
627
views
Expressing a chain of boolean ORs using ILP
How to express a chain of OR operations in an ILP in which each expression is a less than or equal constraint and the left hand side variable in all inequalities is always the same? All the variables ...
- 897
12
votes
2
answers
610
views
Expressing an implication as ILP where each implication term comprises a chain of boolean ORs
Consider an implication of the form $A \implies B$ where both $A, B$ comprises a chain of Boolean OR variables. For example, $(a_1 \lor a_2 \lor a_3) \implies (b_1 \lor b_2 \lor b_3)$. How can this ...
- 897
12
votes
1
answer
229
views
How to reduce recursion when using Gomory cutting planes to solve an integer program?
Consider the following simple integer program
$$\begin{array}{ll} \text{maximize} & 3 x_1 - x_2\\ \text{subject to}
& 3x_1 - x_2 \leqslant 3 \\ & -5x_1 - 4x_2 \leqslant -10 \\ & ...
- 223
12
votes
1
answer
158
views
Computational complexity to compute an IIS
How hard is it to compute an irreducible infeasible subset (IIS) for a linear program? What about an integer program (e.g., removing the integrality constraint on a single variable may be enough to ...
- 2,047
11
votes
5
answers
2k
views
How to compute all paths between two given nodes in a network?
In this post, Erwin Kalvelagen describes a method to compute all paths between two nodes in a given network, such that:
no arc is used more than once
a given path does not contain more than $M$ arcs
...
- 12.9k
11
votes
3
answers
1k
views
Are there explainability approaches in optimization?
In the machine learning community there is the big topic of explainability, where you want to make the solution of ML models explainable or derive explainable models.
This is also interesting for ...
- 3,635
11
votes
2
answers
494
views
Finding an optimal set without forbidden subsets
Given $n$ items, I want to select a set items $S\subseteq\{1,2,\dots,n\}$ that maximize profit. The profit of item $i\in\{1,2,\dots,n\}$ is given by $p_i$ and may be assumed to be non-negative.
...
- 6,063
11
votes
4
answers
379
views
Theoretical results on performance of branch-and-bound
Are there any theoretical results on the performance of branch-and-bound, even for a subset of instances of a particular discrete optimization problem?
As an example, does there exist a result of ...
- 579
11
votes
2
answers
294
views
Generalized Assignment Problem as the sub-problem
I was wondering what is the state-of-the-art for solving the Generalized Assignment Problem (GAP) and if there are special cases that are polynomially solvable?
Moreover, is there any usage of this ...
- 400
11
votes
1
answer
485
views
Expressing a chain of boolean ORs using ILP involving different variables
How can I express a chain of OR operations in an ILP, given that each operand is an inequality between two binary variables? I have asked a similar question here: Chain of Boolean ORs. In that ...
- 897
11
votes
2
answers
204
views
Is deciding the presence of mixed-integer points in the relative interior of a polyhedron in NP?
Given $P = \{x\in\mathbb R^n: Ax \leq b\}$, I want to decide if $(\mathbb Z^\ell \times \mathbb R^{n-\ell}) \cap \operatorname{relint}(P)$ is non-empty.
Is this problem in NP?
One idea is to check ...
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 ...
- 11.9k
11
votes
1
answer
158
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 ...
- 331
10
votes
6
answers
2k
views
Nonlinear integer (0/1) programming solver
I have the following optimisation problem.\begin{align}\max&\quad\sum_i\sum_j\sum_k x_{ji}y_{kj} \operatorname{cost}(i,k)\\\text{s.t.}&\quad\sum_j x_{ji}=1\quad\forall i\\&\quad\sum_k y_{...
- 109
10
votes
1
answer
3k
views
What are good reference books for introduction to operations research?
The reference books should cover the wide range of problem-solving techniques and methods.
10
votes
2
answers
1k
views
Decision Variable Value from a Set (Gurobi)
Is there a way to set a decision variable to take values from a set?
Example:
decision variable $x \in \{0,50,100\}$
So this variable can only take one of these three values and not more.
I have ...
- 1,193
10
votes
2
answers
549
views
How to maximize "contrast" between nodes on a graph?
I have an undirected graph such as the one shown below. I can make up to 3 choices about the color of each node. The edge weights are equal to the difference between the nodes, given by the "...
- 273
10
votes
1
answer
612
views
MIP: If integer variable $>0$ it should be equal to other integer variables $>0$
I have an MIP problem where $n$ different types of cars are delivering packages. Sometimes multiple types of cars are required to go to a single location. For example if car $1$ makes two deliveries ...
- 205
10
votes
1
answer
199
views
Finding the linear functions defining a polyhedron through integer data?
Let's say I have a bunch of linear functions $f_1,\cdots,f_n$ in $k$ variables; then $f_1,\cdots, f_n\le0$ defines a polyhedron $P$ in the $k$-dimensional space.
What I'm looking for is going the ...
- 103
10
votes
2
answers
395
views
Use integer/quadratic programming to maximize consecutive zeros in a binary array
A binary array $t = [t_1, t_2, t_3, t_4, t_5]$ with each element a binary integer variable taking values 0 or 1. You can think this vector as slots with 1 representing the slot being taken and 0 ...
- 201
9
votes
3
answers
979
views
No-good cuts for general integer variables
Question:
Suppose we have an integer program $\min\{c^\top{x}\mid{Ax\leq{b}},x\in\mathbb{Z}_+^n\}$, and suppose that $x^*$ is a feasible solution for this IP (or even that $x^*$ is an extreme point of ...
- 2,047
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 ...
- 325
9
votes
2
answers
526
views
Mixed-Integer Linear Programming With Free Variables
In the classic Mixed-Integer Linear Programming (MILP), the variables are fixed to be either integer or real. I am interested in the following MILP variant, where only one thing different from the ...
- 173
9
votes
2
answers
1k
views
Gurobi finishes with 'infeasible' although optimal solution exists
I am using Gurobi (in Python through gurobipy) to solve an IP on tournament graphs.
I am searching for a non-zero minimal integer weighting such that for every vertex the sum of weights put on the ...
- 153
9
votes
1
answer
489
views
How to get bounds on ILP optimal solution quality
Often, ILP formulations are just too complicated to solve optimally in reasonable time. In those cases, you can still run a solver for some fixed time and simply take the best solution that the solver ...
- 1,482
9
votes
1
answer
592
views
TSP problem: traveller does not visit all nodes - Google OR-tools
Context:
I am dealing with a kind of scheduling problem, in which I have a set of tasks and machines. All tasks must be assigned to machines (not necessary all of them). In addition to that, I must ...
- 1,133
9
votes
1
answer
273
views
Should I factor in time as a parameter or a variable in a scheduling problem with MILP?
I am trying to formulate a problem that will spit out an optimal schedule for my tasks to be completed. To keep the information confidential, I will refer to my tasks as papers that need to be written....
- 91
9
votes
1
answer
166
views
Equivalence of formulations
I have a simple model such as:
\begin{align}\max&\quad z=X_1+X_2+X_3+X_4\\\text{s.t.}&\quad y_1+y_2+y_3+y_4=2\\&\quad X_1 \leq y_1\\&\quad X_2 \leq y_1+y_2\\&\quad X_3 \leq y_2+...
- 852
9
votes
1
answer
240
views
Static stochastic knapsack problem: unbounded version
In the static stochastic knapsack problem (SSKP) the weights $w_i$ of the items are distributed according to a probability distribution. Each item $i \in I$ can be selected at most once.
So, ...
- 937