Tag Info

12

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 reduced solution times. My understanding is that you make the most out of enumerated valid inequalities when the linear relaxation of the MIP is poor, as they can ...

10

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 solver). It assumes that the variables are continuous, not discrete. For simplicity, I'll assume that all inequalities are of the form $a_i'x \ge b_i$ ($i=1,\dots,N$...

9

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 is to try both ways with the solver of your choice. Your results will also change over time, because newer versions of solvers generally implement better ...

9

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$ has a coefficient $c$ in the objective, and $y$ has a coefficient $d$ in the objective. That is, we consider the following program, with the dual variables ...

8

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 point has polynomial complexity for LP, it's the implementation challenges, i.e., manipulating matrices that take up massive memory (and sometimes need to be ...

7

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 Gurobi. You really have to test: sometimes, the solver already found better tricks; other times, there are things they are just not smart enough to seee.

6

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 do what you want, and maybe more. https://support.gurobi.com/hc/en-us/articles/360024738352-How-does-presolve-work- I suppose you can provide a model just ...

6

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 finite set of generators, extreme points and extreme rays). At it's core there often is some sort of finding all (discrete) solutions to a set of linear ...

5

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 applicable. If you are concerned about theoretical complexity, there exist algorithms to solve integer programming problems in polynomial time in fixed dimension. For ...

5

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} \text { for } j \in S\right\})$. Branch-and-bound techniques work by relaxing the integrality constraint and compute lower bounds of the problem (when you minimize)...

5

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). Deep cuts are globally valid, i.e., they are valid at every node of a branch-and-bound tree. This is usually the most desirable type of cut, because we don't ...

4

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 comment deals with vertex and facet enumeration. Since it is a bit unclear what you mean by "discrete solutions", let us distinguish four cases. Finding a single ...

4

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 feasible space to the integer convex hull. What does "Strong Inequalities" mean? There are many Valid Inequalities and the best of them are called Strong ...

3

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 but their main advantage remains warmstarting capabilities. Inside MILP solvers we need to solve many closely related problems and dual simplex (and in some ...

3

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 resource-consuming enumeration, and the list of facets will be very long, maybe too long. Yet, it may depend on your use case. In optimization practice, you almost ...

2

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 term: constraint propagation. For an introduction check for instance: http://www.cs.unibo.it/~gabbri/MaterialeCorsi/CP@CS.pdf

2

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 David Avis from McGill University. One of its key functionalities is redund - quick and efficient removal of redundant inequalities from an H-representaion of a ...

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