Optimization

introduction | linear programming | convex optimization | integer programming | overdetermined problems | underdetermined problems | duality

glpk | matlab/cvx | r/lpsolve | python/cvxopt | excel

introduction

A general form of an optimization problem is to minimize g(x) subject to

(1)
\begin{align} \;\;\;\;\;\;\;f_i(x) \leq b_i, \;\; i \in \{1, ..., n\} \end{align}

where x is a n-dimensional real vector and g and fᵢ are real-valued.

g is the objective function. The components of x are the decision variables. The fᵢ(x) ≤ bᵢ are the constraints.

The maximum of g is the minimum of -g, so a maximization problem can be recast as a minimization problem. The value of the decision variables at the optimum is the same, but the sign of the value of the objective function at the optimum is reversed.

A constraint of the form h(x) = c can be replaced by two constraints of the form h₁(x) ≤ c and h₂(x) ≥ c without changing the meaning of the problem. Moreover, a constraint of the form h(x) ≥ c can be replaced with the equivalent constaint -h(x) ≤ -c.

linear programming

If the objective function g = ∑cᵢ xᵢ and the inequality constraint functions fᵢ = ∑ aᵢⱼ xⱼ are linear, the problem is a linear optimization problem, also called a linear program.

A general form for a linear program is to minimize cTx subject to A x ≤ b and x ≥ 0. Here c and x are vectors with length equal to the number of decision variables. b is a vector with length equal to the number of constraints, and A is a matrix with row count equal to the number of constraints and column count equal to the number of decision variables.

The constraint x ≥ 0 can be imposed without loss of generality by replacing each decision variable xᵢ with xᵢ+ - xᵢ-, where xᵢ+ ≥ 0 and xᵢ- ≥ 0.

convex optimization

integer programming

overdetermined problems

underdetermined problems

duality

The dual problem of maximizing cTx subject to Ax ≤ b and x ≥ 0 is minimizing bTy subject to ATy ≥ c and y ≥ 0. In this context the original problem is called the primal problem.

The primal and the dual problem share the same optimal value, if there is one. Feasible solutions to the primal problem are lower bounds to the optimal value. Feasible solutions to the dual problem are upper bounds to the optimal value. If the primal is unconstrained, the dual is infeasible. If the dual is unconstrained, the primal is infeasible. It is possible for both the primal and dual to be infeasible.

Minimization problems also have a dual. Furthermore, if P is a linear program, and D is its dual, then the dual of D is P.

Duals also exist for nonlinear optimization problems. Although the feasible solutions of the dual of a maximization problem provide upper bounds, the optimal value of the dual may be strictly greater than the optimal value of the primal. The difference is called the duality gap. For convex problems, if the problem meets the KKT conditions the duality gap is zero.

glpk

installation

$ brew install homebrew/science/glpk

$ sudo apt-get install glpk-utils

$ sudo yum install glpk-utils

installing on windows

documentation

GLPK supports several formats for describing the problem. glpsol --help will list them.

Install the package glpk-doc to get a PDF which describes the GMPL format. The PDF is also available here:

Modeling Language GNU MathProg (pdf)

GMPL is a subset of AMPL:

AMPL: A Modeling Language for Mathematical Programming

$ cat lp1.model
var x1 >= 0;
var x2 >= 0;
maximize obj: x1 + 2 * x2;
c1: -3 * x1 + x2 <= 2;
c2: x2 <= 11;
c3: x1 - x2 <= 3;
c4: x1 <= 6;
solve;
display x1;
display x2;
display obj;
end;

$ glpsol -m lp1.model

separate model and data

matlab/cvx

download cvx
install cvx
cvx user's guide

cvx_begin
  variable x1;
  variable x2;
  maximize x1 + 2 * x2;
  subject to
    -3 * x1 + x2 <= 2;
    x2 <= 11;
    x1 - x2 <= 3;
    x1 <= 6;
cvx_end

r/lpsolve

> install.packages('lpSolve')
> require(lpSolve)

> obj = c(1, 2)
> mat = matrix(c(-3, 1, 0, 1, 1, -1, 1, 0), nrow=4, byrow=T)
> dir = c("<=", "<=", "<=", "<=")
> rhs = c(2, 11, 3, 6)
> lp("max", obj, mat, dir, rhs)
Success: the objective function is 28

python/cvxopt

cvxopt user's guide

$ sudo pip install cvxopt

cvxopt finds minimal values for the objective function. To solve a maximization problem, we negate the objective function. We must remember the negate the value of the objective function that we find to get the maximal value.

>>> from cvxopt.modeling import *
>>> x1 = variable(1, 'x1')
>>> x2 = variable(1, 'x2')
>>> c1 = (-3 * x1 + x2 <= 2)
>>> c2 = (x2 <= 11);
>>> c3 = (x1 - x2 <= 3)
>>> c4 = (x1 <= 6)
>>> lp1 = op(-x1 - 2 * x2, [c1, c2, c3, c4])
>>> lp1.solve()
     pcost       dcost       gap    pres   dres   k/t
 0: -1.7235e+01 -5.8647e+01  3e+01  0e+00  1e+00  1e+00
 1: -2.5048e+01 -2.9964e+01  4e+00  4e-16  1e-01  2e-01
 2: -2.7685e+01 -2.8988e+01  1e+00  4e-16  4e-02  1e-01
 3: -2.7997e+01 -2.8010e+01  1e-02  1e-16  4e-04  1e-03
 4: -2.8000e+01 -2.8000e+01  1e-04  2e-16  4e-06  1e-05
 5: -2.8000e+01 -2.8000e+01  1e-06  3e-16  4e-08  1e-07
Optimal solution found.
>>> lp1.status
'optimal'
>>> print(lp1.objective.value())
[-2.80e+01]
>>> print(x1.value)
[ 6.00e+00]
>>> print(x2.value)
[ 1.10e+01]

excel

To solve a linear optimization problem in Excel, the Solver.Xlam add-in must be selected. Go to:

Tools | Add-Ins...

This provides a Solver button in the Data section of the ribbon.

To use it, allocate a row or column to contain the decision variables, and allocate a cell for the objective function which is defined in terms of those decision variables. The SUMPRODUCT function is useful when defining the objective function.

Click the Solver button, which brings up a dialog.

solver.png

Enter the cell reference of the objective function in the topmost box.

Indicate whether the problem is a minimization or maximization problem using the radio buttons.

Enter the cell range of the decision variables in input box below that.

One enters the constaints one at a time by clicking the Add button, which brings up another dialog.

Note that there is a checkbox that can be used to indicate that all decision variables are non-negative.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License