Skip to main content
13 votes
Accepted

Are valid inequalities worth the effort given modern solvers?

It is, at least sometimes, still very useful. I have a short note (link) on a problem in quay crane scheduling in which adding a single - rather uninspired - family of valid inequalities greatly ...
Alberto Santini's user avatar
12 votes

Valid Inequality Example (Wolsey Example 9.3)

As @Kuifje suggested, an upper bound $x_i \le 1$ was mistakenly omitted. This omission was noted in this errata sheet, and it was corrected in the second edition of the book.
RobPratt's user avatar
  • 32.7k
10 votes
Accepted

Algorithm for simplifying a set of linear inequalities

What I'm about to suggest is less sophisticated than (and presumably less efficient than) the presolvers Mark L. Stone mentions, but would be relatively easy to implement (assuming you have an LP ...
prubin's user avatar
  • 39.6k
10 votes

Are valid inequalities worth the effort given modern solvers?

In my experience, it's rarely, but sometimes still, worth doing. There is no general answer however, as it's very model-specific (and sometimes even instance-specific). The only way to know for sure ...
Simon's user avatar
  • 1,142
10 votes
Accepted

State-of-the-art algorithms for solving linear programs

The simple answer is that for large scale problems (1m+ rows and columns) we would use interior point instead of dual simplex. The main challenge is not really the solving algorithm, since interior ...
Nikos Kazazakis's user avatar
9 votes
Accepted

How to relate dual values of valid inequality to the dual values of the original problem?

For simplicity, I will replace $\sum_i \beta_{i,j}$, $ \sum_i f_{i,j}$, and $\alpha_j$ by $x$, $y$, and $z$, respectively. assume that $x$, $y$, and $z$ are defined to be non-negative. assume that $x$...
Kevin Dalmeijer's user avatar
8 votes

No-good cuts for general integer variables

Here's one way, assuming $L_i \le x_i \le U_i$. Introduce binary variables $y_i$ and $z_i$, with linear constraints \begin{align} \sum_i (y_i+z_i) &\ge 1 \tag1\\ y_i + z_i &\le 1 &\text{...
RobPratt's user avatar
  • 32.7k
7 votes

Are valid inequalities worth the effort given modern solvers?

I've seen rather encouraging results using symmetry-breaking constraints, but most valid inequalities were useless (no effect on solving time or, worse, degradation thereof…), both with CPLEX and ...
dourouc05's user avatar
  • 998
7 votes
Accepted

No-good cuts for general integer variables

