Reference

The PyGLPK module, encapsulating the functionality of the GNU Linear Programming Kit. Usage of this module will typically start with the initialization of an LPX instance to define a linear program, and proceed from there to add data to the problem and ultimately solve it. See help on the LPX class, as well as the HTML documentation accompanying your PyGLPK distribution.

class glpk.Bar

Bar objects are used to refer to a particular row or column of a linear program. Rows and columns may be retrieved by indexing into the rows and cols sequences of LPX instances.

bounds

The lower and upper bounds, where None signifies unboundedness.

dual

The dual value of this variable by the last solver.

dual_i

The dual value of this variable by the interior-point solver.

dual_s

The dual value of this variable by the simplex solver.

eval_tab_col() → [(Bar, float), ...]

Returns the column of the current simplex tableau for this variable. The column is returned as a list of tuples containing a reference to a basic variable and the corresponding coefficient from the simplex tableau

If this variable is basic, this method throws a ValueError.

eval_tab_row() → [(Bar, float), ...]

Returns the row of the current simplex tableau for this variable. The row is returned as a list of tuples containing a reference to a non-basic variable and the corresponding coefficient from the simplex tableau.

If this variable is non-basic, this method throws a ValueError.

index

The index of the row or column this object refers to.

iscol

Whether this is a column.

isrow

Whether this is a row.

kind

Either the type ‘float’ if this is a continuous variable, ‘int’ if this is an integer variable, or ‘bool’ if this is a binary variable.

matrix

Non-zero constraint coefficients in this row/column vector as a list of two-element (index, value) tuples.

name

Row/column symbolic name, or None if unset.

nnz

Number of non-zero constraint elements in this row/column.

primal

The primal value of this variable by the last solver.

primal_i

The primal value of this variable by the interior-point solver.

primal_s

The primal value of this variable by the simplex solver.

scale

The scale for the row or column. This is a factor which one may set to improve conditioning in the problem. Most users will want to use the LPX.scale() method rather than setting these directly. The resulting constraint matrix is such that the entry at row i and column j is (for the purpose of optimization) (ri)*(aij)*(sj) where ri and sj are the row and column scaling factors, and aij is the entry of the constraint matrix.

status

Row/column basis status

This is a two character string with the following possible values:

bs

This row/column is basic.

nl

This row/column is non-basic.

nu

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

This row/column is non-basic and free. On assignment this is equivalent to ‘nl’.

ns

This row/column is non-basic and fixed. On assignment this is equivalent to ‘nl’.

valid

Whether this row or column has a valid index in its LP.

value

The value of this variable by the last solver.

value_m

The value of this variable by the MIP solver.

class glpk.BarCollection

Bar collection objects

An instance is used to index into either the rows and columns of a linear program. They exist as the ‘rows’ and ‘cols’ attributes of LPX instances.

One accesses particular rows or columns by indexing the appropriate bar collection object, or iterating over it. Valid indices include particular row and column names (a user defined string) or numbers (counting from 0), a slice specifying a range of numeric elements, or a series of individual indices. For example, for an LPX instance lp, we may have:

lp.rows[0]          # the first row
lp.rows[-1]         # the last row
lp.cols[:3]         # the first three columns
lp.cols[1,'name',5] # column 1, a column named 'name', and column 5

One may also query the length of this sequence to get the number of rows or columns, and del to get rid of rows or columns, e.g.:

len(lp.cols)        # the number of columns in the problem
del lp.rows['arow'] # deletes a row named 'arow'
del lp.rows[-2:]    # deletes the last two rows

add(n)

Add n more rows (constraints) or columns (struct variables). Returns the index of the first added entry.

class glpk.BarCollectionIter

Bar collection iterator objects

Created for iterating over the rows and columns contained with a bar collection.

class glpk.Environment

This represents the PyGLPK environment. Through this, one may control the global behavior of the GLPK. One instance of this exists, named env in the glpk module.

blocks

The number of currently allocated memory blocks.

blocks_peak

The peak value of the blocks attribute.

bytes

The number of currently allocated memory bytes.

bytes_peak

The peak value of the bytes attribute.

