lemke.lemke#

Lemke’s algorithm for solving linear complementarity problems (LCPs).

Functions

`outstatistics`(tableau)	Helper to output statistics of minimum ratio test.
`result_from_tableau`(tableau, success[, ...])
`runlemke`(*, lcp[, callback])	Solve an LCP using Lemke's complementary pivoting algorithm.

Classes

`LcpResult`(success, num_pivots, basis, z0, z, ...)
`LemkeCallback`()	Callback interface for observing the progress of runlemke.
`PrintingCallback`([stream, verbose, z0, lexstats])	A LemkeCallback that prints tableaus and progress to a stream.
`lcp`(M, q, d)	A linear complementarity problem instance (M, q, d).
`tableau`(Mqd)	The tableau used to run Lemke's pivoting algorithm.

Exceptions

RayTermination(enter, tableau)

Raised when Lemke's algorithm can't find a solution and terminates on a secondary ray.

class lemke.lemke.LcpResult(success: bool, num_pivots: int, basis: frozenset[str], z0: fractions.Fraction, z: tuple[fractions.Fraction, ...], w: tuple[fractions.Fraction, ...], ray_entering_variable: str | None)[source]#

basis: frozenset[str]#

num_pivots: int#

ray_entering_variable: str | None#

success: bool#

w: tuple[Fraction, ...]#

z: tuple[Fraction, ...]#

z0: Fraction#

class lemke.lemke.LemkeCallback[source]#

Callback interface for observing the progress of runlemke.

Subclass and override any of these methods to log, print, or otherwise react to the algorithm’s progress (e.g. PrintingCallback). All methods are no-ops by default.

Each pivot triggers on_pivot_start. Every pivot except the last of a successful run is followed by on_pivot_end; the final pivot, which makes z0 leave the basis, is followed by on_done instead. No callbacks are invoked when q >= 0, since no pivoting is needed.

on_done(tableau, result)[source]#: Called once a complementary solution is found, with the final LcpResult.

on_negcol(tableau)[source]#: Called after the RHS column is negated to start pivoting.

on_pivot_end(tableau)[source]#: Called after each pivot completes, except the final one of a successful run (see on_done).

on_pivot_start(tableau, leave, enter)[source]#: Called before each pivot, with the chosen leave/enter variables.

on_ray_termination(tableau, result, message)[source]#: Called if the algorithm terminates on a secondary ray, with the (unsuccessful) LcpResult and the termination message.

on_start(lcp, tableau)[source]#: Called once, after the initial tableau is built.

class lemke.lemke.PrintingCallback(stream=<_io.TextIOWrapper name='<stdout>' mode='w' encoding='utf-8'>, verbose=False, z0=False, lexstats=False)[source]#

A LemkeCallback that prints tableaus and progress to a stream.

Parameters:

stream (file-like, optional) – Where to print output. Default is sys.stdout.
verbose (bool, optional) – If True, print the full tableau after every pivot, not just at the start and end. Default is False.
z0 (bool, optional) – If True, print the current value of z0 before each pivot. Default is False.
lexstats (bool, optional) – If True, print lexicographic minimum-ratio test statistics when the algorithm finishes successfully. Default is False.

on_done(tableau, result)[source]#: Print the final tableau, the result, and lex-stats if lexstats is set.

on_negcol(tableau)[source]#: Print the tableau after negating the RHS column, if verbose.

on_pivot_end(tableau)[source]#: Print the tableau after the pivot completes, if verbose.

on_pivot_start(tableau, leave, enter)[source]#: Print the chosen leaving/entering variables, and z0’s value if z0 is set.

on_ray_termination(tableau, result, message)[source]#: Print the ray-termination message, tableau, and the (unsuccessful) result.

on_start(lcp, tableau)[source]#: Print the LCP instance and the initial tableau.

printout(*args)[source]#: Print args to this callback’s stream.

exception lemke.lemke.RayTermination(enter, tableau)[source]#

Raised when Lemke’s algorithm can’t find a solution and terminates on a secondary ray.

Parameters:

enter (int) – The variable that could not enter the basis (no positive pivot candidate).
tableau (tableau) – The tableau at the point of termination.

tableau#

The incomplete tableau at termination.

Type:: tableau

class lemke.lemke.lcp(M, q, d)[source]#

A linear complementarity problem instance (M, q, d).

Represents the LCP \(w = q + Mz,\ w, z \ge 0,\ z^T w = 0\), together with a covering vector d used to start Lemke’s algorithm.

Can be constructed directly from M, q, d, or via from_file for problems stored in the LCP file format.

Parameters:

M (list of list of int or fractions.Fraction) – Square matrix of shape (n, n), given as the list of its n rows, so M[i][j] is the entry in row i and column j.
q (list of int or fractions.Fraction) – Vector of length n.
d (list of int or fractions.Fraction) – Covering vector of length n.
numerator (Entries must be exact rationals (anything with integer)
denominator (and)
fractions.Fraction); (such as int or)
supported. (floats are not)

M#

As passed in.

Type:: list of list of int or fractions.Fraction

q, d

As passed in.

Type:: list of int or fractions.Fraction

n#

Dimension of the problem.

Type:: int

Examples

>>> from fractions import Fraction as F
>>> from lemke.lemke import lcp
>>> problem = lcp(
...     M=[[F(2), F(1)], [F(1), F(2)]],
...     q=[F(-1), F(-1)],
...     d=[F(1), F(1)],
... )
>>> problem.n
2

classmethod from_file(filename, decimals=4)[source]#

Create an LCP instance from a text file.

