OPTI Toolbox

Problem Definition

An LP has the following form:

Where f is a n x 1 vector containing the linear objective function, which is subject to the following constraints:

Linear Inequalities*

A is a m x n sparse matrix, b is a m x 1 vector.

Linear Equalities*

A_eq is a k x n sparse matrix, b_eq is a k x 1 vector.

Decision Variable Bounds

l_b and u_b are n x 1 vectors, where -inf or inf indicate an unbounded lower or upper bound, respectively.

The goal is to minimize the objective function by selecting a value of x that also satisfies all constraints.

*Your problem description will either use Linear Inequalties and Linear Equalities OR Linear Row Constraints. See the constraint information page.

Example 1: Small Dense LP

Consider the following LP from the basics section:

Note two important characteristics of this problem which make it an LP:

• The objective function is linear (the only operation is a constant times each decision variable, and the result summed).
• The constraints are also linear, as above.

Because of this linear property, we can rewrite this problem in matrix-vector form:

And supply the entire problem to the solver as a collection of matrices and vectors. This not only avoids costly callbacks to MATLAB, but the solver also knows the full structure of the model which it can use when solving.

Using the native matrix & vector notation of MATLAB this can be entered as so:

And the problem solved by passing the problem variables to OPTI, and calling solve on the resulting object:

Because the problem contains only two variables, we can use OPTI's built in plot command to view the solution:

You can see from the above figure that the linear gradient of the objective (dashed in grey) as well as the inequality constraints. Shaded areas represent infeasible regions. As with all LPs the solution will lie on a constraint, or intersection of one or more constraints. For LPs the objective gradient will always be equally spaced straight dashed lines, and constraints straight lines.

Example 2: Large Sparse LP

The above example represents the 'toy' problems that are common when learning linear programming. In reality the problems will typically contain hundreds of decision variables and thousands of constraints. In order to efficiently solve these problems the sparsity structure of the inequality and equality constraints must be exploited.

To illustrate, load a large LP supplied as a .MPS problem with OPTI and lets examine the A matrix:

The figure generated shows just how sparse the matrix is, with less than 0.5% of the entries containing a value other than zero. Exploiting sparsity means ignoring all the values which are zero, both when storing and solving the problem. This saves a lot of memory, and computation time!

In fact the preferred format for LPs with OPTI is to use the MATLAB sparse data type. This is due to all LP solvers supplied with OPTI accepting sparse constraints only! If you supply a dense matrix, it will be automatically converted to a sparse representation. Note the objective vector f and constraint upper and lower bounds, rl and ru must remain dense vectors.

The next important point with the loaded model is the representation of constraints. So far I have shown constraints where the inequality and equality constraints are stored and supplied separately. While this is the MATLAB default, a more efficient method is to store in what I call 'row format', as follows:

This format places bounds on each row of the constraint matrix A. See the constraint information page for more information on this format.

Finally to solve this problem, consider the format the problem has been loaded in:

This structure is a OPTI generated structure that contains all information required to define an optimization problem. It is a standard MATLAB structure so you are free to process it how you like, but it can also be supplied to OPTI as is:

Example 3: LP in Row Format

Consider the following toy LP problem:

For this problem we are going to enter it to OPTI in row format. You are free to choose the format, however you cannot mix the two in one problem. You will be presented with a warning if the selected solver requires a different format.