# Questions tagged [integer-programming]

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

16 questions
Filter by
Sorted by
Tagged with
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.
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. ...
537 views

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.
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 ...
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 ...
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?
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 (...
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 \\ & ... 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? 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 ... 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 ... 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 ... 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? 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 ... 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$ (...
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 ...