Expects a file starting with n= <dim>, followed by keyword-labeled blocks M=, q=, d= giving the matrix and vectors as whitespace-separated numbers, with the entries of M listed row by row. Numbers may be given as integers, fractions (e.g. 1/3), or decimals (e.g. 0.3). Blank lines and lines starting with #, % or * are ignored.

Parameters:

filename (str or pathlib.Path) – Path to the LCP file.
decimals (int, optional) – Number of decimal places to which numbers written as decimals (e.g. 0.145) are rounded before conversion to fractions. Must be between 0 and utils.MAXDECIMALS. Default is utils.DEFAULT_DECIMALS.

Returns:

The LCP described by the file.

Return type:

lcp

Raises:

TypeError – If decimals is not an integer.
ValueError – If decimals is out of range, the file does not start with n=, doesn’t contain the expected number of values, has an unrecognized keyword, or contains an invalid number.

Examples

Given a file lcp.txt containing:

n= 2
M= 2 1
   1 2
q= -1 -1
d= 1 1

>>> from lemke.lemke import lcp
>>> problem = lcp.from_file("lcp.txt")
>>> print(problem.n)
2

lemke.lemke.outstatistics(tableau)[source]#: Helper to output statistics of minimum ratio test.

lemke.lemke.result_from_tableau(tableau: tableau, success: bool, ray_entering_variable: str | None = None) → LcpResult[source]#

lemke.lemke.runlemke(*, lcp, callback=None)[source]#

Solve an LCP using Lemke’s complementary pivoting algorithm.

Parameters:

lcp (lcp) – The LCP instance to solve.
callback (LemkeCallback, optional) – Hook invoked at each step of the algorithm to observe or report progress. Pass PrintingCallback for a ready-made implementation. Default is None.

Returns:

The outcome of the algorithm. If a complementary solution was found, success is True and z, w hold the solution. If the algorithm terminated on a secondary ray, success is False, ray_entering_variable names the variable that could not enter, and z0, z, w describe the final (non-solution) basis. If q >= 0 the trivial solution z = 0, w = q is returned without pivoting and without invoking callback.

Return type:

LcpResult

Examples

Basic usage with no callbacks:

>>> from lemke.lemke import lcp, runlemke
>>> problem = lcp.from_file("lcp.txt")
>>> result = runlemke(lcp=problem)
>>> result.success
True
>>> result.z
(Fraction(1, 3), Fraction(1, 3))
>>> print(result)
Process finished successfully after 3 pivots.
Solution found:
basis=     z1  z2
    z=  0 1/3 1/3
    w=      0   0

Usage with a printing callback:

>>> from lemke.lemke import lcp, runlemke, PrintingCallback
>>> problem = lcp.from_file("lcp.txt")
>>> cb = PrintingCallback(verbose=True, z0=True)
>>> result = runlemke(lcp=problem, callback=cb)
# prints the given lcp, tableau and z0 at each step, and the final result

class lemke.lemke.tableau(Mqd)[source]#

The tableau used to run Lemke’s pivoting algorithm.

Stores the LCP data as a scaled integer tableau (to allow exact arithmetic during pivoting) and keeps track of which variables are currently basic/cobasic.

Parameters:: Mqd (lcp) – The LCP instance to build the tableau from.

n#

Problem dimension.

Type:: int

A#

The scaled tableau, shape (n, n + 2) (columns correspond to n + 1 cobasic variables, plus RHS).

Type:: list of list of int

determinant#

Current tableau determinant (always positive after pivoting).

Type:: int

scalefactor#

Per-column scale factors (LCM of denominators) used to keep the tableau in exact integer arithmetic.

Type:: list of int

bascobas#

Location for each variable index: its tableau row (if basic) or n + column (if cobasic).

Type:: list of int

whichvar#

Inverse of bascobas: which variable occupies each row or column.

Type:: list of int

pivotcount#

Number of pivots performed so far.

Type:: int

lextested, lexcomparisons

Per-column statistics from the lexicographic minimum-ratio test.

Type:: list of int

assertbasic(v, info)[source]#: Assert that variable v is basic.

assertcobasic(v, info)[source]#: Assert that variable v is cobasic.

complement(v)[source]#

Return the complementary variable of v (Z(i) <-> W(i)).

Parameters:: v (int) – A variable index other than z0.
Returns:: The complementary variable index.
Return type:: int
Raises:: RuntimeError – If v is z0 (0), which has no complement.

lexminvar(enter)[source]#

Find the leaving variable via the lexicographic minimum-ratio test.

Parameters:

enter (int) – The entering variable index (must currently be cobasic).

Returns:

leave (int) – The leaving variable index.
z0leave (bool) – True if z0 is among the (possibly tied) leaving candidates, meaning the algorithm may terminate after this pivot.

Raises:

RayTermination – If no row has a positive entry in the entering column, meaning the algorithm has found an unbounded ray instead of a solution.

negcol(col)[source]#: Negate every entry in the given column of the tableau.

negrow(row)[source]#: Negate every entry in the given row of the tableau.

pivot(leave, enter)[source]#

Pivot the tableau, exchanging leave (basic) and enter (cobasic).

Performs an exact-arithmetic pivot on A[row][col] where row/col correspond to leave/enter, then renormalizes the tableau to have positive determinant and updates the basic/cobasic variables.

Parameters:

leave (int) – Variable currently basic that will become cobasic.
enter (int) – Variable currently cobasic that will become basic.

testtablvars()[source]#: Check that bascobas and whichvar are consistent inverses.

vartoa(v)[source]#: Return the display name of variable index v, e.g. “z0” or “w3”.