Solvers

Simplex

class epyglpki.SimplexSolver

The problem’s simplex solver

basis(algorithm, status, warmup=False)

Change or retrieve basis

A basis is defined by the statuses assigned to all variables and constraints; the possible statuses are

• 'basic': basic
• 'lower': non-basic with active lower bound
• 'upper': non-basic with active upper bound
• 'free': non-basic free
• 'fixed': non-basic fixed

A basis is valid if the basis matrix is non-singular, which implies that the number of basic variables and constraints is equal to the total number of constraints.

Parameters:

• algorithm (str) –

  an algorithm for generating a basis (omit to keep current basis), chosen from

  • 'standard': sets all constraints as basic
  • 'advanced': sets as basic
    1. all non-fixed constraints
    2. as many non-fixed variables as possible, while preserving the lower triangular structure of the basis matrix
    3. appropriate fixed constraints to complete the basis
  • 'Bixby': algorithm used by CPLEX, as discussed by Bixby
• status (Mapping from Variable or Constraint to str) – the mapping of statuses to change (omit for retrieval only)
• warmup (bool) – whether to ‘warm up’ the basis, so that SimplexSolver.solve() can be used without presolving

Returns:

a mapping of the basis statuses of all variables and constraints

Return type:

dict from Variable or Constraint to str

Raises:

• ValueError – if algorithm is neither 'standard', 'advanced', nor 'Bixby'
• TypeError – if basis is not Mapping
• TypeError – if basis keys are neither Variable nor Constraint
• ValueError – if the basis is invalid
• ValueError – if the basis matrix is singular
• ValueError – if the basis matrix is ill-conditioned

Todo

Add doctest

Note

After SimplexSolver.solve() has been run successfully, the basis is left in a valid state. So it is not necessary to run this method before, e.g., re-optimizating after only the objective has been changed.

constraints(dual=False)

Return the values of the constraints for the current solution

Parameters:dual (bool) – whether to return dual or primal values Returns:the nonzero values of the constraints for the current solution Return type:dict from Constraint to float Raises TypeError:  if dual is not bool

Todo

Add doctest

controls(defaults=False, **controls)

Change or retrieve the solver’s control parameters

Parameters:

