Working with LP solver

The ALGLIB package includes two linear programming solvers, simplex method and interior point method (IPM), which can be used via a common API. This page discusses the linear programming API provided by ALGLIB and some generic LP-related questions.

We also recommend that you read the aforementioned articles on the simplex method and the IPM for a better understanding of solver-specific issues.

Creating a minlpstate instance

A solver object stores all details of your problem formulation: variables count, target function, and constraints. It is created with the minlpcreate constructor function, which accepts variables count N and returns a solver object with a 'default' N-dimensional optimization problem being configured.

Note #1
As of ALGLIB 3.17, problem dimensionality is fixed and can't be changed on the fly.

The default problem is perfectly valid, i.e., you can call minlpoptimize right after the solver creation, but it makes no sense: the default problem has zero cost and no general linear constraints, and all variables are fixed at zero value. Thus, the next step is to load your linear programming problem into the solver object.

The steps outlined below can be done in any sequence, and, in fact, you can call these functions multiple times. In most cases, new calls will overwrite the results of the previous calls ('set' semantics), and in some cases, functions will perform incremental modification of the solver state ('add' semantics).

Specifying a linear programming problem

Target function (cost vector)

The target function (cost vector) can be set with the minlpsetcost function.

Box constraints

Box constraints have the form L ≤ x ≤ U, with L_i=-∞ meaning that no lower bound is present, and U_i=+∞ meaning that no upper bound is present. It is possible to have free variables (no constraints at all). Unlike some LP solvers, ALGLIB has no problems with such variables. It is also possible to have some (or even all) L_i=U_i, which means that the i-th variable is fixed.

The default state of the box constraints is L=U=0, i.e., x is fixed at exactly zero value. Box constraints can be modified with the following functions:

• minlpsetbc to set lower and upper bounds to user-specified N-dimensional vectors BndL and BndU (different bounds may be specified for different variables)
• minlpsetbcall to set the same lower and upper bounds for all variables
• minlpsetbci to modify box constraints for an individual variable

General linear constraints

ALGLIB supports two-sided linear constraints A_L ≤ A·x ≤ A_U. It is the most flexible formulation of the linear constraints that can represent equality, inequality, and range constraints:

• A_L,i=-∞ means that we have an upper bound constraint A_i·x ≤ A_U,i
• A_U,i=+∞ means that we have a lower bound constraint A_L,i ≤ A_i·x
• -∞ < A_L,i < A_U,i < +∞ means that we have a range constraint A_L,i ≤ A_i·x ≤ A_U,i
• finally, -∞ < A_L,i=A_U,i < +∞ means that we have an equality constraint A_L,i=A_i·x=A_U,i

The default state of linear constraints is an absense of constraints. Linear constraints can be modified (either completely rewritten or incrementally modified) with the following functions:

• minlpsetlc2 to rewrite current constraints by A_L ≤ A·x ≤ A_U, with A being a sparse matrix (an instance of the sparsematrix class)
• minlpsetlc2dense to rewrite current constraints by A_L ≤ A·x ≤ A_U, with A being a dense matrix
• minlpaddlc2 to append a single linear constraint A_L,k ≤ A_k·x ≤ A_U,k to the end of the present constraint matrix, with A_k being a row stored in the sparse compressed format (set of indexes and values)
• minlpaddlc2dense to append a single linear constraint A_L,k ≤ A_k·x ≤ A_U,k to the end of the present constraint matrix, with A_k being a row stored in conventional dense storage format (as a vector)

Variable scales

In this section we briefly discuss how variable scaling is controlled in ALGLIB. Additional information can be found in this separate article on variable scaling.

Knowing variable scales is important for two reasons. First and foremost, it allows the optimizer to automatically adjust stopping criteria for differently scaled variables. All stepsize-based stopping criteria in ALGLIB are calculated times variable scale. Second, variable scales may be used as a preconditioner.

Most LP/NLP solvers do not require their users to provide variable scales, instead relying on various heuristics that rescale the input problem by looking into cost and constraints. In our opinion, all such heuristics may fail, so we prefer to give our users explicit control over variable scaling.

By default, the LP solver assumes that all variables have unit scale. These default scales can be modified with the minlpsetscale function.

Running the LP solver

Choosing the LP algorithm

As of version 3.17, ALGLIB includes the following LP solvers:

• revised dual simplex method, selected by calling minlpsetalgodss
• interior point method, selected by calling minlpsetalgoipm

An interior point method (IPM) is used by default. This method is easier to accelerate in C++ and C# with low-level optimizations (see the article on the method for more details), and it has a very clean and straightforward internal structure. Contrary to that, the simplex method has difficult data access patterns that are hard to accelerate with SIMD or parallelism.

From the other side, these two methods are so different that they complement each other. On some problems, the simplex method works faster and/or has better stability than the IPM. Thus, if your problem can't be solved by the interior point solver, the dual simplex method is worth trying.

Optimization and results

Optimization is performed in two steps: first, you call minlpoptimize to run the solver, and second, you call minlpresults to retrieve the results of the last optimization round. The latter function returns solution candidate x and optimization report rep, an instance of the minlpreport class. The report structure stores additional information:

• target function value rep.f
• dual variables rep.y
• statuses of the box/linear constraints rep.stats
• primal and dual errors, iterations count, and termination type

One may call minlpoptimize many times for the same solver object (say, after the modification of the problem specification). Subsequent calls try to reuse previously allocated memory as much as possible. In the native ALGLIB (C++, Python, ...), it results in a great reduction of memory fragmentation. In the managed environment (C#), memory fragmentation is not an issue, but the load on the garbage collector still matters.

Linear programming tips and tricks

In addition to the present description of the ALGLIB linear programming API, we also recommend an article with several tips and tricks for linear programming. This article discusses common errors made during problem modeling, ways to improve performance, and so on.

This article is licensed for personal use only.