mem_limit

The memory limit in megabytes. None if no limit is set.

term_hook

Function to intercept all terminal output. This should be a callable object that accepts a single string argument, or None to indicate that no hook is set (e.g., all output goes to the terminal, default behavior). Note that when the function is called, there is no guarantee that the input string will be a full line, or even non-empty. All exceptions thrown by the function will go ignored and unreported.

term_on

Whether or not terminal output for the underlying GLPK procedures is on or off.

version

Tuple holding the major version and minor version of the GLPKthat this PyGLPK module was built upon. For example, if built against GLPK 4.31, version==(4,31).

class glpk.KKT

Karush-Kuhn-Tucker conditions.

This is returned from a check on quality of solutions. Four types of conditions are stored here:

• KKT.PE conditions are attributes prefixed by ‘pe’ measuring error in the primal solution.
• KKT.PB conditions are attributes prefixed by ‘pb’ measuring error in satisfying primal bound constraints, i.e., feasibility.
• KKT.DE and KKT.DB are analogous, but for the dual.

db_ae_ind

Index of the variable with the largest absolute error.

db_ae_max

Largest absolute error.

db_quality

Character representing the quality of primal feasibility. ‘H’, high, ‘M’, medium, ‘L’, low, or ‘?’ wrong or infeasible.

db_re_ind

Index of the variable with the largest relative error.

db_re_max

Largest relative error.

de_ae_max

Largest absolute error.

de_ae_row

Index of the column with the largest absolute error.

de_quality

Character representing the quality of the primal solution. ‘H’, high, ‘M’, medium, ‘L’, low, or ‘?’ wrong or infeasible.

de_re_max

Largest relative error.

de_re_row

Index of the column with the largest relative error.

pb_ae_ind

Index of the variable with the largest absolute error.

pb_ae_max

Largest absolute error.

pb_quality

Character representing the quality of primal feasibility. ‘H’, high, ‘M’, medium, ‘L’, low, or ‘?’ wrong or infeasible.

pb_re_ind

Index of the variable with the largest relative error.

pb_re_max

Largest relative error.

pe_ae_max

Largest absolute error.

pe_ae_row

Index of the row with the largest absolute error.

pe_quality

Character representing the quality of the primal solution. ‘H’, high, ‘M’, medium, ‘L’, low, or ‘?’ wrong or infeasible.

pe_re_max

Largest relative error.

pe_re_row

Index of the row with the largest relative error.

class glpk.LPX → empty linear program

LPX(gmp=filename) -> linear program with data read from a GNU MathProg file

containing model and data

LPX(mps=filename) -> linear program with data read from a datafile in fixed

MPS format

LPX(freemps=filename) -> linear program with data read from a datafile in

free MPS format

LPX(cpxlp=filename) -> linear program with data read from a datafile in

fixed CPLEX LP format

LPX(glp=filename) -> linear program with data read from a datafile in GNU

LP format

