441 lines
17 KiB
Python
441 lines
17 KiB
Python
|
"""HiGHS Linear Optimization Methods
|
||
|
|
|
||
|
|
Interface to HiGHS linear optimization software.
|
||
|
|
https://highs.dev/
|
||
|
|
|
||
|
|
.. versionadded:: 1.5.0
|
||
|
|
|
||
|
|
References
|
||
|
|
----------
|
||
|
|
.. [1] Q. Huangfu and J.A.J. Hall. "Parallelizing the dual revised simplex
|
||
|
|
method." Mathematical Programming Computation, 10 (1), 119-142,
|
||
|
|
2018. DOI: 10.1007/s12532-017-0130-5
|
||
|
|
|
||
|
|
"""
|
||
|
|
|
||
|
|
import inspect
|
||
|
|
import numpy as np
|
||
|
|
from ._optimize import OptimizeWarning, OptimizeResult
|
||
|
|
from warnings import warn
|
||
|
|
from ._highs._highs_wrapper import _highs_wrapper
|
||
|
|
from ._highs._highs_constants import (
|
||
|
|
CONST_INF,
|
||
|
|
MESSAGE_LEVEL_NONE,
|
||
|
|
HIGHS_OBJECTIVE_SENSE_MINIMIZE,
|
||
|
|
|
||
|
|
MODEL_STATUS_NOTSET,
|
||
|
|
MODEL_STATUS_LOAD_ERROR,
|
||
|
|
MODEL_STATUS_MODEL_ERROR,
|
||
|
|
MODEL_STATUS_PRESOLVE_ERROR,
|
||
|
|
MODEL_STATUS_SOLVE_ERROR,
|
||
|
|
MODEL_STATUS_POSTSOLVE_ERROR,
|
||
|
|
MODEL_STATUS_MODEL_EMPTY,
|
||
|
|
MODEL_STATUS_OPTIMAL,
|
||
|
|
MODEL_STATUS_INFEASIBLE,
|
||
|
|
MODEL_STATUS_UNBOUNDED_OR_INFEASIBLE,
|
||
|
|
MODEL_STATUS_UNBOUNDED,
|
||
|
|
MODEL_STATUS_REACHED_DUAL_OBJECTIVE_VALUE_UPPER_BOUND
|
||
|
|
as MODEL_STATUS_RDOVUB,
|
||
|
|
MODEL_STATUS_REACHED_OBJECTIVE_TARGET,
|
||
|
|
MODEL_STATUS_REACHED_TIME_LIMIT,
|
||
|
|
MODEL_STATUS_REACHED_ITERATION_LIMIT,
|
||
|
|
|
||
|
|
HIGHS_SIMPLEX_STRATEGY_DUAL,
|
||
|
|
|
||
|
|
HIGHS_SIMPLEX_CRASH_STRATEGY_OFF,
|
||
|
|
|
||
|
|
HIGHS_SIMPLEX_EDGE_WEIGHT_STRATEGY_CHOOSE,
|
||
|
|
HIGHS_SIMPLEX_EDGE_WEIGHT_STRATEGY_DANTZIG,
|
||
|
|
HIGHS_SIMPLEX_EDGE_WEIGHT_STRATEGY_DEVEX,
|
||
|
|
HIGHS_SIMPLEX_EDGE_WEIGHT_STRATEGY_STEEPEST_EDGE,
|
||
|
|
)
|
||
|
|
from scipy.sparse import csc_matrix, vstack, issparse
|
||
|
|
|
||
|
|
|
||
|
|
def _highs_to_scipy_status_message(highs_status, highs_message):
|
||
|
|
"""Converts HiGHS status number/message to SciPy status number/message"""
|
||
|
|
|
||
|
|
scipy_statuses_messages = {
|
||
|
|
None: (4, "HiGHS did not provide a status code. "),
|
||
|
|
MODEL_STATUS_NOTSET: (4, ""),
|
||
|
|
MODEL_STATUS_LOAD_ERROR: (4, ""),
|
||
|
|
MODEL_STATUS_MODEL_ERROR: (2, ""),
|
||
|
|
MODEL_STATUS_PRESOLVE_ERROR: (4, ""),
|
||
|
|
MODEL_STATUS_SOLVE_ERROR: (4, ""),
|
||
|
|
MODEL_STATUS_POSTSOLVE_ERROR: (4, ""),
|
||
|
|
MODEL_STATUS_MODEL_EMPTY: (4, ""),
|
||
|
|
MODEL_STATUS_RDOVUB: (4, ""),
|
||
|
|
MODEL_STATUS_REACHED_OBJECTIVE_TARGET: (4, ""),
|
||
|
|
MODEL_STATUS_OPTIMAL: (0, "Optimization terminated successfully. "),
|
||
|
|
MODEL_STATUS_REACHED_TIME_LIMIT: (1, "Time limit reached. "),
|
||
|
|
MODEL_STATUS_REACHED_ITERATION_LIMIT: (1, "Iteration limit reached. "),
|
||
|
|
MODEL_STATUS_INFEASIBLE: (2, "The problem is infeasible. "),
|
||
|
|
MODEL_STATUS_UNBOUNDED: (3, "The problem is unbounded. "),
|
||
|
|
MODEL_STATUS_UNBOUNDED_OR_INFEASIBLE: (4, "The problem is unbounded "
|
||
|
|
"or infeasible. ")}
|
||
|
|
unrecognized = (4, "The HiGHS status code was not recognized. ")
|
||
|
|
scipy_status, scipy_message = (
|
||
|
|
scipy_statuses_messages.get(highs_status, unrecognized))
|
||
|
|
scipy_message = (f"{scipy_message}"
|
||
|
|
f"(HiGHS Status {highs_status}: {highs_message})")
|
||
|
|
return scipy_status, scipy_message
|
||
|
|
|
||
|
|
|
||
|
|
def _replace_inf(x):
|
||
|
|
# Replace `np.inf` with CONST_INF
|
||
|
|
infs = np.isinf(x)
|
||
|
|
with np.errstate(invalid="ignore"):
|
||
|
|
x[infs] = np.sign(x[infs])*CONST_INF
|
||
|
|
return x
|
||
|
|
|
||
|
|
|
||
|
|
def _convert_to_highs_enum(option, option_str, choices):
|
||
|
|
# If option is in the choices we can look it up, if not use
|
||
|
|
# the default value taken from function signature and warn:
|
||
|
|
try:
|
||
|
|
return choices[option.lower()]
|
||
|
|
except AttributeError:
|
||
|
|
return choices[option]
|
||
|
|
except KeyError:
|
||
|
|
sig = inspect.signature(_linprog_highs)
|
||
|
|
default_str = sig.parameters[option_str].default
|
||
|
|
warn(f"Option {option_str} is {option}, but only values in "
|
||
|
|
f"{set(choices.keys())} are allowed. Using default: "
|
||
|
|
f"{default_str}.",
|
||
|
|
OptimizeWarning, stacklevel=3)
|
||
|
|
return choices[default_str]
|
||
|
|
|
||
|
|
|
||
|
|
def _linprog_highs(lp, solver, time_limit=None, presolve=True,
|
||
|
|
disp=False, maxiter=None,
|
||
|
|
dual_feasibility_tolerance=None,
|
||
|
|
primal_feasibility_tolerance=None,
|
||
|
|
ipm_optimality_tolerance=None,
|
||
|
|
simplex_dual_edge_weight_strategy=None,
|
||
|
|
mip_rel_gap=None,
|
||
|
|
mip_max_nodes=None,
|
||
|
|
**unknown_options):
|
||
|
|
r"""
|
||
|
|
Solve the following linear programming problem using one of the HiGHS
|
||
|
|
solvers:
|
||
|
|
|
||
|
|
User-facing documentation is in _linprog_doc.py.
|
||
|
|
|
||
|
|
Parameters
|
||
|
|
----------
|
||
|
|
lp : _LPProblem
|
||
|
|
A ``scipy.optimize._linprog_util._LPProblem`` ``namedtuple``.
|
||
|
|
solver : "ipm" or "simplex" or None
|
||
|
|
Which HiGHS solver to use. If ``None``, "simplex" will be used.
|
||
|
|
|
||
|
|
Options
|
||
|
|
-------
|
||
|
|
maxiter : int
|
||
|
|
The maximum number of iterations to perform in either phase. For
|
||
|
|
``solver='ipm'``, this does not include the number of crossover
|
||
|
|
iterations. Default is the largest possible value for an ``int``
|
||
|
|
on the platform.
|
||
|
|
disp : bool
|
||
|
|
Set to ``True`` if indicators of optimization status are to be printed
|
||
|
|
to the console each iteration; default ``False``.
|
||
|
|
time_limit : float
|
||
|
|
The maximum time in seconds allotted to solve the problem; default is
|
||
|
|
the largest possible value for a ``double`` on the platform.
|
||
|
|
presolve : bool
|
||
|
|
Presolve attempts to identify trivial infeasibilities,
|
||
|
|
identify trivial unboundedness, and simplify the problem before
|
||
|
|
sending it to the main solver. It is generally recommended
|
||
|
|
to keep the default setting ``True``; set to ``False`` if presolve is
|
||
|
|
to be disabled.
|
||
|
|
dual_feasibility_tolerance : double
|
||
|
|
Dual feasibility tolerance. Default is 1e-07.
|
||
|
|
The minimum of this and ``primal_feasibility_tolerance``
|
||
|
|
is used for the feasibility tolerance when ``solver='ipm'``.
|
||
|
|
primal_feasibility_tolerance : double
|
||
|
|
Primal feasibility tolerance. Default is 1e-07.
|
||
|
|
The minimum of this and ``dual_feasibility_tolerance``
|
||
|
|
is used for the feasibility tolerance when ``solver='ipm'``.
|
||
|
|
ipm_optimality_tolerance : double
|
||
|
|
Optimality tolerance for ``solver='ipm'``. Default is 1e-08.
|
||
|
|
Minimum possible value is 1e-12 and must be smaller than the largest
|
||
|
|
possible value for a ``double`` on the platform.
|
||
|
|
simplex_dual_edge_weight_strategy : str (default: None)
|
||
|
|
Strategy for simplex dual edge weights. The default, ``None``,
|
||
|
|
automatically selects one of the following.
|
||
|
|
|
||
|
|
``'dantzig'`` uses Dantzig's original strategy of choosing the most
|
||
|
|
negative reduced cost.
|
||
|
|
|
||
|
|
``'devex'`` uses the strategy described in [15]_.
|
||
|
|
|
||
|
|
``steepest`` uses the exact steepest edge strategy as described in
|
||
|
|
[16]_.
|
||
|
|
|
||
|
|
``'steepest-devex'`` begins with the exact steepest edge strategy
|
||
|
|
until the computation is too costly or inexact and then switches to
|
||
|
|
the devex method.
|
||
|
|
|
||
|
|
Currently, using ``None`` always selects ``'steepest-devex'``, but this
|
||
|
|
may change as new options become available.
|
||
|
|
|
||
|
|
mip_max_nodes : int
|
||
|
|
The maximum number of nodes allotted to solve the problem; default is
|
||
|
|
the largest possible value for a ``HighsInt`` on the platform.
|
||
|
|
Ignored if not using the MIP solver.
|
||
|
|
unknown_options : dict
|
||
|
|
Optional arguments not used by this particular solver. If
|
||
|
|
``unknown_options`` is non-empty, a warning is issued listing all
|
||
|
|
unused options.
|
||
|
|
|
||
|
|
Returns
|
||
|
|
-------
|
||
|
|
sol : dict
|
||
|
|
A dictionary consisting of the fields:
|
||
|
|
|
||
|
|
x : 1D array
|
||
|
|
The values of the decision variables that minimizes the
|
||
|
|
objective function while satisfying the constraints.
|
||
|
|
fun : float
|
||
|
|
The optimal value of the objective function ``c @ x``.
|
||
|
|
slack : 1D array
|
||
|
|
The (nominally positive) values of the slack,
|
||
|
|
``b_ub - A_ub @ x``.
|
||
|
|
con : 1D array
|
||
|
|
The (nominally zero) residuals of the equality constraints,
|
||
|
|
``b_eq - A_eq @ x``.
|
||
|
|
success : bool
|
||
|
|
``True`` when the algorithm succeeds in finding an optimal
|
||
|
|
solution.
|
||
|
|
status : int
|
||
|
|
An integer representing the exit status of the algorithm.
|
||
|
|
|
||
|
|
``0`` : Optimization terminated successfully.
|
||
|
|
|
||
|
|
``1`` : Iteration or time limit reached.
|
||
|
|
|
||
|
|
``2`` : Problem appears to be infeasible.
|
||
|
|
|
||
|
|
``3`` : Problem appears to be unbounded.
|
||
|
|
|
||
|
|
``4`` : The HiGHS solver ran into a problem.
|
||
|
|
|
||
|
|
message : str
|
||
|
|
A string descriptor of the exit status of the algorithm.
|
||
|
|
nit : int
|
||
|
|
The total number of iterations performed.
|
||
|
|
For ``solver='simplex'``, this includes iterations in all
|
||
|
|
phases. For ``solver='ipm'``, this does not include
|
||
|
|
crossover iterations.
|
||
|
|
crossover_nit : int
|
||
|
|
The number of primal/dual pushes performed during the
|
||
|
|
crossover routine for ``solver='ipm'``. This is ``0``
|
||
|
|
for ``solver='simplex'``.
|
||
|
|
ineqlin : OptimizeResult
|
||
|
|
Solution and sensitivity information corresponding to the
|
||
|
|
inequality constraints, `b_ub`. A dictionary consisting of the
|
||
|
|
fields:
|
||
|
|
|
||
|
|
residual : np.ndnarray
|
||
|
|
The (nominally positive) values of the slack variables,
|
||
|
|
``b_ub - A_ub @ x``. This quantity is also commonly
|
||
|
|
referred to as "slack".
|
||
|
|
|
||
|
|
marginals : np.ndarray
|
||
|
|
The sensitivity (partial derivative) of the objective
|
||
|
|
function with respect to the right-hand side of the
|
||
|
|
inequality constraints, `b_ub`.
|
||
|
|
|
||
|
|
eqlin : OptimizeResult
|
||
|
|
Solution and sensitivity information corresponding to the
|
||
|
|
equality constraints, `b_eq`. A dictionary consisting of the
|
||
|
|
fields:
|
||
|
|
|
||
|
|
residual : np.ndarray
|
||
|
|
The (nominally zero) residuals of the equality constraints,
|
||
|
|
``b_eq - A_eq @ x``.
|
||
|
|
|
||
|
|
marginals : np.ndarray
|
||
|
|
The sensitivity (partial derivative) of the objective
|
||
|
|
function with respect to the right-hand side of the
|
||
|
|
equality constraints, `b_eq`.
|
||
|
|
|
||
|
|
lower, upper : OptimizeResult
|
||
|
|
Solution and sensitivity information corresponding to the
|
||
|
|
lower and upper bounds on decision variables, `bounds`.
|
||
|
|
|
||
|
|
residual : np.ndarray
|
||
|
|
The (nominally positive) values of the quantity
|
||
|
|
``x - lb`` (lower) or ``ub - x`` (upper).
|
||
|
|
|
||
|
|
marginals : np.ndarray
|
||
|
|
The sensitivity (partial derivative) of the objective
|
||
|
|
function with respect to the lower and upper
|
||
|
|
`bounds`.
|
||
|
|
|
||
|
|
mip_node_count : int
|
||
|
|
The number of subproblems or "nodes" solved by the MILP
|
||
|
|
solver. Only present when `integrality` is not `None`.
|
||
|
|
|
||
|
|
mip_dual_bound : float
|
||
|
|
The MILP solver's final estimate of the lower bound on the
|
||
|
|
optimal solution. Only present when `integrality` is not
|
||
|
|
`None`.
|
||
|
|
|
||
|
|
mip_gap : float
|
||
|
|
The difference between the final objective function value
|
||
|
|
and the final dual bound, scaled by the final objective
|
||
|
|
function value. Only present when `integrality` is not
|
||
|
|
`None`.
|
||
|
|
|
||
|
|
Notes
|
||
|
|
-----
|
||
|
|
The result fields `ineqlin`, `eqlin`, `lower`, and `upper` all contain
|
||
|
|
`marginals`, or partial derivatives of the objective function with respect
|
||
|
|
to the right-hand side of each constraint. These partial derivatives are
|
||
|
|
also referred to as "Lagrange multipliers", "dual values", and
|
||
|
|
"shadow prices". The sign convention of `marginals` is opposite that
|
||
|
|
of Lagrange multipliers produced by many nonlinear solvers.
|
||
|
|
|
||
|
|
References
|
||
|
|
----------
|
||
|
|
.. [15] Harris, Paula MJ. "Pivot selection methods of the Devex LP code."
|
||
|
|
Mathematical programming 5.1 (1973): 1-28.
|
||
|
|
.. [16] Goldfarb, Donald, and John Ker Reid. "A practicable steepest-edge
|
||
|
|
simplex algorithm." Mathematical Programming 12.1 (1977): 361-371.
|
||
|
|
"""
|
||
|
|
if unknown_options:
|
||
|
|
message = (f"Unrecognized options detected: {unknown_options}. "
|
||
|
|
"These will be passed to HiGHS verbatim.")
|
||
|
|
warn(message, OptimizeWarning, stacklevel=3)
|
||
|
|
|
||
|
|
# Map options to HiGHS enum values
|
||
|
|
simplex_dual_edge_weight_strategy_enum = _convert_to_highs_enum(
|
||
|
|
simplex_dual_edge_weight_strategy,
|
||
|
|
'simplex_dual_edge_weight_strategy',
|
||
|
|
choices={'dantzig': HIGHS_SIMPLEX_EDGE_WEIGHT_STRATEGY_DANTZIG,
|
||
|
|
'devex': HIGHS_SIMPLEX_EDGE_WEIGHT_STRATEGY_DEVEX,
|
||
|
|
'steepest-devex': HIGHS_SIMPLEX_EDGE_WEIGHT_STRATEGY_CHOOSE,
|
||
|
|
'steepest':
|
||
|
|
HIGHS_SIMPLEX_EDGE_WEIGHT_STRATEGY_STEEPEST_EDGE,
|
||
|
|
None: None})
|
||
|
|
|
||
|
|
c, A_ub, b_ub, A_eq, b_eq, bounds, x0, integrality = lp
|
||
|
|
|
||
|
|
lb, ub = bounds.T.copy() # separate bounds, copy->C-cntgs
|
||
|
|
# highs_wrapper solves LHS <= A*x <= RHS, not equality constraints
|
||
|
|
with np.errstate(invalid="ignore"):
|
||
|
|
lhs_ub = -np.ones_like(b_ub)*np.inf # LHS of UB constraints is -inf
|
||
|
|
rhs_ub = b_ub # RHS of UB constraints is b_ub
|
||
|
|
lhs_eq = b_eq # Equality constraint is inequality
|
||
|
|
rhs_eq = b_eq # constraint with LHS=RHS
|
||
|
|
lhs = np.concatenate((lhs_ub, lhs_eq))
|
||
|
|
rhs = np.concatenate((rhs_ub, rhs_eq))
|
||
|
|
|
||
|
|
if issparse(A_ub) or issparse(A_eq):
|
||
|
|
A = vstack((A_ub, A_eq))
|
||
|
|
else:
|
||
|
|
A = np.vstack((A_ub, A_eq))
|
||
|
|
A = csc_matrix(A)
|
||
|
|
|
||
|
|
options = {
|
||
|
|
'presolve': presolve,
|
||
|
|
'sense': HIGHS_OBJECTIVE_SENSE_MINIMIZE,
|
||
|
|
'solver': solver,
|
||
|
|
'time_limit': time_limit,
|
||
|
|
'highs_debug_level': MESSAGE_LEVEL_NONE,
|
||
|
|
'dual_feasibility_tolerance': dual_feasibility_tolerance,
|
||
|
|
'ipm_optimality_tolerance': ipm_optimality_tolerance,
|
||
|
|
'log_to_console': disp,
|
||
|
|
'mip_max_nodes': mip_max_nodes,
|
||
|
|
'output_flag': disp,
|
||
|
|
'primal_feasibility_tolerance': primal_feasibility_tolerance,
|
||
|
|
'simplex_dual_edge_weight_strategy':
|
||
|
|
simplex_dual_edge_weight_strategy_enum,
|
||
|
|
'simplex_strategy': HIGHS_SIMPLEX_STRATEGY_DUAL,
|
||
|
|
'simplex_crash_strategy': HIGHS_SIMPLEX_CRASH_STRATEGY_OFF,
|
||
|
|
'ipm_iteration_limit': maxiter,
|
||
|
|
'simplex_iteration_limit': maxiter,
|
||
|
|
'mip_rel_gap': mip_rel_gap,
|
||
|
|
}
|
||
|
|
options.update(unknown_options)
|
||
|
|
|
||
|
|
# np.inf doesn't work; use very large constant
|
||
|
|
rhs = _replace_inf(rhs)
|
||
|
|
lhs = _replace_inf(lhs)
|
||
|
|
lb = _replace_inf(lb)
|
||
|
|
ub = _replace_inf(ub)
|
||
|
|
|
||
|
|
if integrality is None or np.sum(integrality) == 0:
|
||
|
|
integrality = np.empty(0)
|
||
|
|
else:
|
||
|
|
integrality = np.array(integrality)
|
||
|
|
|
||
|
|
res = _highs_wrapper(c, A.indptr, A.indices, A.data, lhs, rhs,
|
||
|
|
lb, ub, integrality.astype(np.uint8), options)
|
||
|
|
|
||
|
|
# HiGHS represents constraints as lhs/rhs, so
|
||
|
|
# Ax + s = b => Ax = b - s
|
||
|
|
# and we need to split up s by A_ub and A_eq
|
||
|
|
if 'slack' in res:
|
||
|
|
slack = res['slack']
|
||
|
|
con = np.array(slack[len(b_ub):])
|
||
|
|
slack = np.array(slack[:len(b_ub)])
|
||
|
|
else:
|
||
|
|
slack, con = None, None
|
||
|
|
|
||
|
|
# lagrange multipliers for equalities/inequalities and upper/lower bounds
|
||
|
|
if 'lambda' in res:
|
||
|
|
lamda = res['lambda']
|
||
|
|
marg_ineqlin = np.array(lamda[:len(b_ub)])
|
||
|
|
marg_eqlin = np.array(lamda[len(b_ub):])
|
||
|
|
marg_upper = np.array(res['marg_bnds'][1, :])
|
||
|
|
marg_lower = np.array(res['marg_bnds'][0, :])
|
||
|
|
else:
|
||
|
|
marg_ineqlin, marg_eqlin = None, None
|
||
|
|
marg_upper, marg_lower = None, None
|
||
|
|
|
||
|
|
# this needs to be updated if we start choosing the solver intelligently
|
||
|
|
|
||
|
|
# Convert to scipy-style status and message
|
||
|
|
highs_status = res.get('status', None)
|
||
|
|
highs_message = res.get('message', None)
|
||
|
|
status, message = _highs_to_scipy_status_message(highs_status,
|
||
|
|
highs_message)
|
||
|
|
|
||
|
|
x = np.array(res['x']) if 'x' in res else None
|
||
|
|
sol = {'x': x,
|
||
|
|
'slack': slack,
|
||
|
|
'con': con,
|
||
|
|
'ineqlin': OptimizeResult({
|
||
|
|
'residual': slack,
|
||
|
|
'marginals': marg_ineqlin,
|
||
|
|
}),
|
||
|
|
'eqlin': OptimizeResult({
|
||
|
|
'residual': con,
|
||
|
|
'marginals': marg_eqlin,
|
||
|
|
}),
|
||
|
|
'lower': OptimizeResult({
|
||
|
|
'residual': None if x is None else x - lb,
|
||
|
|
'marginals': marg_lower,
|
||
|
|
}),
|
||
|
|
'upper': OptimizeResult({
|
||
|
|
'residual': None if x is None else ub - x,
|
||
|
|
'marginals': marg_upper
|
||
|
|
}),
|
||
|
|
'fun': res.get('fun'),
|
||
|
|
'status': status,
|
||
|
|
'success': res['status'] == MODEL_STATUS_OPTIMAL,
|
||
|
|
'message': message,
|
||
|
|
'nit': res.get('simplex_nit', 0) or res.get('ipm_nit', 0),
|
||
|
|
'crossover_nit': res.get('crossover_nit'),
|
||
|
|
}
|
||
|
|
|
||
|
|
if np.any(x) and integrality is not None:
|
||
|
|
sol.update({
|
||
|
|
'mip_node_count': res.get('mip_node_count', 0),
|
||
|
|
'mip_dual_bound': res.get('mip_dual_bound', 0.0),
|
||
|
|
'mip_gap': res.get('mip_gap', 0.0),
|
||
|
|
})
|
||
|
|
|
||
|
|
return sol
|