| | |
- __builtin__.object
-
- Bar
- BarCollection
- BarCollectionIter
- KKT
- LPX
- Objective
- ObjectiveIter
- Params
class Bar(__builtin__.object) |
| |
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.
|
| |
Methods defined here:
- __repr__(...)
- x.__repr__() <==> repr(x)
- __str__(...)
- x.__str__() <==> str(x)
Data descriptors defined here:
- 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.
- 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, or 'int'
if this is an integer 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.
- 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 BarCollection(__builtin__.object) |
| |
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
|
| |
Methods defined here:
- __contains__(...)
- x.__contains__(y) <==> y in x
- __delitem__(...)
- x.__delitem__(y) <==> del x[y]
- __getitem__(...)
- x.__getitem__(y) <==> x[y]
- __iter__(...)
- x.__iter__() <==> iter(x)
- __len__(...)
- x.__len__() <==> len(x)
- __setitem__(...)
- x.__setitem__(i, y) <==> x[i]=y
- add(...)
- add(n)
Add n more rows (constraints) or columns (struct variables).
Returns the index of the first added entry.
|
class KKT(__builtin__.object) |
| |
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.
|
| |
Data descriptors defined here:
- 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 LPX(__builtin__.object) |
| |
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 the 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 elment 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.
params Holds control parameters and statistics.
|
| |
Methods defined here:
- __init__(...)
- x.__init__(...) initializes x; see x.__class__.__doc__ for signature
- __repr__(...)
- x.__repr__() <==> repr(x)
- __str__(...)
- x.__str__() <==> str(x)
- adv_basis(...)
- adv_basis()
Construct an advanced initial basis, triangular with as few
variables as possible fixed.
- cpx_basis(...)
- 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.
- exact(...)
- 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(...)
- intopt()
MIP solver based on branch-and-bound.
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(...)
- 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(...)
- 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.
- kkt(...)
- 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(...)
- 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.
- read_basis(...)
- read_basis(filename)
Reads an LP basis in the fixed MPS format from a given file.
- scale(...)
- scale([toscale=True])
Either scale or unscale depending on truth of the argument.
Note that this only affects the internal state of the LP
representation.
- simplex(...)
- simplex()
Attempt to solve the problem using a 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.
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.)
- std_basis(...)
- std_basis()
Construct the standard trivial inital basis for this LP.
- write(...)
- 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.
prob -- Problem data in a plain text 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.
Data descriptors defined here:
- cols
- Column collection. See the help on class BarCollection.
- 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.
- 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.
- params
- Control parameter collection. See the help on class Params.
- 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.
- 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.
Data and other attributes defined here:
- __new__ = <built-in method __new__ of type object at 0x788004>
- T.__new__(S, ...) -> a new object with type S, a subtype of T
|
class Objective(__builtin__.object) |
| |
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
|
| |
Methods defined here:
- __delitem__(...)
- x.__delitem__(y) <==> del x[y]
- __getitem__(...)
- x.__getitem__(y) <==> x[y]
- __iter__(...)
- x.__iter__() <==> iter(x)
- __len__(...)
- x.__len__() <==> len(x)
- __setitem__(...)
- x.__setitem__(i, y) <==> x[i]=y
Data descriptors defined here:
- maximize
- True or False depending on whether we are trying to maximize
or minimize this objective function.
- 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 Params(__builtin__.object) |
| |
Parameter and statistics collection objects. An instance of
this exists as the 'params' attribute of LPX instances. By
changing parameters here, one may affect the behavior of
the solvers, data readers, writers, verbosity, etc.
|
| |
Methods defined here:
- reset(...)
- reset()
Resets all control parameters to their default values.
Data descriptors defined here:
- branch
- Branching heuristic option (for MIP only):
0 -- branch on first variable
1 -- branch on last variable
2 -- branch using a heuristic by Driebeck and Tomlin
- btrack
- Backtracking heuristic option (for MIP only):
0 -- depth first search
1 -- breadth first search
2 -- backtrack using the best projection heuristic
- dual
- Whether to, if the initial basic solution is dual feasible, use
the dual simplex.
- itcnt
- Simplex iterations count. This count is increased by one each
time when one simplex iteration has been performed.
- itlim
- Simplex iterations limit. If this value is positive, it is
decreased by one each time when one simplex iteration has been
performed, and reaching zero value signals the solver to stop
the search. Negative value means no iterations limit.
- mpsfree
- Whether the MIPS writer should omit column and vector names
whenever possible (free style). If False, the writer never
omits names (pedantic style).
- mpsinfo
- Whether when writing MPS data, comments containing
information on the problem should be written as well.
- mpsobj
- How the objective function should be output in MPS writing:
0 -- never output objective function row
1 -- always output objective function row
2 -- output objective function row if the problem has no free rows
- mpsorig
- Whether when writing MPS data, the original symbolic names
for rows and columns should be used. If False, when writing,
plain names are generated from the index of the row and column
(counting from 1).
- mpsskip
- Whether the MIPS writer should skip empty columns.
- mpswide
- Whether when writing MIPS, all data fields should be used.
If False, fields 5 and 6 are kept empty.
- msglev
- Output level for solver routines:
0 -- none
1 -- error messages
2 -- normal
3 -- full information
- objll
- Lower limit of the objective function. If on the phase II
the objective function reaches this limit and continues
decreasing, the solver stops the search. (Used in the dual
simplex only.)
- objul
- Lower limit of the objective function. If on the phase II
the objective function reaches this limit and continues
increasing, the solver stops the search. (Used in the dual
simplex only.)
- outdly
- Output delay, in seconds. This parameter specifies how long
the solver should delay sending information about the solution
to the standard output. Non-positive value means no delay.
- outfrq
- Output frequency, in iterations. This parameter specifies how
frequently the solver sends information about the solution to
the standard output. This must be positive.
- presol
- Whether the simplex solver should use the LP presolver.
- price
- Pricing option for primal and dual simplex.
0 -- textbook pricing
1 -- steepest edge pricing
- relax
- Relaxation parameter used in the ratio test. If it is zero, the
textbook ratio test is used. If it is non-zero (should be
positive), Harris' two-pass ratio test is used. In the latter
case on the first pass of the ratio test basic variables (in the
case of primal simplex) or reduced costs of non-basic variables
(in the case of dual simplex) are allowed to slightly violate
their bounds, but not more than (relax*tolbnd) or (relax*toldj)
(thus, relax specifies the mixture of tolbnd or toldj).
- round
- Whether to round tiny primal and dual values to exact zero.
- scale
- Scaling used when the lp.scale() method is called.
0 -- no scaling
1 -- equilibration scaling
2 -- geometric mean scaling
3 -- geometric then equilibration scaling
- tmlim
- Searching time limit, in seconds. If this value is positive,
it is decreased each time when one simplex iteration has been
performed by the amount of time spent for the iteration, and
reaching zero value signals the solver to stop the search.
Negative value means no time limit.
- tolbnd
- Relative tolerance used to check the basic solution's primal
feasibility. (Do not change this parameter without detailed
understanding of its purpose.)
- toldj
- Absolute tolerance used to check the basic solution's dual
feasibility. (Do not change this parameter without detailed
understanding of its purpose.)
- tolint
- Absolute tolerance used to check if the current basic solution
is integer feasible. (Do not change this parameter without
detailed understanding of its purpose.)
- tolobj
- Relative tolerance used to check if the value of the objective
function is not better than in the best known integer feasible
solution. (Do not change this parameter without detailed
understanding of its purpose.)
- tolpiv
- Relative tolerance used to choose eligible pivotal elements of
the simplex table. (Do not change this parameter without
detailed understanding of its purpose.)
- usecuts
- A bitstring representing what cuts should be used in the
intopt() solver. For a current value 'val', the truth of
these indicates which cuts will be used (multiple cuts
may be used):
0x01 & val -- mixed cover cuts
0x02 & val -- clique cuts
0x04 & val -- Gomory's mixed integer cuts
For example, 0x07 or 0xFF or the like would use all cuts,
and 0 would mean no cuts will be used.
| |