This document explains the function of the classes defined in PyGLPK. In addition to descriptions, for the benefit of those familiar with the C API, it proceeds by example and analogy to the C API: there is often some C code in one color followed by some Python code in a different color which tries to do the same thing, in this spirit:

printf("Hello world!"); total = 0; for (i=0; i<10; ++i) total += i*i;

print "Hello world!" total = sum(i*i for i in range(10))

Hopefully, in the case of multiline examples, it should be obvious which lines correspond to each other.

Reading this document through is not necessarily the best way to gain an understanding of PyGLPK if you are completely new to it. This is organized in order of object above any other consideration: advanced obscure subjects relating to LPX objects occur before simple functionality of row and column objects. Rather, this is intended to be a reference.

The most basic object in PyGLPK is the LPX class, just as in the GLPK C API it is the LPX structure. As a rule, it holds data and methods that are relevant to the linear problem as a whole. Throughout the code in this document, the token `lp`

refers to an LPX object.

One may create the Python instance of an LPX problem with a constructor. An LPX that has been modified can be restored to its original pristine state with a call to the `erase`

method. One may explicitly delete the object. Note that one does not need to delete the LPX object as it should be automatically garbage collected, though it may be desirable to do so, just as it is sometimes desirable to free a Python object without waiting until it falls out of scope.

lp = glp_create_prob(); glp_erase_prob(lp); glp_delete_prob(lp);

lp = glpk.LPX() lp.erase() del lp

If you have maintained objects which point back to the LPX object (e.g., rows, columns, objective function), the LPX can be deleted, but the underlying object shall not be freed until these references are discarded. In other words, there is nothing special about deleting the object versus any other Python object. The point is that `del lp`

will not necessarily result in deallocation of the LPX structure.

One gets and sets the name for a problem by querying or assigning to the `name`

attribute. As with the C API, names are limited to 255 characters. Unset names are `None`

. One unsets a name by assigning `None`

or deleting the `name`

.

glp_set_prob_name(lp, "some name"); glp_set_prob_name(lp, NULL); char *thename = glp_get_prob_name(lp);

lp.name = "some name" del lp.name # Alternately, lp.name = None thename = lp.name

One gets and sets the entries of the entire constraint matrix by querying or assigning the attribute `matrix`

. Assignments to `matrix`

will remove previous entries.

Retrieving `matrix`

will yeild a list of three element `(int,int,float)`

tuples over the non-zero entries in this matrix, each of the form `(ri, ci, value)`

, indicating that row `ri`

and column `ci`

(counting from 0) hold value `value`

.

For example, consider if `lp`

encoded the constraint matrix:

p | = | x_{0} | + | x_{1} | + | x_{2} |

q | = | 10x_{0} | + | 4x_{1} | + | 5x_{2} |

r | = | 2x_{0} | + | 6x_{2} |

Then `print lp.matrix`

outputs `[(0, 0, 1.0), (0, 1, 1.0), (0, 2, 1.0), (1, 0, 10.0), (1, 1, 4.0), (1, 2, 5.0), (2, 0, 2.0), (2, 2, 6.0)]`

.

For setting rather than getting, one may set all non-zero entries of the constraint matrix by assigning an iterable with similar structure to the `matrix`

attribute. The iterable must yield values each in one of these two forms:

- The integer-integer-float tuple
`(ri, ci, value)`

where`index`

≥ 0 specifies that element`index`

should have value`value`

(negative indices are permitted in this context if you like) - The single float item
`value`

which specifies an object equivalent to`(ri, ci+1, value)`

(or`(ri+1, 0, value)`

if`ci+1`

goes past the end of the column) where`ri, ci`

was the last location considered. If this single-value form is used on the first entry, the location 0, 0 is assumed.

Indices out of bounds will result in an `IndexError`

and duplicate indices will result in an `ValueError`

. Order does not matter, except of course for single value entries, as their location depends on the previous entry.

One may set all entries of a row or column in the constraint matrix to zero by assigning `None`

to or deleting the `matrix`

attribute.

Suppose we wanted to set rather than get the earlier matrix.

int ia[] = {0+1, 0+1, 0+1, 1+1, 2+1, 1+1, 1+1, 2+1}; int ja[] = {0+1, 1+1, 2+1, 0+1, 0+1, 1+1, 2+1, 2+1}; double ar[] = {1.0, 1.0, 1.0, 10.0, 2.0, 4.0, 5.0, 6.0} glp_load_matrix(lp, sizeof(ia), ia, ja, ar);

lp.matrix = [(0, 0, 1.0), (0, 1, 1.0), (0, 2, 1.0), (1, 0, 10.0), (2, 0, 2.0), (1, 1, 4.0), (1, 2, 5.0), (2, 2, 6.0)]

One could also do the following.

lp.matrix = [ 1.0, 1.0, 1.0, 10.0, 4.0, 5.0, 2.0, 0.0, 6.0 ]

One gets the number of non-zero constraint matrix entries by querying the `nnz`

integer attribute.

int numnonzero = glp_get_num_nz(lp);

numnonzero = lp.nnz

The user may want to define the initial LP basis prior to starting simplex optimization. There are several automatic ways of constructing this basis.

`std_basis`

method constructs a trivial LP basis.`adv_basis`

method constructs an advanced LP basis that tries to have as few fixed variables as possible while maintaining the triangularity of the basis matrix.`cpx_basis`

method constructs an advanced LP basis as described in R. Bixby. "Implementing the Simplex method: The initial basis."*ORSA Journal on Computing*, 4(3), 1992.`read_basis`

reads a basis stored in the fixed MPS file format from a given file name. If this method fails, it throws a`RuntimeError`

.

glp_std_basis(lp); glp_adv_basis(lp, 0); glp_cpx_basis(lp); lpx_read_basis(lp, "/path/to/file");