LPX(gmp=(model_filename[, data_filename[, output_filename]]) -> linear

program from GNU MathProg input files. The first element is a path to model second, the second to the data section. If the second element is omitted or is None then the model file is presumed to also hold the data. The third element holds the output data file to write display statements to. If omitted or None, the output is instead put through to standard output.

This represents a linear program object. It holds data and offers methods relevant to the whole of the linear program. There are many members in this class, but the most important are: obj -> represents the objective function rows -> a collection over which one can access rows cols -> same, but for columns

adv_basis()

Construct an advanced initial basis, triangular with as few variables as possible fixed.

cols

Column collection. See the help on class BarCollection.

copy()

Copies the content of this problem into a new problem and returns it.

cpx_basis()

Construct an advanced Bixby basis. This basis construction method is described in: Robert E. Bixby. Implementing the Simplex Method: The Initial Basis. ORSA Journal on Computing, Vol. 4, No. 3, 1992, pp. 267-84.

dual_ratio_test([(glpk.Bar, float), int, float]) → int

Perform dual ratio test using an explicitly specified row of the simplex tableau.

The row of the simplex tableau is given as a list of tuples, with each tuple containing a basic variable and a coefficient. The second argument is an integer specifying the direction in which the variable changes when entering the basis: +1 means increasing, -1 means decreasing. The third argument is an absolute tolerance used by the routine to skip small coefficients.

Returns the index of the input row corresponding to the pivot element.

erase()

Erase the content of this problem, restoring it to the state it was in when it was first created.

exact()

Attempt to solve the problem using an exact simplex method.

This returns None if the problem was successfully solved. Alternately, on failure it will return one of the following strings to indicate failure type:

fault

There are no rows or columns, or the initial basis is invalid, or the initial basis matrix is singular or ill-conditioned.

itlim

Iteration limited exceeded.

tmlim

Time limit exceeded.

integer()

MIP solver based on branch-and-bound.

This procedure has a great number of optional keyword arguments to control the functioning of the solver. We list these here, including descriptions of their legal values:

msg_lev

Controls the message level of terminal output.

LPX.MSG_OFF

no output (default)

LPX.MSG_ERR

error and warning messages

LPX.MSG_ON

normal output

LPX.MSG_ALL

full informational output

br_tech

Branching technique option.

LPX.BR_FFV

first fractional variable

LPX.BR_LFV

last fractional variable

LPX.BR_MFV

most fractional variable

LPX.BR_DTH

heuristic by Driebeck and Tomlin (default)

LPX.BR_PCH

hybrid pseudo-cost heuristic

bt_tech

Backtracking technique option.

LPX.BT_DFS

depth first search

LPX.BT_BFS

breadth first search

LPX.BT_BLB

best local bound (default)

LPX.BT_BPH

best projection heuristic

pp_tech

Preprocessing technique option.

LPX.PP_NONE

disable preprocessing

LPX.PP_ROOT

perform preprocessing only on the root level

LPX.PP_ALL

perform preprocessing on all levels (default)

sr_heur

Simple rounding heuristic (default True) (requires glpk >= 4.57.0)

fp_heur

Feasibility pump heurisic (default False)

ps_heur

Proximity search heuristic (default False)

ps_tm_lim

Proximity search time limit in milliseconds (default 60000)

gmi_cuts

Use Gomory’s mixed integer cuts (default False)

mir_cuts

Use mixed integer rounding cuts (default False)

cov_cuts

Use mixed cover cuts (default False)

clq_cuts

Use clique cuts (default False)

tol_int

Tolerance used to check if the optimal solution to the current LP relaxation is integer feasible.

tol_obj

Tolerance used to check if the objective value in the optimal solution to the current LP is not better than the best known integer feasible solution.

mip_gap

elative mip gap tolerance (default 0.0)

tm_lim

Search time limit in milliseconds. (default is max int)

out_frq

Terminal output frequency in milliseconds. (default 5000)

out_dly

Terminal output delay in milliseconds. (default 10000)

presolve

MIP presolver (default False)

binarize

Binarization option, used only if presolver is enabled (default False)

callback

A callback object the user may use to monitor and control the solver. During certain portions of the optimization, the solver will call methods of callback object. (default None)

The last parameter, callback, is worth its own discussion. During the branch-and-cut algorithm of the MIP solver, at various points callback hooks are invoked which allow the user code to influence the proceeding of the MIP solver. The user code may influence the solver in the hook by modifying and operating on a Tree instance passed to the hook. These hooks have various codes, which we list here:

select

request for subproblem selection

prepro

request for preprocessing

rowgen

request for row generation

heur

request for heuristic solution

cutgen

request for cut generation

branch

request for branching

bingo

better integer solution found

During the invocation of a hook with a particular code, the callback object will have a method of the same name as the hook code called, with the Tree instance. For instance, for the ‘cutgen’ hook, it is equivalent to:

callback.cutgen(tree)

being called with tree as the Tree instance. If the method does not exist, then instead the method ‘default’ is called with the same signature. If neither the named hook method nor the default method exist, then the hook is ignored.

This method requires a mixed-integer problem where an optimal solution to an LP relaxation (either through simplex() or exact()) has already been found. Alternately, try intopt().

This returns None if the problem was successfully solved. Alternately, on failure it will return one of the following strings to indicate failure type.

fault

There are no rows or columns, or it is not a MIP problem, or integer variables have non-int bounds.

nopfs

No primal feasible solution.

nodfs

Relaxation has no dual feasible solution.

itlim

Iteration limited exceeded.

tmlim

Time limit exceeded.

sing

Error occurred solving an LP relaxation subproblem.

interior()

Attempt to solve the problem using an interior-point method.

This returns None if the problem was successfully solved. Alternately, on failure it will return one of the following strings to indicate failure type:

fault

There are no rows or columns.

nofeas

The problem has no feasible (primal/dual) solution.

noconv

Very slow convergence or divergence.

itlim

Iteration limited exceeded.

instab

Numerical instability when solving Newtonian system.

intopt()

More advanced MIP branch-and-bound solver than integer(). This variant does not require an existing LP relaxation.

This returns None if the problem was successfully solved. Alternately, on failure it will return one of the following strings to indicate failure type.

fault

There are no rows or columns, or it is not a MIP problem, or integer variables have non-int bounds.

nopfs

No primal feasible solution.

nodfs

Relaxation has no dual feasible solution.

itlim

Iteration limited exceeded.

tmlim

Time limit exceeded.

sing

Error occurred solving an LP relaxation subproblem.

kind

Either the type ‘float’ if this is a pure linear programming (LP) problem, or the type ‘int’ if this is a mixed integer programming (MIP) problem.

kkt([scaled=False])

Return an object encapsulating the results of a check on the Karush-Kuhn-Tucker optimality conditions for a basic (simplex) solution. If the argument ‘scaled’ is true, return results of checking the internal scaled instance of the LP instead.

kktint()

Similar to kkt(), except analyzes solution quality of an mixed-integer solution. Note that only the primal components of the KKT object will have meaningful values.

matrix

The constraint matrix as a list of three element (row index, column index, value) tuples across all non-zero elements of the constraint matrix.

name

Problem name, or None if unset.

nbin

The number of binary column variables, i.e., integer with 0 to 1 bounds. Always 0 if this is not a mixed integer problem.

nint

The number of integer column variables. Always 0 if this is not a mixed integer problem.

nnz

Number of non-zero constraint coefficients.

obj

Objective function object.

prime_ratio_test([(glpk.Bar, float), int, float]) → int

Perform primal ratio test using an explicitly specified column of the simplex tableau.

The column of the simplex tableau is given as a list of tuples, with each tuple containing a basic variable and a coefficient. The second argument is an integer specifying the direction in which the variable changes when entering the basis: +1 means increasing, -1 means decreasing. The third argument is an absolute tolerance used by the routine to skip small coefficients.

Returns the index of the input column corresponding to the pivot element.

ray

A non-basic row or column the simplex solver has identified as causing primal unboundness, or None if no such variable has been identified.

rows

Row collection. See the help on class BarCollection.

scale([flags=LPX.SF_AUTO])

Perform automatic scaling of the problem data, in order to improve conditioning. The behavior is controlled by various flags, which can be bitwise ORed to combine effects. Note that this only affects the internal state of the LP representation. These flags are members of the LPX class:

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

simplex([keyword arguments])

Attempt to solve the problem using a simplex method.

This procedure has a great number of optional keyword arguments to control the functioning of the solver. We list these here, including descriptions of their legal values.

msg_lev

Controls the message level of terminal output.

LPX.MSG_OFF

no output (default)

LPX.MSG_ERR

error and warning messages

LPX.MSG_ON

normal output

LPX.MSG_ALL

full informational output

meth

Simplex method option

LPX.PRIMAL

use two phase primal simplex (default)

LPX.DUAL

use two phase dual simplex

LPX.DUALP

use two phase dual simplex, primal if that fails

pricing

Pricing technique

LPX.PT_STD

standard textbook technique

LPX.PT_PSE

projected steepest edge (default)

r_test

Ratio test technique

LPX.RT_STD

standard textbook technique

LPX.RT_HAR

Harris’ two-pass ratio test (default)

tol_bnd

Tolerance used to check if the basic solution is primal feasible. (default 1e-7)

tol_dj

Tolerance used to check if the basic solution is dual feasible. (default 1e-7)

tol_piv

Tolerance used to choose pivotal elements of the simplex table. (default 1e-10)

obj_ll

Lower limit of the objective function. The solver terminates upon reaching this level. This is used only in dual simplex optimization. (default is min float)

obj_ul

Upper limit of the objective function. The solver terminates upon reaching this level. This is used only in dual simplex optimization. (default is max float)

it_lim

Simplex iteration limit. (default is max int)

tm_lim

Search time limit in milliseconds. (default is max int)

out_frq

Terminal output frequency in iterations. (default 200)

out_dly

Terminal output delay in milliseconds. (default 0)

presolve

Use the LP presolver. (default False)

This returns None if the problem was successfully solved. Alternately, on failure it will return one of the following strings to indicate failure type.

fault

There are no rows or columns, or the initial basis is invalid, or the initial basis matrix is singular or ill-conditioned.

objll

The objective reached its lower limit.

objul

The objective reached its upper limit.

itlim

Iteration limited exceeded.

tmlim

Time limit exceeded.

sing

The basis matrix became singular or ill-conditioned.

nopfs

No primal feasible solution. (Presolver only.)

nodfs

No dual feasible solution. (Presolver only.)

status

The status of solution of the last solver.

This takes the form of a string with these possible values:

opt

The solution is optimal.

undef

The solution is undefined.

feas

The solution is feasible, but not necessarily optimal.

infeas

The solution is infeasible.

nofeas

The problem has no feasible solution.

unbnd

The problem has an unbounded solution.

status_dual

The status of the dual solution of the simplex solver.

Possible values are ‘undef’, ‘feas’, ‘infeas’, ‘nofeas’ in similar meaning to the .status attribute.

status_i

The status of the interior point solver’s solution.

status_m

The status of the MIP solver’s solution.

status_primal

The status of the primal solution of the simplex solver.

Possible values are ‘undef’, ‘feas’, ‘infeas’, ‘nofeas’ in similar meaning to the .status attribute.

status_s

The status of the simplex solver’s solution.

std_basis()

Construct the standard trivial inital basis for this LP.

transform_col([(glpk.Bar, float), ...]) → [(glpk.Bar, float), ...]

Transforms the explicitly specified column

The column to be transformed is given as a list of tuples, with each tuple containing a variable (i.e., an instance of glpk.Bar) and a coefficient. The input variables should be auxiliary variables (i.e., elements of LPX.rows).

The column is returned as a list of tuples containing a reference to a basic variable and the corresponding coefficient from the simplex tableau.

transform_row([(glpk.Bar, float), ...]) → [(glpk.Bar, float), ...]

Transforms the explicitly specified row

The row to be transformed is given as a list of tuples, with each tuple containing a variable (i.e., an instance of glpk.Bar) and a coefficient. The input variables should be structural variables (i.e., elements of LPX.cols).

The row is returned as a list of tuples containing a reference to a non-basic variable and the corresponding coefficient from the simplex tableau.

unscale()

This unscales the problem data, essentially setting all scale factors to 1.

warm_up() → string

Warms up the LP basis.

Returns None if successful, otherwise one of the following error strings:

badb

the basis matrix is invalid

sing

the basis matrix is singular

cond

the basis matrix is ill-conditioned

write(format=filename)

Output data about the linear program into a file with a given format. What data is written, and how it is written, depends on which of the format keywords are used. Note that one may specify multiple format and filename pairs to write multiple types and formats of data in one call to this function.

mps

For problem data in the fixed MPS format.

bas

The current LP basis in fixed MPS format.

freemps

Problem data in the free MPS format.

cpxlp

Problem data in the CPLEX LP format.

glp

Problem data in the GNU LP format.

sol

Basic solution in printable format.

sens_bnds

Bounds sensitivity information.

ips

Interior-point solution in printable format.

mip

MIP solution in printable format.

class glpk.Objective

Objective function objects for linear programs.

An instance is used either to access objective function values for solutions, or to access or set objective function coefficients. The same indices valid for a BarCollection object over the columns (that is, column numeric indices, column names, slices, multiple values) are also valid for indexing into this object. The special index None is used to specify the shift term. If we have an LPX instance lp, we may have:

lp.obj[0]    # the first objective coefficient
lp.obj[None] # the shift term
lp.obj[-3:]  # the last three objective coefficients

lp.obj[1, 4] # the objective coefficients 1, 4

When assigning objective coefficients, for single indices one may assign a single number. For multiple indices, one may assign a single number to make all indicated coefficients identical, or specify an iterable of equal length to set them all individiaully. For example:

lp.obj[0] = 2.5          # set the first objective coef to 2.5
lp.obj[-3:] = 1.0        # the last three obj coefs get 1.0
lp.obj[1, 4] = -2.0, 2.0 # obj coefs 1, 4 get -2.0, 2.0

maximize

True or False depending on whether we are trying to maximize or minimize this objective function, respectively.

name

Objective name, or None if unset.

shift

The constant shift term of the objective function.

value

The current value of the objective function.

value_i

The current value of the interior point objective function.

value_m

The current value of the MIP objective function.

value_s

The current value of the simplex objective function.

class glpk.ObjectiveIter

Objective function iterator objects, used to cycle over the coefficients of the objective function.

class glpk.Tree

Tree instances are passed to MIP solver callback function.

They are used to indicate the state of the solver at some intermediate point in a call to LPX.integer(). There are nodes within the tree, instances of TreeNode, corresponding to subproblems within the search tree. The currently active subproblem is stored in the curr_node member of an instance.

best_node

The node of the current active subproblem with best local bound. If the tree is empty, this is None.

branch_upon(col_index, select='N')

Given the index of a column in the LP, this will add two new subproblems, down and up branches (in that order) to the active list, where the down and up branches are the problems with the column’s variable set to the floor and ceil of the value, respectively. The select parameter controls which of the two branches is selected to next continue the search with ‘D’, ‘U’, and ‘N’ corresponding to choosing the down, up, or letting GLPK select a branch, respectively.

can_branch(col_index)

Given the index of a column in the LP, this will return True if one can branch upon this column’s varible, that is, continue the search with this column’s variable set as an integer. Note that this function should be called only when the reason member of the tree is ‘branch’.

curr_node

The node of the current active subproblem. If there is no current active subproblem in the tree, this will return None.

first_node

The node of the first active subproblem. If there is no current active subproblem in the tree, this is None.

gap

The relative MIP gap (duality gap), that is, the gap between the best MIP solution (best_mip) and best relaxed solution (best_bnd) given by this formula:

|best_mip - best_bnd|

gap = ———————

|best_mip| + epsilon

heuristic(values)

Provide an integer feasible solution of the primal problem, where values is an iterable object yielding at least as many float values as there are columns in the problem. If the provided solution is better than the existing one, the solution is accepted and the problem updated. This function returns True or False depending on whether the solution was accepted or not. Note that this function should be called only when the reason member of the tree is ‘heur’.

last_node

The node of the last active subproblem. If there is no current active subproblem in the tree, this is None.

lp

Problem object used by the MIP solver.

num_active

The number of active nodes.

num_all

The number of all nodes, both active and inactive.

num_total

The total number of nodes, including those already removed.

reason

A string with the reason the callback function has been called.

select(node)

Selects a tree node to continue search from. Note that this function should be called only when the reason member of the tree is ‘select’.

terminate()

Prematurely terminate the MIP solver’s search.

class glpk.TreeIter

Tree iterator objects.

Created for iterating over the active subproblems of the search tree.

class glpk.TreeNode

Represent specific subproblem instances in the search Tree object used by the MIP solver.

active

Whether this node represents an active subproblem.

bound

The local bound for this node’s subproblem.

level

The level of the node in the tree, with 0 if this is the root.

next

The next active subproblem node, None if there is no next active subproblem, or if this is not an active subproblem.

prev

The previous active subproblem node, None if there is no previous active subproblem, or if this is not an active subproblem.

subproblem

The reference number of the subproblem corresponding to this node.

up

The parent subproblem node, None if this is the root.