Questions tagged [integer-programming]

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

Filter by
Sorted by
Tagged with
2
votes
1answer
189 views

What are good reference books for introduction to operations research? [closed]

The reference books should cover the wide range of problem-solving techniques and methods.
11
votes
2answers
401 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. ...
9
votes
1answer
537 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.
8
votes
0answers
59 views

Deciding the presence of mixed-integer points in the relative interior of a polyhedron

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 there an algorithm to do that? Is this ...
10
votes
1answer
60 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 ...
12
votes
0answers
61 views

Family of hard instances for Gomory's cutting plane algorithm

Is there a family of integer programs for which Gomory's cutting plane algorithm demonstrably takes superpolynomial number of iterations?
19
votes
3answers
169 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 optimal solutions, and your solver of choice: For what theoretical and/or practical (...
9
votes
1answer
64 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 \\ & ...
13
votes
1answer
68 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
votes
1answer
91 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, _my_ follow-up question is: With all ...
14
votes
4answers
230 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 ...
12
votes
1answer
132 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 ...
13
votes
1answer
123 views

What is the difference between integer programming and constraint programming?

At first glance both approaches appear to be very similar. So, I wondered where lie the major differences between integer programming and constraint programming?
8
votes
1answer
81 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 ...
7
votes
2answers
120 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 + ... + 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$ (...
14
votes
2answers
152 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 ...