lp.std_basis() lp.adv_basis() lp.cpx_basis() lp.read_basis("/path/to/file")

Prior to optimization, it is often help to scale your problem, in part to avoid numerical instability. The method `scale`

tells the linear program to transform the program into an alternate equivalent formulation with better numerical properties. **Note that this transformation is transparent to the user.** This is a matter of internal representation used to help the solver. This procedure obeys the following flags defined as integers in the LPX class, which can be ORed together to produce a combination of effects:

`SF_GM`

: perform geometric mean scaling`SF_EQ`

: perform equilibration scaling`SF_2N`

: round scale factors to the nearest power of two`SF_SKIP`

: skip scaling, if the problem is well scaled`SF_AUTO`

: choose scaling options automatically

By using the `unscale`

method, one can cancel any previous scaling.

glp_scale_prob(lp, GLP_SF_AUTO); glp_scale_prob(lp, GLP_SF_GM | GLP_SF_2N); glp_unscale_prob(lp);

lp.scale() lp.scale(LPX.SF_GM | LPX.SF_2N) lp.unscale()

One gets the kind of problem (the default linear program or mixed integer) by querying the attribute `kind`

. This will hold either `float`

if this is a pure linear program (LP), or `int`

if this is a mixed integer program (MIP) by having any integer or binary column variables. A linear program becomes a mixed integer program by having some of its columns assigned to either `bin`

or `int`

kind.

int thekind = lpx_get_class(lp);

thekind = lp.kind

One gets the number of integer and binary (i.e., integer with 0, 1 bounds) column variables by querying the `nint`

and `nbin`

integer attributes, respectively. If this is not a mixed integer problem, these attributes always hold 0.

int num_int = glp_get_num_int(lp); int num_bin = glp_get_num_bin(lp);

num_int = lp.nint num_bin = lp.nbin

When it comes time to actually solving a linear program, one calls a `lp.`

method, where *solver*()

refers to one of several solver methods. There are several choices available.*solver*

`simplex`

is a standard simplex method.`exact`

is an exact simplex method.`interior`

is an interior point method.`integer`

is a method that uses a branch-and-bound based method to solve a mixed integer program (MIP). This method requires an existing optimal basic solution as acquired through either`simplex()`

or`exact().`

`intopt`

is a more advanced branch-and-bound MIP solver. This does not require an existing optimal basic solution.

Return values are either `None`

if the solver terminated normally, or a string denoting one of several possible error messages. See help for each method to review these possible return values.

Some of these solver routines may accept additional keyword parameters to control the behavior of the underlying solver. See help for each method to review possible control parameters and default values.

glp_simplex(lp, params); lpx_exact(lp); lpx_interior(lp); glp_intopt(lp, params); // These two may be applied only to MIP problems lpx_intopt(lp);

lp.simplex() lp.exact() lp.interior() lp.integer() # These two may be applied only to MIP problems lp.intopt()

Note, the solver not returning a message simply means that it terminated without error. **It does not mean that an optimal solution or indeed any solution was found!** For example, a solver could terminate without error if it determines that there is no feasible solution.

One gets the solution status for the last solver by querying the `status`

attribute. This takes the form of a string with several possible values.

`opt`

meaning the solution is optimal.`undef`

meaning the solution is undefined.`feas`

meaning the solution is feasible, but not necessarily optimal.`infeas`

meaning the solution is infeasible.`nofeas`

meaning the problem has no feasible solution.`unbnd`

meaning the problem has an unbounded solution.

int stat = glp_get_status(lp); // or glp_(ipt|mip)_status

stat = lp.status

Unlike the C API, PyGLPK remembers which solver was used last and retrieves the corresponding status value. If for whatever reason you wish to retrieve the status of a solver's solution other than what was used last, you may ask for `status_s`

(for `simplex`

and `exact`

), or `status_i`

(for `interior`

), or `status_m`

(for `integer`

or `intopt`

).

Additionally, if one has used the simplex solver, one can get the primal and dual status with the `status_primal`

and `status_dual`

attributes.

int pstat = glp_get_prim_stat(lp); int dstat = glp_get_dual_stat(lp);

pstat = lp.status_primal dstat = lp.status_dual

If, after running a simplex optimizer, your basic solution is unbounded, you may retrieve the row or column corresponding to the non-basic variable causing primal unboundedness within the attribute `ray`

. The meaning of this is that corresponding variable is able to infinitely change in some unbounded direction to improve the objective function.

int the_var_index = lpx_get_ray_info(lp);

row_or_col = lp.ray

In addition to programmatically defining a linear problem, there are methods to read linear programs and MIPs from files. We have seen the empty LPX constructor employed to create an empty problem. The LPX constructor also has the ability to accept a single keyword argument: the keywords specifies a file format, and the argument specifies the filename, as in `lp=glpk.LPX(`

. If successfully read, an LPX instance will be created with the file data.*format*=*filename*)

All formats accept a single string representing the path to the file to be read. Valid formats include the following.

`gmp`

for reading a model and a data file in the GNU MathProg modeling language`mps`

for reading a fixed MPS formatted files`freemps`

for reading a free MPS formatted file`cpxlp`

for reading a CPLEX LP formatted file`glp`

for reading a GNU LP formatted file

The format `gmp`

(GNU MathProg), in addition to accepting a single string argument, may optionally accept a three element tuple instead, containing these elements:

- A file name argument specifying the GMP model file.
- A file name argument specifying the GMP data file. This may optionally be
`None`

if the data is included in the model file. - A file name argument specifying the output file, where the output of any "display" statements in the GMP are output. This may optionally be
`None`

to send output to standard output.

`gmp`

option, if you input a single string `filename`

instead of a tuple, it is equivalent to inputing the tuple `(filename, None, None)`

