Linear programming tips and tricks

This page provides tips and tricks for the ALGLIB LP solver, and it discusses some common errors. See the 'Using LP solver' article for a description of the ALGLIB linear programming API.

Linear programming tips and tricks

Properly scale your variables

Variable scaling is important - it provides an optimizer with essential hints on the geometry of the problem and per-variable accuracy expectations. Especially badly scaled problems can't be solved without knowledge of variable scales, so it is important to provide the optimizer with explicit variable scales.

Try different LP solvers

The simplex method and the interior point method behave differently. Some problems that are difficult to solve with the simplex method (usually due to primal/dual degeneracy) can be easily solved with the interior point method. Similarly, there are problems that are hard to solve with the interior point method but easy to solve with the simplex method.

Thus, it is essential to try both solvers on your problem and to check solution quality (target value, primal and dual errors) and running time.

Use INF, not some large number for bounds

It is tempting to use arbitrarily large upper bounds to 'emulate' a variable with no upper bound. It is possible to specify the box constraint of the form 0 ≤ x ≤ 10000000000 just to tell the solver that x is nonnegative and that we do not care about its upper bound.

Nonlinear programming solvers usually handle such bounds without a problem, but LP solvers are special. The simplex method can ignore such bounds in most cases, but the interior point method can be destabilized by them. The ALGLIB implementation of the interior point method has several heuristics that try to detect such bounds and drop them on the fly, but nevertheless it is much better to use ∞ to tell the LP solver that the variable is unconstrained from above (or below).

Reuse the solver object when possible

If one sequentially solves many problems with same variable count N, it makes sense to reuse the LP solver instance. It is possible to modify a previously used solver object by completely rewriting box/linear constraints or incrementally adding new ones and running optimization again. In this case, previously allocated memory will be reused as much as possible.

This strategy is beneficial for two reasons. First, it greatly reduces memory fragmentation (important for C++ or other native programming environments). Second, even when running on .NET, where memory fragmentation is not a problem, one may want to put less stress on the garbage collector (especially important for long-running high-performance applications).

Use native ALGLIB, if possible

This advice is intended for C# users who can choose between a fully managed ALGLIB implementation and a C# wrapper around a native computational core.

Quite often, performance of .NET applications approaches that of native code. Nevertheless, high-performance computing is a special area where it is possible to achieve almost 100% utilization of your CPU. And native code is still a winner in this area - one may achieve ~1.5-2x speedup by switching to native ALGLIB.

This article is licensed for personal use only.