This is what I have been using. Assume $\color{darkred}x_i \in \{\color{darkblue}L_i,\dots,\color{darkblue}U_i\}$ and we want: $$ \sum_i |\color{darkred}x_i-\color{darkblue}x_i^*| \ge 1$$ or $$\begin{...
Erwin Kalvelagen's user avatar
6 votes

Algorithm for simplifying a set of linear inequalities

It sounds like you want something along the lines of a (partial) presolve, which most commercial solvers implement. For example, Gurobi has a presolve accessible from the Python interface which should ...
Mark L. Stone's user avatar
6 votes

No-good cuts for general integer variables

If you are willing to entertain an element of risk, and assuming that the feasible region is bounded, you might get away with a single new binary variable $z$. Assume that the feasible region $X$ is ...
prubin's user avatar
  • 39.6k
6 votes

Is the "reverse search" algorithm of David Avis the state-of-the-art method for finding discrete solutions to a system of linear inequalities?

There are many algorithms suggested for converting the "external" representation of a polyhedron (i.e., the set of solutions to a finite set of linear inequalities) into an "internal" one (i.e., a ...
Marco Lübbecke's user avatar
5 votes
Accepted

Guidelines for adding user cuts to models

Performance-wise, there are two main classes of cuts: (i) normal cuts, and (ii) global or "deep" cuts (definitions may vary between fields, this is what we use in deterministic global optimisation). ...
Nikos Kazazakis's user avatar
5 votes

Is the "reverse search" algorithm of David Avis the state-of-the-art method for finding discrete solutions to a system of linear inequalities?

As far as I can tell from the information I could on the "Reverse Search" algorithm, it is a technique that helps to enumerate combinatorial structures. In particular the paper you mention in a ...
Paul Bouman's user avatar
  • 2,100
5 votes

Is the "reverse search" algorithm of David Avis the state-of-the-art method for finding discrete solutions to a system of linear inequalities?

I am not familiar with the "reverse search" algorithm. For solving systems of linear inequalities in practice, algorithms for integer programming or constraint programming are probably most ...
Kevin Dalmeijer's user avatar
5 votes
Accepted

Valid Inequalities and Strong Inequalities

Usually in the context of LP/MIP you make statements about the convex hull of the mixed-integer set that you defined $P = \text{conv}(\left\{x \in \mathbb{R}^{n} : A x \leq b, x_{j} \in \mathbb{Z} \...
JakobS's user avatar
  • 2,767
4 votes

Valid Inequalities and Strong Inequalities

What exactly does "valid inequality" mean? Valid Inequalities are constraints that reduce your feasible space without removing integer solutions. In other words, Valid Inequalities approximate your ...
Alexandre Frias's user avatar
4 votes

Cover cuts for knapsack constraint with integer variables

Consider the integer knapsack set as: $$ K_{I} = \{ x \in Z^{N}_{+} : ax \leq b, x \leq u\} $$ Let $C \subseteq N$ be a cover if $\lambda = \sum_{i \in C} u_ia_i − b \gt 0$ and consider the ...
A.Omidi's user avatar
  • 8,960
3 votes

Separating violated cover inequalities

A partial answer to part (ii) of your question (this was too long for a comment so I'm including it as an answer). Note that the following assumes a minimal cover. The sequence independent lifting ...
tc1729's user avatar
  • 131
3 votes
Accepted

Separating violated cover inequalities

As a heuristic for finding a minimal violated cover inequality, you can solve your min-knapsack problem to find a cover $C$. Then, you may note that all objective function coefficients of the ...
Sune's user avatar
  • 6,647
3 votes

State-of-the-art algorithms for solving linear programs

You are right that the dual simplex (and to some degree the primal simplex) are still very much state-of-the-art ways to solve LPs. The last 3 decades saw significant improvements on these algorithms ...
Philipp Christophel's user avatar
3 votes

Exploiting ordering to removing infeasible solutions in MILP

Depending on the solver used, you may be able to prioritize the $x$ variables so that variables with higher indices are branched on before variables with lower indices (and elements of $x$ are ...
prubin's user avatar
  • 39.6k
3 votes

How to get all the facet inequalities from a set of valid inequalities?

I believe the answer to your question is principally "no." You mention these implementations, and there are some more, like porta or polymake, but in principle, this is an enormously ...
Marco Lübbecke's user avatar
2 votes

Algorithm for simplifying a set of linear inequalities

Sometimes it already helps to know the name of a problem. From a more theoretical point of view, i believe that there is a community working on your problem. I know the problem you describe under the ...
ckrk's user avatar
  • 121
2 votes

Algorithm for simplifying a set of linear inequalities

I have some experience with theoretical work around large systems of inequalities, and I found these packages very useful: lrslib - computational geometry package, in exact arithmetics, created by ...
Konstantin's user avatar
2 votes

Cover cuts for knapsack constraint with integer variables

Sure. Another way of doing this is by extending the number of items. Suffices to create $\lfloor \frac{b}{a_i} \rfloor$ dummy items to each item $i \in N$. Thus, we would have the new items set $N^{'} ...
Matheus Diógenes Andrade's user avatar
2 votes
Accepted

Proving the Validity of a Given Inequality Involving Ratios of $p$ and $q$

Maybe the definition of KL divergence is enough? If we eliminate the constraint that $q + p < 1$, notice that nothing changes in your inequality if I exchange $q$ and $1-q$. \begin{align} \left(\...
Uomond's user avatar
  • 86
2 votes

Finding a maximum violated infeasible subset

Here's where I think you are heading: \begin{align} &\max_{z\in\{0,1\}^N} \left[\sum_{i\in N} \bar{x}_i z_i - \max_{y\in\{0,1\}^N} \left(\sum_{i\in N} y_i: \sum_{i\in N} a_i y_i \le b \land \...
RobPratt's user avatar
  • 32.7k
1 vote

down lifting of variable coefficients for cover inequalities

Generally, the purpose of lifting is to obtain a strong inequality in a higher dimensional space than the original inequality. A cover inequality is only in very rare cases a facet defining inequality ...
Sune's user avatar
  • 6,647

Only top scored, non community-wiki answers of a minimum length are eligible