{"id":108,"date":"2016-10-11T17:43:16","date_gmt":"2016-10-11T15:43:16","guid":{"rendered":"https:\/\/project.inria.fr\/readinggroupoc\/?p=108"},"modified":"2017-06-11T12:17:53","modified_gmt":"2017-06-11T10:17:53","slug":"linear-programming-a-hello-world-in-sagemath","status":"publish","type":"post","link":"https:\/\/project.inria.fr\/readinggroupoc\/linear-programming-a-hello-world-in-sagemath\/","title":{"rendered":"Linear programming: a “Hello world” in SageMath"},"content":{"rendered":"

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

A mathematical optimization problem of the form:<\/p>\n\\(\\displaystyle \\text{minimize } c^T x \\\\ \\text{subject to } a_i^T x \\leq b_i,~~ i=1,\\ldots,m \\)\n

is known as a linear program<\/em> (or LP for short), because both the objective and constraint functions are linear. Here the vectors\u00a0\\(\\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.<\/p>\n

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

Below is the SageMath script (see the outcome here!<\/a>):<\/p>\n

# by default, it assumes 'minimization'. we can specify maximization with the additional parameter maximization = True\r\nLP = MixedIntegerLinearProgram(solver = \"GLPK\")\r\n\r\n# generate variables \r\nx = LP.new_variable(integer=False)\r\n\r\n# add constraints\r\nLP.add_constraint( -1 <= x[1] <= 1 );\r\nLP.add_constraint( -1 <= x[2] <= 1 );\r\nLP.add_constraint( 2*x[1] + x[2] <= 0.5 );\r\n\r\n# set objective function\r\nobj = x[1]+x[2]\r\nLP.set_objective(obj)\r\n\r\nprint '**** Solving LP (with GLPK) ****'    \r\n\r\nLP.show()\r\n\r\noval = LP.solve()\r\nxopt = LP.get_values(x);\r\n    \r\nprint 'Objective Value:', oval\r\nfor i, v in xopt.iteritems():\r\n    print 'x_%s = %f' % (i, v)\r\n    print '\\n'<\/pre>\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<\/a>. It is worth noting that several commercial ones propose free academic licenses; among these, Gurobi<\/a> is very interesting to consider.<\/p>\n
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. <\/p>\n
\n
References:<\/p>\n