.
lp = lpx_read_mps("/path/to/mps_file") lp = lpx_read_freemps("/path/to/free_mps_file") lp = lpx_read_cpxlp("/path/to/cplexlp_file") lp = lpx_read_model("modelfile", NULL, NULL) lp = lpx_read_model("modelfile", "datafile", "output.txt") lp = lpx_read_prob("/path/to/gnulp_file")

lp = glpk.LPX(mps="/path/to/mps_file") lp = glpk.LPX(freemps="/path/to/free_mps_file") lp = glpk.LPX(cpxlp="/path/to/cplexlp_file") lp = glpk.LPX(gmp="modelfile") lp = glpk.LPX(gmp=("modelfile", "datafile", "output.txt")) lp = glpk.LPX(glp="/path/to/gnulp_file")

One may export data about a linear program to a file in a variety of formats conveying a variety of different types of information using the method `write`

. The method accepts a large number of keyword arguments: each keyword specifies a file format, and the argument a file name, as in `lp.write(`

. Upon invocation, the LPX object will attempt to write the data specified by the format into the indicated file.*format*=*filename*)

Valid formats include the following.

`mps`

for problem data in the fixed MPS format.`bas`

for the LP basis in fixed MPS format.`freemps`

for problem data in the free MPS format.`cpxlp`

for problem data in the CPLEX LP format.`glp`

for problem data in the GNU LP format.`prob`

for problem data in a plain text format.`sol`

for basic solution in printable format.`sens_bnds`

for bounds sensitivity information.`ips`

for interior-point solution in printable format.`mip`

for MIP solution in printable format.

`write`

in order to write multiple files in multiple formats in one go. For example, you might want to simultaneously write out printable problem data, solutions, and bounds sensitivity information all in one go with something like `lp.write(prob="foo.prob", sol="foo.sol", sens_bnds="foo.bnds")`

.
lpx_write_mps(lp, filename) lpx_write_bas(lp, filename) lpx_write_freemps(lp, filename) lpx_write_prob(lp, filename) lpx_write_cpxlp(lp, filename) lpx_print_prob(lp, filename) lpx_print_sol(lp, filename) lpx_print_sens_bnds(lp, filename) lpx_print_ips(lp, filename) lpx_print_mip(lp, filename)

lp.write(mps=filename) lp.write(bas=filename) lp.write(freemps=filename) lp.write(glp=filename) lp.write(cpxlp=filename) lp.write(prob=filename) lp.write(sol=filename) lp.write(sens_bnds=filename) lp.write(ips=filename) lp.write(mip=filename)

A linear program objective function specifies what linear function the LP is attempting to either minimize or maximize. Correspondingly, the objective object allows one to set objective function coefficients and the direction of optimization, and retrieve the objection function value after optimization.

The objective function for an LPX object `lp`

is contained within `lp.obj`

. This objects is an instance of the `Objective`

class. Through this object one can set the objective coefficients and retrieve the objective value.

Similar to how one names problems, one gets and sets the name for the objective function by querying or assigning to the `name`

attribute. As with the C API, names are limited to 255 characters. Unset names are `None`

. One unsets a name by assigning `None`

or deleting the `name`

.

glp_set_obj_name(lp, "some name"); glp_set_obj_name(lp, NULL); char *thename = glp_get_obj_name(lp);

lp.obj.name = "some name" del lp.obj.name thename = lp.obj.name

One gets and sets whether this is a minimization or maximization problem by querying or assigning to the `maximize`

boolean attribute.

glp_set_obj_dir(lp, GLP_MIN); glp_set_obj_dir(lp, GLP_MAX); int ismax = (glp_get_obj_dir(lp) == GLP_MAX);

lp.obj.maximize = False lp.obj.maximize = True ismax = lp.obj.maximize

One gets and sets the objective function coefficients by indexing into the `obj`

object, e.g., `lp.obj[index]`

. There are as many objective coefficients as there are columns, so valid indices include `0`

through `len(lp.cols)-1`

as well as (for negative indexing) `-1`

through `-len(lp.cols)`

.

One can access and change these objective coefficients through either a single index, or access or change multiple coefficients by defining multiple indices through either a series of indices or a slice.

When assigning new objective coefficients, valid assignments include single numbers (in which case all indexed coefficients receive this same value) or an iterable object (in which case all indexed coefficients receive values specified in turn).

The objective function's constant shift term can be accessed either by using `None`

as an index, or by accessing the `shift`

attribute, that is, `lp.obj.shift`

.

glp_set_obj_coef(lp, 2+1, 3.0); for (i=0; i<glp_get_num_cols(lp); ++i) glp_set_obj_coef(lp, i+1, 1.0) glp_set_obj_coef(lp, 0+1, 3.14159); glp_set_obj_coef(lp, 2+1, -2.0); glp_set_obj_coef(lp, 0, 0.5); glp_set_obj_coef(lp, glp_get_num_cols(lp), 25.0); double c = glp_get_obj_coef(lp, 3+1); double c1 = glp_get_obj_coef(lp, 1+1), c2 = glp_get_obj_coef(lp, 2+1);

lp.obj[2] = 3.0 lp.obj[:] = 1.0 lp.obj[0,2] = 3.14159, -2.0 lp.obj.shift = 0.5 # Alternately, lp.obj[None] = 0.5 lp.obj[-1] = 25.0 c = lp.obj[3] c1, c2 = lp.obj[1,2]

One gets the value for the objective function by querying the `value`

attribute.

double oval = glp_get_obj_val(lp); // or glp_(ipt|mip)_obj_val

oval = lp.obj.value

Unlike the C API, PyGLPK remembers which solver was used last and retrieves the corresponding objective function value. If for whatever reason you wish to retrieve an objective function from a solver type different from what you used last, you can force the issue by asking for `value_s`

(for `simplex`

and `exact`

), or `value_i`

(for `interior`

), or `value_m`

(for `integer`

or `intopt`

).