• defaults (bool) – whether to set the parameters back to their default values or not
• controls –

  zero or more named parameters to change from the following list:

  • msg_lev (str) – the message level, with possible values
    • 'no': no output
    • 'warnerror': warnings and errors only
    • 'normal': normal output
    • 'full': normal output and informational messages
  • meth (str) – simplex method, with possible values
    • 'primal': two-phase primal simplex
    • 'dual': two-phase dual simplex
    • 'dual_fail_primal': two-phase dual simplex and, if it fails, switch to primal simplex
  • pricing (str) – pricing technique, with possible values
    • 'Dantzig': standard ‘textbook’
    • 'steepest': projected steepest edge
  • r_test (str) – ratio test technique, with possible values
    • 'standard': standard ‘textbook’
    • 'Harris': Harris’s two-pass ratio test
  • tol_bnd (Real) – tolerance used to check if the basic solution is primal feasible
  • tol_dj (Real) – tolerance used to check if the basic solution is dual feasible
  • tol_piv (Real) – tolerance used to choose eligble pivotal elements of the simplex table
  • obj_ll (Real) – lower limit of the objective function (only if meth is 'dual')
  • obj_ul (Real) – upper limit of the objective function (only if meth is 'dual')
  • it_lim (Integral) – iteration limit
  • tm_lim (Integral) – time limit [ms]
  • out_frq (Integral) – output frequency [iterations] of informational messages
  • out_dly (Integral) – output delay [ms] of solution process information
  • presolve (bool) – use LP presolver

  or, for basis factorization, from the following list:

  • type (str) – basis factorization type, with possible values
    • 'Forrest-Tomlin': LU + Forrest–Tomlin update
    • 'Bartels-Golub': LU + Schur complement + Bartels–Golub update
    • 'Givens': LU + Schur complement + Givens rotation update
  • lu_size (Integral) – initial size of the Sparse Vector Area, in non-zeros (for first LU-factorization; set to 0 to determine it automatically)
  • piv_tol (Real) – Markowitz threshold pivoting tolerance (value must lie between 0 and 1)
  • piv_lim (Integral) – number of pivot candidates that need to be considered on choosing a pivot element (at least 1)
  • suhl (bool) – use Suhl heuristic
  • eps_tol (Real) – tolerance below which numbers are replaced by zero
  • max_gro (Real) – maximal growth factor of elements of the U-matrix above which the basis matrix is considered ill-conditioned
  • nfs_max (Integral) – maximal number of additional row-like factors (used only when type is 'Forrest-Tomlin')
  • upd_tol (Real) – update tolerance for the relative magnitude of diagonal elements of U determining whether the factorization is inaccurate (value must lie between 0 and 1; used only when type is 'Forrest-Tomlin')
  • nrs_max (Integral) – maximal number of additional row and columns (used only when type is 'Bartels-Golub' or Givens')
  • rs_size (Integral) – initial size of the Sparse Vector Area, in non-zeros (for initial LU-factorization; set to 0 to determine it automatically; used only when type is 'Bartels-Golub' or Givens')

Raises ValueError:  

if a non-existing control name is given

Todo

Add doctest

objective()

Return the objective value for the current solution

Returns:the objective value for the current solution Return type:float

Todo

Add doctest

print_ranges(varstraints, fname)

Write a sensitivity analysis report to file in readable format

Parameters:

• varstraints (Sequence of Variable and/or Constraint) – sequence of variables and/or constraints to analyze
• fname (str) – the name of the file to write to

Raises:

• Exception – if the current solution is not optimal
• TypeError – if varstraints is not Sequence of Variable and/or Constraint
• ValueError – if the current basis is invalid
• ValueError – if the current basis matrix is singular
• ValueError – if the current basis matrix is ill-conditioned

Todo

Add doctest

print_solution(fname)

Write the solution to a file in a readable format

Parameters:fname (str) – the name of the file to write to Raises RuntimeError:  if there is an error writing the file

Todo

Add doctest

read_solution(fname)

Read the solution from a file

Parameters:fname (str) – the name of the file to read from (written by SimplexSolver.write_solution()) Raises RuntimeError:  if there is an error reading the file

Todo

Add doctest

solve(exact=False)

Solve the linear program

Parameters:

exact (bool) – whether to use exact arithmetic or not (only if the meth control parameter is 'primal')

Returns:

solution status; see SimplexSolver.status() for details, or "obj_ll reached" or "obj_ul reached" in case that happens

Return type:

str

Raises:

• ValueError – if exact is True but the meth control parameter is not 'primal'
• ValueError – if finite values are set for obj_ll or obj_ll while the meth control parameter is not 'dual'
• ValueError – if the basis is invalid
• ValueError – if the basis matrix is singular
• ValueError – if the basis matrix is ill-conditioned
• ValueError – if incorrect bounds are given
• RuntimeError – in case of solver failure
• StopIteration – if the iteration limit is exceeded
• StopIteration – if the time limit is exceeded
• StopIteration – if the presolver detects the problem has no primal feasible solution
• StopIteration – if the presolver detects the problem has no dual feasible solution

Todo

Add doctest

status(detailed=False)

Return the current solution status

Parameters:detailed (bool) – whether to give a detailed solution status Returns:the current solution status

• in case detailed is False, either 'undefined', 'optimal, 'infeasible', 'no feasible', 'feasible', or 'unbounded'
• in case detailed is True, a pair of statuses is given, one for the primal solution and one for the dual solution, either 'undefined', 'infeasible', 'no feasible', or 'feasible'

Return type:str or length-2 tuple of str

Todo

Add doctest

unboundedness()

Return a variable or constraint causing unboundedness

Returns:a variable or constraint causing unboundedness (if any) and the nature of the unboundedness, either 'primal' or 'dual' Return type:length-2 tuple of Variable or Constraint and str

Todo

Add doctest

variables(dual=False)

Return the values of the variables for the current solution

Parameters:dual (bool) – whether to return dual or primal values Returns:the nonzero values of the variables for the current solution Return type:dict from Variable to float Raises TypeError:  if dual is not bool

Todo

Add doctest

write_solution(fname)

Write the solution to a file

Parameters:fname (str) – the name of the file to write to Raises RuntimeError:  if there is an error writing the file

Todo

Add doctest

Interior Point

class epyglpki.IPointSolver

The problem’s interior point solver

constraints(dual=False)

Return the values of the constraints for the current solution

Parameters:dual (bool) – whether to return dual or primal values Returns:the nonzero values of the constraints for the current solution Return type:dict from Constraint to float Raises TypeError:  if dual is not bool

Todo

Add doctest

controls(defaults=False, **controls)

Change or retrieve the solver’s control parameters

Parameters:

• defaults (bool) – whether to set the parameters back to their default values or not
• controls –

  zero or more named parameters to change from the following list:

  • msg_lev (str) – the message level, with possible values
    • 'no': no output
    • 'warnerror': warnings and errors only
    • 'normal': normal output
    • 'full': normal output and informational messages
  • ord_alg (str) – the ordering algorithm used prior to Cholesky factorization, with possible values
    • 'orig': normal (original)
    • 'qmd': quotient minimum degree
    • 'amd': approximate minimum degree
    • 'symamd': approximate minimum degree for symmetric matrices

Raises ValueError:  

if a non-existing control name is given

Todo

Add doctest

objective()

Return the objective value for the current solution

Returns:the objective value for the current solution Return type:float

Todo

Add doctest

print_solution(fname)

Write the solution to a file in a readable format

Parameters:fname (str) – the name of the file to write to Raises RuntimeError:  if there is an error writing the file

Todo

Add doctest

read_solution(fname)

Read the solution from a file

Parameters:fname (str) – the name of the file to read from (written by IPointSolver.write_solution()) Raises RuntimeError:  if there is an error reading the file

Todo

Add doctest

solve()

Solve the linear program

Returns:

solution status; see IPointSolver.status() for details

Return type:

str

Raises:

• ValueError – if the problem has no rows/columns
• ArithmeticError – if there occurs very slow convergence or divergence
• StopIteration – if the iteration limit is exceeded
• ArithmeticError – if numerical instability occurs on solving the Newtonian system

Todo

Add doctest

status()

Return the current solution status

Returns:the current solution status, either 'undefined', 'optimal, 'infeasible', or 'no feasible' Return type:str

Todo

Add doctest

variables(dual=False)

Return the values of the variables for the current solution

Parameters:dual (bool) – whether to return dual or primal values Returns:the nonzero values of the variables for the current solution Return type:dict from Variable to float Raises TypeError:  if dual is not bool

Todo

Add doctest

write_solution(fname)

Write the solution to a file

Parameters:fname (str) – the name of the file to write to Raises RuntimeError:  if there is an error writing the file

Todo

Add doctest

Integer Optimization

class epyglpki.IntOptSolver

The problem’s integer optimization solver

constraints()

Return the values of the constraints for the current solution

Returns:the nonzero values of the constraints for the current solution Return type:dict from Constraint to float

Todo

Add doctest

controls(defaults=False, **controls)

Change or retrieve the solver’s control parameters

Parameters:

• defaults (bool) – whether to set the parameters back to their default values or not
• controls –

  zero or more named parameters to change from the following list:

  • msg_lev (str) – the message level, with possible values
    • 'no': no output
    • 'warnerror': warnings and errors only
    • 'normal': normal output
    • 'full': normal output and informational messages
  • out_frq (Integral) – output frequency [ms] of informational messages
  • out_dly (Integral) – output delay [ms] of current LP relaxation solution
  • tm_lim (Integral) – time limit [ms]
  • br_tech (str) – the branching technique, with possible values
    • 'first_fracvar': first fractional variable
    • 'last_fracvar': last fractional variable
    • 'most_fracvar': most fractional variable
    • 'Driebeek-Tomlin': heuristic by Driebeek & Tomlin
    • 'hybrid_peudocost': hybrid pseudocost heuristic
  • bt_tech (str) – the backtracking technique, with possible values
    • 'depth': depth first search
    • 'breadth': breadth first search
    • 'bound': best local bound
    • 'projection': best projection heuristic
  • pp_tech (str) – the preprocessing technique, with possible values
    • 'none': disable preprocessing
    • 'root': preprocessing only on the root level
    • 'all': preprocessing on all levels
  • mir_cuts (bool) – generate mixed integer rounding cuts
  • gmi_cuts (bool) – generate Gomory’s mixed integer cuts
  • cov_cuts (bool) – generate mixed cover cuts
  • clq_cuts (bool) – generate clique cuts
  • fp_heur (bool) – apply feasibility pump heuristic
  • tol_int (Real) – absolute tolerance used to check if the optimal solution to the current LP relaxation is integer feasible
  • tol_obj (Real) – relative tolerance used to check if the objective value in the optimal solution to the current LP relaxation is not better than in the best known integer feasible solution.
  • mip_gap (Real) – relative MIP-gap tolerance (search stops once the relative MIP-gap falls below this value)
  • presolve (bool) – use MIP presolver, may simplify the problem
  • binarize (bool) – binarize integer variables (only used if presolve is True)

Raises ValueError:  

if a non-existing control name is given

Todo

Add doctest

objective()

Return the objective value for the current solution

Returns:the objective value for the current solution Return type:float

Todo

Add doctest

print_solution(fname)

Write the solution to a file in a readable format

Parameters:fname (str) – the name of the file to write to Raises RuntimeError:  if there is an error writing the file

Todo

Add doctest

read_solution(fname)

Read the solution from a file

Parameters:fname (str) – the name of the file to read from (written by IntOptSolver.write_solution()) Raises RuntimeError:  if there is an error reading the file

Todo

Add doctest

solve(solver='branchcut', obj_bound)

Solve the mixed-integer linear program

Parameters:

• solver (str) –

  which solver to use, chosen from

  • 'branchcut': a branch-and-cut solver
  • 'intfeas1': a SAT solver based integer feasibility solver; applicable only to problems
    • that are feasibility problems (but see obj_bound description)
    • with only binary variables (and integer variables with coinciding lower and upper bound)
    • with all-integer coefficients

    and furthermore efficient mainly for problems with constraints that are covering, packing, or partitioning inequalities, i.e., sums of binary variables \(x\) or their ‘negation’ \(1-x\), smaller than, equal to, or larger than \(1\).

• obj_bound (Integral) – if solver is 'intfeas1', a solution is considered feasible only if the corresponding objective value is not worse than this bound (not used if solver is 'branchcut')

Returns:

solution status; see IntOptSolver.status() for details

Return type:

str

Raises:

• ValueError – if solver is neither 'branchcut' nor 'intfeas1'
• TypeError – if obj_bound is not Integral
• ValueError – if incorrect bounds are given
• ValueError – if no optimal LP relaxation basis has been provided
• ValueError – if the LP relaxation is infeasible
• ValueError – if the LP relaxation is unbounded
• RuntimeError – in case of solver failure
• StopIteration – if the relative mip gap tolerance has been reached
• StopIteration – if the time limit has been exceeded
• StopIteration – if the branch-and-cut callback terminated the solver
• ValueError – if not all problem parameters are integer (only relevant if solver is 'intfeas1')
• OverflowError – if an integer overflow occurred when transforming to CNF SAT format

Todo

Add doctest

status()

Return the current solution status

Returns:the current solution status, either 'undefined', 'optimal, 'no feasible', or 'feasible' Return type:str

Todo

Add doctest

variables()

Return the values of the variables for the current solution

Returns:the nonzero values of the variables for the current solution Return type:dict from Variable to float or int Raises ValueError:  if a variable with 'integer' or 'binary' kind has a non-integer value

Todo

Add doctest

write_solution(fname)

Write the solution to a file

Parameters:fname (str) – the name of the file to write to Raises RuntimeError:  if there is an error writing the file

Todo

Add doctest