12
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 ...
- 2,073
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.
- 30.3k
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 ...
- 37.8k
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 ...
- 11.9k
9
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 ...
- 1,122
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$...
- 6,063
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{...
- 30.3k
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 ...
- 998
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 ...
- 13.1k
6
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{...
- 2,585
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 ...
- 37.8k
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 ...
- 5,909
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).
...
- 11.9k
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 ...
- 2,080
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 ...
- 6,063
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} \...
- 2,737
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 ...
- 676
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 ...
- 8,382
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 ...
- 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 ...
- 6,352
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 ...
- 3,168
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 ...
- 37.8k
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 ...
- 5,909
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 ...
- 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 ...
- 306
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^{'} ...
- 1,198
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(\...
- 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 \...
- 30.3k
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 ...
- 6,352
Only top scored, non community-wiki answers of a minimum length are eligible