double soval = glp_get_obj_value(lp); double ioval = glp_ipt_obj_value(lp); double moval = glp_mip_obj_value(lp);

soval = lp.obj.value_s ioval = lp.obj.value_i moval = lp.obj.value_m

In a linear program, rows and columns correspond to variables. Correspondingly, individual rows and column objects contain methods and data pertaining to individual variables: bounds, values after optimization, status, relevant entries of the constraint matrix, and other such objects.

Rows and columns live all live within two objects stored within an LPX object `lp`

as `lp.rows`

and `lp.cols`

. Both of these objects is an instance of the `BarCollection`

class. Individual rows and columns, all of type `Bar`

, can be accessed by indexing or iteration over these collections.

To add rows or columns, call the `add`

method on either the `row`

or `column`

subcontainer. As in the C API, the newly created rows and columns are initially empty, and the return value of the `add`

method holds the first newly valid index.

int rnew = glp_add_rows(lp, nrs); int cnew = glp_add_cols(lp, ncs);

rnew = lp.rows.add(nrs) cnew = lp.cols.add(ncs)

One gets the number of rows or columns by querying the length of the LP's `row`

and `column`

containers.

int nrs = glp_get_num_rows(lp); int ncs = glp_get_num_cols(lp);

nrs = len(lp.rows) ncs = len(lp.cols)

One accesses particular rows and columns by indexing into the `lp.rows`

and `lp.cols`

collections. For example, `lp.rows[ri]`

returns the row at index `ri`

. This index may also be a negative index counting backwards from the end of the collection, e.g., `lp.cols[-1]`

to get the last column of the LP.

These structures adopt much of the familiar behavior of Python sequences. Among other implications, this means that unlike in the C API, rows and columns are indexed from 0.

As we shall see, rows and columns can be named. One may also index named rows and columns by their names.

int rownum = glp_find_row(lp, "rowname")

row = lp.rows["rowname"]

In addition to single integer or string values, one may specify multiple values in this index to retrieve a list of all specified rows or columns.

lp.cols[2,5,"bob",6] # columns 2, 5, one named "bob", 8

Indexing by slicing is supported as well. This will result in a list of all indices specified by the slice.

lp.rows[4:9] # rows 4 through 8 lp.cols[-3:] # the last 3 columns lp.rows[::2] # every row with an even index

One may also iterate over the `lp.rows`

and `lp.cols`

collections. Here is a comparative example of setting each column to name `x`

`i`, where `i` is the index of this column, so the columns will be named `x0`

, `x1`

, `x2`

, etc.

char buff[10]; for (i=1; i<=glp_get_num_cols(lp); ++i) { snprintf(buff, sizeof(buff), "x%d", i-1); glp_set_col_name(lp, i, buff); }

for col in lp.cols: col.name = "x%d" % col.index

As with the problem and the objective function, one gets and sets the name for a row or column by querying or assigning the attribute `name`

.

Note the use of an index into the `rows`

or `cols`

collections to retrieve a particular row or columns. As with the C API, indices are integral, though we count from 0.

glp_set_row_name(lp, ri+1, "row name"); glp_set_col_name(lp, ci+1, "col name"); char *rname = glp_get_row_name(lp, ri+1); char *cname = glp_get_col_name(lp, ci+1);

lp.rows[ri].name = "row name" lp.cols[ci].name = "col name" rname = lp.rows[ri].name cname = lp.cols[ci].name

After the user names a row or column, they may index this row or column by its name.

lp.rows[ri].name = "xi" therow = lp.rows["xi"]

One gets and sets the bounds for a row or column by querying or assigning the attribute `bounds`

. To set bounds, one may assign one or two values to the `bounds`

, where values are either `None`

or numeric.

One `None`

(or two `None`

s) sets the row's auxiliary (or column's structural) variable unbounded. (One may also delete the bounds.) One numeric value (or two equal numeric values) sets an equality bound. In the case of two values, the first is interpreted as a lower bound, the second as an upper bound, with `None`

indicating unboundedness in that direction. Setting a lower bound greater than an upper bound causes a `ValueError`

.

In this code, we see instances of setting free (unbounded), lower, upper, double, and fixed (equality) bounds, respectively on a row and column.

glp_set_row_bnds(lp, ri+1, GLP_FR, 0, 0); glp_set_row_bnds(lp, ri+1, GLP_LO, 2, 0); glp_set_col_bnds(lp, ci+1, GLP_UP, 0, 5); glp_set_col_bnds(lp, ci+1, GLP_DB, -1, 3.14159); glp_set_row_bnds(lp, ri+1, GLP_FX, 3.4, 3.4);

lp.rows[ri].bounds = None # Or, lp.rows[ri].bounds = None, None # Or, del lp.rows[ri].bounds lp.rows[ri].bounds = 2, None lp.cols[ci].bounds = None, 5 lp.cols[ci].bounds = -1, 3.14159 lp.rows[ri].bounds = 3.4 # Or, lp.rows[ri].bounds = 3.4, 3.4

Accessing bounds always yields two values (again, either `None`

or numeric) representing lower and upper bounds respectively, even if the bounds resulted from either a single value assignment or a deletion. Again, `None`

represents unboundedness in that direction.

One gets and sets the entries of a row or column in the constraint matrix by querying or assigning the attribute `matrix`

. Assignments to `matrix`

will remove previous entries.

Retrieving `matrix`

will yield a list of two element tuples over the non-zero entries in this row or column, each of the form `(index, value)`

. The `index`

is the index (counting from 0) of the entry holding value `value`

in this row or column.

If we have an LPX object with `r` rows and `c` columns, then valid indices for rows are 0 through `c`−1, and valid entries for columns are 0 through `r`−1.

For example, suppose for an object `lp`

the row `r`_{2} (that is, row at index 2) encodes the constraint:

