# Tag Info

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,123

### 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.
• 32.7k
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 ...
• 39.6k

### 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,142
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 ...
• 12.2k
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,212

### 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{...
• 32.7k

### 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
Accepted

• 8,960

### 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
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,647

### 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,188

### 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 ...
• 39.6k

### 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,929

### 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

### 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

• 86