3
$\begingroup$

Suppose we have a feasible LP problem in its standard form. From Ax=b we can directly determine some of its variables and thus we can reduce the problem.

For example, from two constraints: x+y+z=2 and x+y=1, we can determine z=1. Then we can replace 'z' with '1' and move it to the RHS, and delete variable 'z' as well as one of the constraints above.

Are there any tools which can do this kind of reduction?

$\endgroup$

1 Answer 1

9
$\begingroup$

Concept

The tools you are referring to are commonly called presolvers.

Resources (Implementation) / Availability

Every optimization software makes use of those (to improve performance, but also numerical-stability). This includes commercial solvers, as well as non-commercial ones.

Most implementations, if not all are embedded into the solver framework. The sole exception known to me would be:

  • papilo: Parallel Presolve for Integer and Linear Optimization (LP + MILP)

Embedded candidates to look at:

  • SCIP (LP + MILP + ?MINLP?)
  • HiGHS (LP + MILP)
  • CoinOR Clp (LP)
    • (somewhere in CoinOR Cbc or related libs would be MILP presolving too)

Even if embedded, most most solvers allow to do the presolving step in an isolated step without automatically triggering follow-up solving (if the user wants it).

Resources (Theory)

There are high-quality resources on this topic.

Linear-Programming

  • Andersen, Erling D., and Knud D. Andersen. "Presolving in linear programming." Mathematical Programming 71 (1995): 221-245.

Mixed-Integer-Programming Extensions

In this context, presolving is usually much more important and much more powerful (imho).

  • Achterberg, Tobias, et al. "Presolve reductions in mixed integer programming." INFORMS Journal on Computing 32.2 (2020): 473-506.
  • Gamrath, Gerald, et al. "Progress in presolving for mixed integer programming." Mathematical Programming Computation 7 (2015): 367-398.
$\endgroup$
1
  • $\begingroup$ Thanks a lot! It seems that those presolvers may break the standard form. Can we reduce the problem while maintaining the standard form? $\endgroup$
    – andy
    Aug 28, 2023 at 14:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.