`p` = 10`x`_{0} − 3.14159`x`_{1} + 0.5`x`_{3}

Then `print lp.rows[2].matrix`

outputs `[(0, 10.0), (1, -3.14159), (3, 0.5)]`

.

One may set all non-zero entries of a row or column by assigning an iterable with similar structure to the `matrix`

attribute. Suppose our LPX object has `numr` rows and `numc` columns. The iterable must yield values each in one of these two forms:

- The integer-float tuple
`(index, value)`

which specifies that element`index`

should have value`value`

(note that negative indices are permitted in this context if you like) - The single float item
`value`

which specifies an object equivalent to`(index+1, value)`

where`index`

was the last index used in this iterable, or 0 if this is the first object in the iterable

For example, where one interested in defining (rather than simply retrieving) the entries of the constraint row used in the example above, if there are four columns, all of the following are equivalent:

# Define constraint p = 10*x0 - 3.14159*x1 + 0.5*x3 lp.rows[2].matrix = [(0, 10), (1, -3.14159), (3, 0.5)] lp.rows[2].matrix = [(0, 10), (1, -3.14159), (-1, 0.5)] lp.rows[2].matrix = [(1, -3.14159), (0, 10), (3, 0.5)] lp.rows[2].matrix = [10, -3.14159, 0, 0.5] lp.rows[2].matrix = [10, -3.14159, (-1, 0.5)] lp.rows[2].matrix = [10, -3.14159, (3, 0.5)]

Indices out of bounds will result in an `IndexError`

and duplicate indices will result in an `ValueError`

. Order does not matter, except of course for single value entries, as their index depends on the previous entry.

One may set all entries of a row or column in the constraint matrix to zero by assigning `None`

to or deleting the `matrix`

attribute.

One gets the number of non-zero constraint elements within a row or a column by querying the `nnz`

integer attribute.

int rnnz = glp_get_mat_row(lp, ri+1, NULL, NULL); int cnnz = glp_get_mat_col(lp, ci+1, NULL, NULL);

rnnz = lp.row[ri].nnz cnnz = lp.col[ci].nnz

To delete rows or columns, delete as one would from a typical Python list. Note the methods of indexing into the row and column collections. Accepted indices include single values, lists of values, or slices.

int indices1[] = { 2+1 }; glp_del_cols(lp, 1, indices1-1); int indices2[] = { 2+1,5+1,6+1 }; glp_del_rows(lp, 3, indices2-1); int indices3[] = { 3+1, 4+1, 5+1, 6+1 }; glp_del_cols(lp, 4, indices3-1);

del lp.cols[2] # Remove col indexed at 2 del lp.rows[2,5,6] # Remove rows indexed at 2,5,6 del lp.cols[3:7] # Remove cols indexed at 3,4,5,6

`scale`

attribute. Changing the scaling factor for row glp_set_rii(lp, 2, 3.14159); glp_set_sjj(lp, 4, 2.0); double row3scale = glp_get_rii(lp, 3); double col3scale = glp_get_sjj(lp, 3);

lp.rows[2].scale = 3.14159 lp.cols[4].scale = 2.0 row3scale = lp.rows[3].scale col3scale = lp.cols[3].scale

As is clear from the previous examples, row and column collections (e.g., as accessed by `lp.rows`

) and rows and columns (e.g., as accessed by `lp.rows[i]`

) as well as the rows and columns themselves are bona fide objects. (This was a design choice: rather than having only the LPX class where one defines a hundred or so get and set methods, as the C API must, one retrieves the rows and columns and operates on them instead.)

As a point of implementation, these row and column objects do not contain the row and column data. In reality, they just contain a pointer back to the LPX and an index. We shall see consequences of this in this subsection.

Aside from attributes which have obvious analogies to functions in the C API (e.g., `name`

with the `glp_[gs]et_(row|col)_name`

functions), rows and columns have other special attributes that do not have analogies in the C API which are exposed to Python users in the hope they may find them useful.

`index`

is an integer attribute containing the index of this row or column.

`valid`

is a boolean attribute containing whether this row or column is valid. A row or column may become invalid if its index points to somewhere beyond the current size of the LPX. This is mostly useless: one can track the size of the program, and even if you do not, using an out of date row or column safely throws exceptions.

`isrow`

and `iscol`

are boolean attributes indicating whether this is a row or a column. Naturally these two attributes are inverses of each other.

Example usage of these principles to elucidate these implementations is illustrated in this example. All assertions in this snippet are satisfied.

lp = glpk.LPX() lp.rows.add(3) lp.rows[0].name, lp.rows[1].name, lp.rows[2].name = 'p', 'q', 'r' row1, row2 = lp.rows[1], lp.rows[2] assert row1.name == 'q' and row2.name == 'r' del lp.rows[1] assert row1.name == 'r' and row1.valid and not row2.valid assert row1.isrow

One gets and sets the current basis status for a row or column by querying or assigning the attribute `status`

. This is a two-character string with the following possible values.

`bs`

meaning this row/column is basic.`nl`

meaning this row/column is non-basic.`nu`

meaning this row/column is non-basic and set to the upper bound. On assignment, if this row/column is not double bounded, this is equivalent to`nl`

.`nf`

meaning this row/column is non-basic and free. On assignment this is equivalent to`nl`

.`ns`

meaning this row/column is non-basic and fixed. On assignment this is equivalent to`nl`

.

if (glp_get_row_stat(lp, ri+1) == GLP_BS) printf("row is basic\n"); else printf("row is non-basic\n");

if lp.rows[ri].status == "bs": print "row is basic" else: print "row is non-basic"

As an example of setting the status, the user may wish to assign to this attribute in order to manually define the initial basis and not rely upon the automatic basis definition methods `lp.*_basis()`

. To illustrate this, here is the code within the GLPK standard basis code in both C and Python versions.

