Linear programming: a “Hello world” in SageMath – Reading Group on Optimization and Control

In this post we show how to formulate an LP in SageMath, and to solve it with GLPK, a standard open-source mathematical optimization package.

A mathematical optimization problem of the form:

$\displaystyle \text{minimize } c^T x \\ \text{subject to } a_i^T x \leq b_i,~~ i=1,\ldots,m$

is known as a linear program (or LP for short), because both the objective and constraint functions are linear. Here the vectors $\displaystyle c, a_1, \ldots, a_m \in \mathbb{R}^n$ and scalars $\displaystyle b_1, \ldots, b_m \in \mathbb{R}$ are problem parameters. Linear programs are a subclass of convex programs, since any linear function is convex.

As a toy example, consider:
$\displaystyle \begin{aligned} \text{min}& ~x_1 + x_2 \\ \text{s.t.}& ~x_1, x_2 \in [-1,1] \\ & ~2x_1 + x_2 \leq 0.5 \end{aligned}$

Below is the SageMath script (see the outcome here!):

# by default, it assumes 'minimization'. we can specify maximization with the additional parameter maximization = True
LP = MixedIntegerLinearProgram(solver = "GLPK")
 
# generate variables 
x = LP.new_variable(integer=False)
 
# add constraints
LP.add_constraint( -1 <= x[1] <= 1 );
LP.add_constraint( -1 <= x[2] <= 1 );
LP.add_constraint( 2*x[1] + x[2] <= 0.5 );
 
# set objective function
obj = x[1]+x[2]
LP.set_objective(obj)
 
print '**** Solving LP (with GLPK) ****'    
 
LP.show()
 
oval = LP.solve()
xopt = LP.get_values(x);
 
print 'Objective Value:', oval
for i, v in xopt.iteritems():
    print 'x_%s = %f' % (i, v)
    print '\n'

There are dozens of LP solvers (practically any language for doing scientific computing comes with its own package for optimization purposes!); check this list. It is worth noting that several commercial ones propose free academic licenses; among these, Gurobi is very interesting to consider.

We have chosen SageMath because it is a full-fledged platform for scientific computing. Moreover, it is free software, built upon Python (and Cython, for performance); consequently, there is a huge number of lines of code that you can readily re-use in your projects to achieve different functionalities.

References:

To install SageMath in your local machine.
To start using SageMathCloud, an open-source platform for doing collaborative mathematics, and an introductory video here.
An interactive applet for a simple linear program (by Prof. Gregory V. Bard).