GLPK

Introduction

In this example, we will explore how to submit a GLPK program to Multivac to compute an objective function.

Example Code

Suppose we want to maximize the following objective function:

\[\begin{split}\begin{aligned} & \underset{\mathbf{x}}{\text{maximize}} & & Z = 10 x_0 + 6 x_1 + 4 x_2 \\ & \text{subject to} & & p = x_0 + x_1 + x_2 \\ & & & q = 10 x_0 + 4 x_1 + 5 x_2 \\ & & & r = 2 x_0 + 2 x_1 + 6 x_2 \\ & \text{and bounds of variables} & & -\infty < p \leq 100, \quad 0 \leq x_0 < \infty \\ & & & -\infty < q \leq 600, \quad 0 \leq x_1 < \infty \\ & & & -\infty < r \leq 300, \quad 0 \leq x_2 < \infty \\ \end{aligned}\end{split}\]

We will create a file named test_glpk.py to compute the result:

#!/usr/bin/python3
import glpk                         # Import the GLPK module
lp = glpk.LPX()                     # Create empty problem instance
lp.name = 'sample'                  # Assign symbolic name to problem
lp.obj.maximize = True              # Set this as a maximization problem
lp.rows.add(3)                      # Append three rows to this instance
for r in lp.rows:                   # Iterate over all rows
   r.name = chr(ord('p')+r.index)  # Name them p, q, and r
lp.rows[0].bounds = None, 100.0     # Set bound -inf < p <= 100
lp.rows[1].bounds = None, 600.0     # Set bound -inf < q <= 600
lp.rows[2].bounds = None, 300.0     # Set bound -inf < r <= 300
lp.cols.add(3)                      # Append three columns to this instance
for c in lp.cols:                   # Iterate over all columns
   c.name = 'x%d' % c.index        # Name them x0, x1, and x2
   c.bounds = 0.0, None            # Set bound 0 <= xi < inf
lp.obj[:] = [10.0, 6.0, 4.0]        # Set objective coefficients
lp.matrix = [
   1.0, 1.0, 1.0,                  # Set nonzero entries of the
   10.0, 4.0, 5.0,                 # constraint matrix. (In this
   2.0, 2.0, 6.0                   # case, all are non-zero.)
]
lp.simplex()                        # Solve this LP with the simplex method
print ('Z = %g;' % lp.obj.value)     # Retrieve and print obj func value
print ('; '.join('%s = %g' % (c.name, c.primal) for c in lp.cols))

Execution

We will create a Python virtual environment named venv. This step is only required the first time the venv is created; afterwards it can be reused. You need to install the GLPK package: pip install glpk

$ python3 -m venv venv
$ source venv/bin/activate
$ pip install glpk
$ deactivate

We will create a configuration file, for example test_glpk.slurm, containing the execution settings for this GLPK script.

VERSION=1.3
JOB_NAME=test_glpk
NAME_OUTPUT=out
PARTITION=all
N_TASKS=1
CPUS_PER_TASK=1
MAIL_TYPE=END,FAIL
MAIL_USER=nom.usuari@upc.edu
MEMORY=1G
BEGIN=now
TIME_LIMIT=00:05:00
LOG_OUTPUT=log
FORCED_NODES=
EXCLUDED_NODES=
ROUTE=~/
COMMANDS=(
   "hostname" # To know which machine executed the job
   "source $ROUTE/venv/bin/activate"
   "python3 $ROUTE/test_glpk.py"
   "deactivate"

)

We will submit this script from iocex using the following command:

multivac test_glpk.slurm

Once execution is complete, the output of our program will be visible in the same directory where the job was launched.