int i, j, m, n, type; double lb, ub; // all auxiliary variables are basic m = glp_get_num_rows(lp); for (i = 1; i <= m; i++) glp_set_row_stat(lp, i, GLP_BS); // all structural variables are non-basic n = glp_get_num_cols(lp); for (j = 1; j <= n; j++) { type = glp_get_col_type(lp, j); lb = glp_get_col_lb(lp, j); ub = glp_get_col_ub(lp, j); if (type != GLP_DB || fabs(lb) <= fabs(ub)) glp_set_col_stat(lp, j, GLP_NL); else glp_set_col_stat(lp, j, GLP_NU); }

# all auxiliary variables are basic for row in lp.rows: row.status = "bs" # all structural variables are non-basic for col in lp.cols: lb, ub = col.bounds if lb==None or ub==None or abs(lb)<=abs(ub): col.status = "nl" else: col.status = "nu"

One gets and sets the kind of variable (the default continuous, or integer) by querying or assigning the attribute `kind`

. This will hold either `float`

if this is a continuous variable, `int`

if this is an integer variable, or `bool`

if this is a binary variable.

glp_set_col_kind(lp, ci+1, GLP_CV); glp_set_col_kind(lp, ci+1, GLP_IV); glp_set_col_kind(lp, ci+1, GLP_BV); int kind = glp_get_col_kind(lp, ci+1);

lp.cols[ci].kind = float lp.cols[ci].kind = int lp.cols[ci].kind = bool kind = lp.cols[ci].kind

Note that PyGLPK and GLPK do not make any distinction between setting a column as binary, versus setting the column as integral with [0, 1] bounds.

Another note, rows must be continuous. As a matter of implementation, because they are the same type of object as columns, they may also be queried and assigned to in this fashion. However, their `kind`

attribute always returns and only accepts `float`

.

One gets a row or column's variable value by querying the `primal`

, `dual`

, or `value`

attribute.

double pval = glp_get_row_prim(ri+1); // if simplex double dval = glp_get_col_dual(ci+1);

pval = lp.rows[ri].primal dval = lp.cols[ci].dual

The two attributes `primal`

and `value`

are interchangeable. The term value is used to refer to the solutions of the MIP since it only has one type of value (no dual). However, since it is the same type of value (loosely speaking), this "link" between the two was established.

Note that unlike the C API, this remembers which solver was used last and retrieves the appropriate corresponding variable value. If for whatever reason you wish to retrieve a variable function from a solver type different from what you used last (e.g., reviewing the relaxed basic solution after calling `integer()`

), you can ask for `primal_s`

or `dual_s`

(for primals and duals from `simplex`

and `exact`

), or `primal_i`

or `dual_i`

(for primals and duals from `interior`

), or `value_m`

(for values from `integer`

or `intopt`

).

double prim_sim_row = glp_get_row_prim(lp, ri+1); double prim_sim_col = glp_get_col_prim(lp, ci+1); double dual_sim_row = glp_get_row_dual(lp, ri+1); double dual_sim_col = glp_get_col_dual(lp, ci+1); double prim_ipt_row = glp_ipt_row_prim(lp, ri+1); double prim_ipt_col = glp_ipt_col_prim(lp, ci+1); double dual_ipt_row = glp_ipt_row_dual(lp, ri+1); double dual_ipt_col = glp_ipt_col_dual(lp, ci+1); double valu_mip_row = glp_mip_row_val (lp, ri+1); double valu_mip_col = glp_mip_col_val (lp, ci+1);

prim_sim_row, prim_sim_col = lp.rows[ri].primal_s, lp.cols[ci].primal_s dual_sim_row, dual_sim_col = lp.rows[ri].dual_s, lp.cols[ci].dual_s prim_ipt_row, prim_ipt_col = lp.rows[ri].primal_i, lp.cols[ci].primal_i dual_ipt_row, dual_ipt_col = lp.rows[ri].dual_i, lp.cols[ci].dual_i valu_mip_row, valu_mip_col = lp.rows[ri].value_m, lp.cols[ci].value_m

In this section we describe the MIP solver callback interface, and the `Tree`

and `TreeNode`

objects supporting this interface for affecting the MIP solver.

One of the more esoteric parts of the GLPK mixed integer programming solver is the use of callbacks to let the user code affect the flow of the search process. Within PyGLPK, one can define a callback object which will be invoked at various parts of the algorithm, through the use of the optional `callback`

keyword parameter to the MIP solver, whose argument we will term `cb`

:

lp.integer(callback=cb)

What this `cb`

callback object is is not strictly defined, but this object `cb`

should respond to calls of the form `cb.`

, where *method*(tree)

is one of *method*`select`

, `prepro`

, `rowgen`

, `heur`

, `cutgen`

, `branch`

, or `bingo`

. These different methods represent the MIP solver seeking the callback object's input at various phases of the input. (If a method does not exist, PyGLPK will try the `default`

method instead, and if that does not exist, it will ignore the callback for that method.)

The `tree`

argument to these methods is a `Tree`

instance, a representation of the search tree of the method. The Tree instance contains data about the problem being solved.

void callback_func(glp_tree *tree, void *info) { switch (glp_ios_reason(tree)) { case GLP_ISELECT: // some code to select subproblems here... case GLP_IPREPRO: // some code for preprocessing here... case GLP_IROWGEN: // some code for providing constraints here... case GLP_IHEUR: // some code for providing heuristic solutions here... case GLP_ICUTGEN: // some code for providing constraints here... case GLP_IBRANCH: // some code to choose a variable to branch on here... case GLP_IBINGO: // some code to monitor the situation here... } } ... glp_iocp parm; glp_init_iocp(&parm); parm.cb_func = callback_func; glp_intopt(lp, &parm);

class Callback: def select(self, tree): # some code to select subproblems here... def prepro(self, tree): # some code for preprocessing here... def rowgen(self, tree): # some code for providing constraints here... def heur(self, tree): # some code for providing heuristic solutions here... def cutgen(self, tree): # some code for providing constraints here... def branch(self, tree): # some code to choose a variable to branch on here... def bingo(self, tree): # some code to monitor the situation here... lp.integer(callback=Callback())

The `Tree`

instance passed along to the function contains active subproblems being searched, where each subproblem corresponds to a `TreeNode`

instance.

Each of these seven phases of GLPK's implementation of the branch and cut algorithm correspond to these seven methods. By calling a particular method, the GLPK indicates that it desires some sort of input from the user. While a full description of the branch and cut algorithm is beyond the scope of this document (see the "Branch-and-cut interface routines" section of the "GNU Linear Programming Kit Reference Manual" that came with you GLPK distribution), and unfortunately a full understanding of what to do in each instance is beyond this author, we briefly describe the phases here, and what may be helpful in each instance to do what GLPK wants us to do.

Note that all operations are optional. One does not need to implement each method, and it is fine for a method to not do what is being requested: even just having a `pass`

statement in a method is fine. The GLPK has default behavior for all of the methods in case the user does not choose to affect the solution process.

`select`

, request for subproblem selection- There is no current node, so set one of the active subproblems as the current node with the
`tree.select`

method. The default behavior of the GLPK is to select the node with the best local bound, equivalent to this:def select(self, tree): tree.select(tree.best_node)

`prepro`

, request for preprocessing- The GLPK manual suggests that one may take advantage of this to perform preprocessing, perhaps of the form of tightening or loosening bounds of some variables, through modification of the
`tree.lp`

program object. `rowgen`

, request for row generation- When the current subproblem has been solved to optimality and the LP relaxation has been solved with a solution better than the best known integer feasible solution, this procedure may be called upon to add "lazy" constraints to the
`tree.lp`

, which is done as one normally adds rows (`tree.lp.rows.add(...)`

, and so on). `heur`

, request for a heuristic solution- When the current subproblem being solved to optimality is integer infeasible (i.e., some integer problems are fractional), though with a better objective value than the best known integer solution, one may call
`tree.heuristic(newsol)`

where`newsol`

is some iterable object (like a list, or an iterator) which can yield at least`len(tree.lp.cols)`

float values (with integral values for integral columns), to serve as the new primal values. (The method will check to see if it is better.) Note that feasibility of this solution is not checked by the method, so use caution. `cutgen`

, request for cut generation- Similar to
`rowgen`

, called when the subproblem being solved is integer infeasible but better than the best known integer solution, with the intent being that one adds constraints to cut off the current solution. `branch`

, request for branching- In the case of integer infeasibility, we have some integer variable (e.g., column) with non-integer value
`V`. Branching is the process of splitting this process by adding two subproblems to the active list with the column's value set to ⎣`V`⎦ and ⎡`V`⎤. For some column index`j`

, which we have confirmed we can branch upon with the`tree.can_branch`

method, we call the`tree.branch`

method with that index to add the two corresponding subproblems.def branch(self, tree): # Find the first fractional integer variable, and branch on it for j in xrange(len(tree.lp.cols)): if tree.can_branch(j): tree.branch(j) break

`bingo`

, better integer solution found- When the LP relaxation finds an integer feasible solution, this method is called. This is intended only for informational purposes, and should not modify any problem data.

One may retrieve the `LPX`

problem object used by the MIP solver with the `lp`

member, i.e., `tree.lp`

. This object is not necessarily the same `LPX`

instance as that for which we called `lp.integer()`

if some preprocessing was performed by the MIP solver.

Modification of the underlying LPX object is an important part of the callback procedures, especially in the `rowgen`

, `cutgen`

, and `prepro`

methods. It is important to note that not all operations you may perform on LPX objects within this callback are necessarily safe: modifying the problem object out from under the procedure in the middle of optimization might cause problems. However, it is difficult to distinguish a "problematic" change versus one which is helpful for, say, preprocessing, or computing cuts, or what have you.

In order to aid ease of use, the PyGLPK implements "generic" solution retrieval methods. For instance, an LP potentially has multiple objective function values: one for the last simplex solution `lp.obj.value_s`

, one for the last interior point solution `lp.obj.value_i`

, and one for the last MIP solution `lp.obj.value_m`

. However, there is also a `lp.obj.value`

, which sensibly supposes that a user is interested in the solution the solver (which covers the vast majority of use cases). However, in the midst of integer solution, the MIP solver hasn't yet become the "last" solver, so be sure to be explicit when retrieving values of columns and objective function values.

glp_prob *lp = glp_ios_get_prob(tree);

lp = tree.lp

The `Tree`

instance has many methods that allow one to affect the search process, as described earlier: `can_branch`

and `branch_upon`

to choose a column to set as integer, `heuristic`

to set a new integer feasible solution, `select`

to select an active subproblem for expansion, and `terminate`

to just terminate the solution outright.

glp_ios_can_branch(tree, 5+1); glp_ios_branch_upon(tree, 5+1, 'D'); double *values; glp_ios_heur_sol(tree, values) glp_ios_select_node(tree, node_num); glp_ios_terminate(tree);

tree.can_branch(5) tree.branch_upon(5, 'D') tree.heuristic(values) tree.select(node) tree.terminate()

The tree instance contains an active subproblem list, corresponding to current entries in the search tree which have not yet been explored. The tree contains several members that let one access the tree nodes, corresponding to subproblems in the list:

`curr_node`

, the current active subproblem's node, which will be`None`

in the selection phase when there is no current subproblem.`first_node`

, the first node in the active subproblem list.`last_node`

, the last node in the active subproblem list.`best_node`

, the node whose active subproblem has the best local bound.

For instance:

int node_num; node_num = glp_ios_curr_node(tree); node_num = glp_ios_next_node(tree, 0); node_num = glp_ios_prev_node(tree, 0); node_num = glp_ios_best_node(tree);

node = tree.curr_node node = tree.first_node node = tree.last_node node = tree.best_node

One may also iterate over `tree`

to get all of the nodes in the active list.

In addition to `Tree`

members, each `TreeNode`

has members to connect them to other `TreeNode`

objects in the tree.

`next`

, which gets the next active subproblem's node, or`None`

if this is the last active node or an inactive node.`prev`

, which gets the previous active subproblem's node, or`None`

if this is the first active node or an inactive node.`up`

, which gets the parent node that generated this node, or`None`

if this is the root node.`level`

, which is this node's distance from the root,`0`

if this is the root node`subproblem`

, which is the integral subproblem number, assigned in order from 1 onwards.

int other_node_num, lev; other_node_num = glp_ios_next_node(tree, node_num); other_node_num = glp_ios_prev_node(tree, node_num); other_node_num = glp_ios_up_node(tree, node_num); lev = glp_ios_node_level(tree, node_num); // node_num is the subproblem id number

other_node = node.next other_node = node.prev other_node = node.up other_node = node.level subproblem_num = node.subproblem

One may get the tree size through the use of various members.

`num_active`

, the number of active nodes.`num_all`

, the number of active and inactive nodes in the tree.`num_total`

, the number of nodes which were generated, active, inactive, and those nodes which have already been removed.

int count; glp_ios_tree_size(tree, &count, NULL, NULL); glp_ios_tree_size(tree, NULL, &count, NULL); glp_ios_tree_size(tree, NULL, NULL, &count);

count = tree.num_active count = tree.num_all count = tree.num_total

One may get the current relative gap between the integer and relaxed solution with the `gap`

member.

double gap = glp_ios_mip_gap(tree);

gap = tree.gap

One may get the lower (in minimization) or upper (in maximization) bound on the integer optimal solution to a node's subproblem with the `bound`

member of a `TreeNode`

instance.

double bound = glp_ios_node_bound(tree, node_num);

bound = node.bound

The `Tree`

member `reason`

holds a string indicating the reason why the callback was invoked. While the reason for the callback is the same as the method name called in the callback (e.g., `select`

is called only if `tree.reason='select'`

), if one implements the `default`

method in lieu of specific methods, one may wish to extract the reason with this member.

int reasoncode = glp_ios_reason(tree);

reason = tree.reason

Contained within `glpk.env`

object is an `Environment`

instance, through which one controls the global behavior of the GLPK routines.

In the environment is a tuple `version`

that reflects the version of GLPK that the build process believed it was linking against at compilation time. For example, if the module believed it was linking against GLPK 4.31, the tuple would be `(4, 31)`

.

printf("GLPK version is %s\n", glp_version());

print 'GLPK version is %d.%d\n' % glpk.env.version

The GLPK monitors its own memory use, and this information can be retrieved from these members of the `glpk.env`

object. The `blocks`

member holds the current number of allocated memory blocks, while `blocks_peak`

holds the maximum this ever reached. The `bytes`

and `bytes_peak`

members are similar, except for bytes. Note that blocks are not a particular size, but are multiple

int blocks, blocks_peak; glp_long bytes, bytes_peak; glp_mem_usage(&blocks, &blocks_peak, &bytes, &bytes_peak);

blocks = glpk.env.blocks blocks_peak = glpk.env.blocks_peak bytes = glpk.env.bytes bytes_peak = glpk.env.bytes_peak

One may also set the maximum number of megabytes with the `mem_limit`

member.

glp_mem_limit(50);

glpk.env.mem_limit = 50

The GLPK has many functions that produce output. The user may at their option turn off or on the output by setting the environment's `term_on`

attribute to `False`

or `True`

.

glp_term_out(GLP_OFF); glp_term_out(GLP_ON);

glpk.env.term_on = False glpk.env.term_on = True

In addition to turning it on and off, one may enable more fine grained control by intercepting all terminal output with a function hook. The function will be called with a single string argument whenever the GLPK chooses to print something. Note that this will intercept only that output which is produced by the GLPK itself -- other output from Python will be completely unaffected.

int term_hook(void *info, const char *output) { FILE *logfile = (FILE *)info; fputs(output, logfile); return 1; } ... FILE *lf = fopen("glpk_logfile.txt", "w"); glp_term_hook(term_hook, (void*)lf);

logfile = file('glpk_logfile.txt', 'w') def term_hook(output): file.write(output) glpk.env.term_hook = term_hook

One may remove the terminal hook function (e.g., resume default terminal output) by assigning the value `None`

.

glp_term_hook(NULL, NULL);

glpk.env.term_hook = None

The linear program object has the ability to return a `KKT`

type objects with which the user may evaluate the fitness of either simplex or MIP solutions.

One can compute and retrieve these conditions for simplex solvers with the `kkt`

and for integer solvers with the `kktint`

methods. The `kkt`

method has an optional argument that allows one to specify whether one wants to compute the conditions for the internally scaled version of the problem (by default false).

LPXKKT kkt, skkt, ikkt; lpx_check_kkt(lp, 0, &kkt); // unscaled simplex KKT lpx_check_kkt(lp, 1, &skkt); // scaled simplex KKT lpx_check_int(lp, &ikkt); // integer conditions

kkt = lp.kkt() # unscaled simplex KKT skkt = lp.kkt(True) # scaled simplex KKT ikkt = lp.kktint() # integer conditions

These objects have KKT statistics about the absolute and relative errors and worst rows and columns in the primal and (in the case of non-integer problems) dual solutions. See the inline help for more information about these fields.

In addition to this documentation, like most Python objects, the objects have built in inline help, accessible from an interactive Python session. For example, to access the built in documentation for the `glpk`

module:

help(glpk)

Thomas Finley, 2007, 2008