1436 lines
60 KiB
Python
1436 lines
60 KiB
Python
# -*- coding: utf-8 -*-
|
|
"""
|
|
Created on Sat Aug 22 19:49:17 2020
|
|
|
|
@author: matth
|
|
"""
|
|
|
|
|
|
def _linprog_highs_doc(c, A_ub=None, b_ub=None, A_eq=None, b_eq=None,
|
|
bounds=None, method='highs', callback=None,
|
|
maxiter=None, disp=False, presolve=True,
|
|
time_limit=None,
|
|
dual_feasibility_tolerance=None,
|
|
primal_feasibility_tolerance=None,
|
|
ipm_optimality_tolerance=None,
|
|
simplex_dual_edge_weight_strategy=None,
|
|
mip_rel_gap=None,
|
|
**unknown_options):
|
|
r"""
|
|
Linear programming: minimize a linear objective function subject to linear
|
|
equality and inequality constraints using one of the HiGHS solvers.
|
|
|
|
Linear programming solves problems of the following form:
|
|
|
|
.. math::
|
|
|
|
\min_x \ & c^T x \\
|
|
\mbox{such that} \ & A_{ub} x \leq b_{ub},\\
|
|
& A_{eq} x = b_{eq},\\
|
|
& l \leq x \leq u ,
|
|
|
|
where :math:`x` is a vector of decision variables; :math:`c`,
|
|
:math:`b_{ub}`, :math:`b_{eq}`, :math:`l`, and :math:`u` are vectors; and
|
|
:math:`A_{ub}` and :math:`A_{eq}` are matrices.
|
|
|
|
Alternatively, that's:
|
|
|
|
minimize::
|
|
|
|
c @ x
|
|
|
|
such that::
|
|
|
|
A_ub @ x <= b_ub
|
|
A_eq @ x == b_eq
|
|
lb <= x <= ub
|
|
|
|
Note that by default ``lb = 0`` and ``ub = None`` unless specified with
|
|
``bounds``.
|
|
|
|
Parameters
|
|
----------
|
|
c : 1-D array
|
|
The coefficients of the linear objective function to be minimized.
|
|
A_ub : 2-D array, optional
|
|
The inequality constraint matrix. Each row of ``A_ub`` specifies the
|
|
coefficients of a linear inequality constraint on ``x``.
|
|
b_ub : 1-D array, optional
|
|
The inequality constraint vector. Each element represents an
|
|
upper bound on the corresponding value of ``A_ub @ x``.
|
|
A_eq : 2-D array, optional
|
|
The equality constraint matrix. Each row of ``A_eq`` specifies the
|
|
coefficients of a linear equality constraint on ``x``.
|
|
b_eq : 1-D array, optional
|
|
The equality constraint vector. Each element of ``A_eq @ x`` must equal
|
|
the corresponding element of ``b_eq``.
|
|
bounds : sequence, optional
|
|
A sequence of ``(min, max)`` pairs for each element in ``x``, defining
|
|
the minimum and maximum values of that decision variable. Use ``None``
|
|
to indicate that there is no bound. By default, bounds are
|
|
``(0, None)`` (all decision variables are non-negative).
|
|
If a single tuple ``(min, max)`` is provided, then ``min`` and
|
|
``max`` will serve as bounds for all decision variables.
|
|
method : str
|
|
|
|
This is the method-specific documentation for 'highs', which chooses
|
|
automatically between
|
|
:ref:`'highs-ds' <optimize.linprog-highs-ds>` and
|
|
:ref:`'highs-ipm' <optimize.linprog-highs-ipm>`.
|
|
:ref:`'interior-point' <optimize.linprog-interior-point>` (default),
|
|
:ref:`'revised simplex' <optimize.linprog-revised_simplex>`, and
|
|
:ref:`'simplex' <optimize.linprog-simplex>` (legacy)
|
|
are also available.
|
|
integrality : 1-D array or int, optional
|
|
Indicates the type of integrality constraint on each decision variable.
|
|
|
|
``0`` : Continuous variable; no integrality constraint.
|
|
|
|
``1`` : Integer variable; decision variable must be an integer
|
|
within `bounds`.
|
|
|
|
``2`` : Semi-continuous variable; decision variable must be within
|
|
`bounds` or take value ``0``.
|
|
|
|
``3`` : Semi-integer variable; decision variable must be an integer
|
|
within `bounds` or take value ``0``.
|
|
|
|
By default, all variables are continuous.
|
|
|
|
For mixed integrality constraints, supply an array of shape `c.shape`.
|
|
To infer a constraint on each decision variable from shorter inputs,
|
|
the argument will be broadcasted to `c.shape` using `np.broadcast_to`.
|
|
|
|
This argument is currently used only by the ``'highs'`` method and
|
|
ignored otherwise.
|
|
|
|
Options
|
|
-------
|
|
maxiter : int
|
|
The maximum number of iterations to perform in either phase.
|
|
For :ref:`'highs-ipm' <optimize.linprog-highs-ipm>`, this does not
|
|
include the number of crossover iterations. Default is the largest
|
|
possible value for an ``int`` on the platform.
|
|
disp : bool (default: ``False``)
|
|
Set to ``True`` if indicators of optimization status are to be
|
|
printed to the console during optimization.
|
|
presolve : bool (default: ``True``)
|
|
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.
|
|
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.
|
|
dual_feasibility_tolerance : double (default: 1e-07)
|
|
Dual feasibility tolerance for
|
|
:ref:`'highs-ds' <optimize.linprog-highs-ds>`.
|
|
The minimum of this and ``primal_feasibility_tolerance``
|
|
is used for the feasibility tolerance of
|
|
:ref:`'highs-ipm' <optimize.linprog-highs-ipm>`.
|
|
primal_feasibility_tolerance : double (default: 1e-07)
|
|
Primal feasibility tolerance for
|
|
:ref:`'highs-ds' <optimize.linprog-highs-ds>`.
|
|
The minimum of this and ``dual_feasibility_tolerance``
|
|
is used for the feasibility tolerance of
|
|
:ref:`'highs-ipm' <optimize.linprog-highs-ipm>`.
|
|
ipm_optimality_tolerance : double (default: ``1e-08``)
|
|
Optimality tolerance for
|
|
:ref:`'highs-ipm' <optimize.linprog-highs-ipm>`.
|
|
Minimum allowable value is 1e-12.
|
|
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.
|
|
|
|
Curently, ``None`` always selects ``'steepest-devex'``, but this
|
|
may change as new options become available.
|
|
mip_rel_gap : double (default: None)
|
|
Termination criterion for MIP solver: solver will terminate when the
|
|
gap between the primal objective value and the dual objective bound,
|
|
scaled by the primal objective value, is <= mip_rel_gap.
|
|
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
|
|
-------
|
|
res : OptimizeResult
|
|
A :class:`scipy.optimize.OptimizeResult` 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 the HiGHS simplex method, this includes iterations in all
|
|
phases. For the HiGHS interior-point method, this does not include
|
|
crossover iterations.
|
|
crossover_nit : int
|
|
The number of primal/dual pushes performed during the
|
|
crossover routine for the HiGHS interior-point method.
|
|
This is ``0`` for the HiGHS simplex method.
|
|
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`.
|
|
|
|
Notes
|
|
-----
|
|
|
|
Method :ref:`'highs-ds' <optimize.linprog-highs-ds>` is a wrapper
|
|
of the C++ high performance dual revised simplex implementation (HSOL)
|
|
[13]_, [14]_. Method :ref:`'highs-ipm' <optimize.linprog-highs-ipm>`
|
|
is a wrapper of a C++ implementation of an **i**\ nterior-\ **p**\ oint
|
|
**m**\ ethod [13]_; it features a crossover routine, so it is as accurate
|
|
as a simplex solver. Method :ref:`'highs' <optimize.linprog-highs>` chooses
|
|
between the two automatically. For new code involving `linprog`, we
|
|
recommend explicitly choosing one of these three method values instead of
|
|
:ref:`'interior-point' <optimize.linprog-interior-point>` (default),
|
|
:ref:`'revised simplex' <optimize.linprog-revised_simplex>`, and
|
|
:ref:`'simplex' <optimize.linprog-simplex>` (legacy).
|
|
|
|
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
|
|
----------
|
|
.. [13] Huangfu, Q., Galabova, I., Feldmeier, M., and Hall, J. A. J.
|
|
"HiGHS - high performance software for linear optimization."
|
|
https://highs.dev/
|
|
.. [14] Huangfu, Q. and Hall, J. A. J. "Parallelizing the dual revised
|
|
simplex method." Mathematical Programming Computation, 10 (1),
|
|
119-142, 2018. DOI: 10.1007/s12532-017-0130-5
|
|
.. [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.
|
|
"""
|
|
pass
|
|
|
|
|
|
def _linprog_highs_ds_doc(c, A_ub=None, b_ub=None, A_eq=None, b_eq=None,
|
|
bounds=None, method='highs-ds', callback=None,
|
|
maxiter=None, disp=False, presolve=True,
|
|
time_limit=None,
|
|
dual_feasibility_tolerance=None,
|
|
primal_feasibility_tolerance=None,
|
|
simplex_dual_edge_weight_strategy=None,
|
|
**unknown_options):
|
|
r"""
|
|
Linear programming: minimize a linear objective function subject to linear
|
|
equality and inequality constraints using the HiGHS dual simplex solver.
|
|
|
|
Linear programming solves problems of the following form:
|
|
|
|
.. math::
|
|
|
|
\min_x \ & c^T x \\
|
|
\mbox{such that} \ & A_{ub} x \leq b_{ub},\\
|
|
& A_{eq} x = b_{eq},\\
|
|
& l \leq x \leq u ,
|
|
|
|
where :math:`x` is a vector of decision variables; :math:`c`,
|
|
:math:`b_{ub}`, :math:`b_{eq}`, :math:`l`, and :math:`u` are vectors; and
|
|
:math:`A_{ub}` and :math:`A_{eq}` are matrices.
|
|
|
|
Alternatively, that's:
|
|
|
|
minimize::
|
|
|
|
c @ x
|
|
|
|
such that::
|
|
|
|
A_ub @ x <= b_ub
|
|
A_eq @ x == b_eq
|
|
lb <= x <= ub
|
|
|
|
Note that by default ``lb = 0`` and ``ub = None`` unless specified with
|
|
``bounds``.
|
|
|
|
Parameters
|
|
----------
|
|
c : 1-D array
|
|
The coefficients of the linear objective function to be minimized.
|
|
A_ub : 2-D array, optional
|
|
The inequality constraint matrix. Each row of ``A_ub`` specifies the
|
|
coefficients of a linear inequality constraint on ``x``.
|
|
b_ub : 1-D array, optional
|
|
The inequality constraint vector. Each element represents an
|
|
upper bound on the corresponding value of ``A_ub @ x``.
|
|
A_eq : 2-D array, optional
|
|
The equality constraint matrix. Each row of ``A_eq`` specifies the
|
|
coefficients of a linear equality constraint on ``x``.
|
|
b_eq : 1-D array, optional
|
|
The equality constraint vector. Each element of ``A_eq @ x`` must equal
|
|
the corresponding element of ``b_eq``.
|
|
bounds : sequence, optional
|
|
A sequence of ``(min, max)`` pairs for each element in ``x``, defining
|
|
the minimum and maximum values of that decision variable. Use ``None``
|
|
to indicate that there is no bound. By default, bounds are
|
|
``(0, None)`` (all decision variables are non-negative).
|
|
If a single tuple ``(min, max)`` is provided, then ``min`` and
|
|
``max`` will serve as bounds for all decision variables.
|
|
method : str
|
|
|
|
This is the method-specific documentation for 'highs-ds'.
|
|
:ref:`'highs' <optimize.linprog-highs>`,
|
|
:ref:`'highs-ipm' <optimize.linprog-highs-ipm>`,
|
|
:ref:`'interior-point' <optimize.linprog-interior-point>` (default),
|
|
:ref:`'revised simplex' <optimize.linprog-revised_simplex>`, and
|
|
:ref:`'simplex' <optimize.linprog-simplex>` (legacy)
|
|
are also available.
|
|
|
|
Options
|
|
-------
|
|
maxiter : int
|
|
The maximum number of iterations to perform in either phase.
|
|
Default is the largest possible value for an ``int`` on the platform.
|
|
disp : bool (default: ``False``)
|
|
Set to ``True`` if indicators of optimization status are to be
|
|
printed to the console during optimization.
|
|
presolve : bool (default: ``True``)
|
|
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.
|
|
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.
|
|
dual_feasibility_tolerance : double (default: 1e-07)
|
|
Dual feasibility tolerance for
|
|
:ref:`'highs-ds' <optimize.linprog-highs-ds>`.
|
|
primal_feasibility_tolerance : double (default: 1e-07)
|
|
Primal feasibility tolerance for
|
|
:ref:`'highs-ds' <optimize.linprog-highs-ds>`.
|
|
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.
|
|
|
|
Curently, ``None`` always selects ``'steepest-devex'``, but this
|
|
may change as new options become available.
|
|
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
|
|
-------
|
|
res : OptimizeResult
|
|
A :class:`scipy.optimize.OptimizeResult` 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. This includes iterations
|
|
in all phases.
|
|
crossover_nit : int
|
|
This is always ``0`` for the HiGHS simplex method.
|
|
For the HiGHS interior-point method, this is the number of
|
|
primal/dual pushes performed during the crossover routine.
|
|
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`.
|
|
|
|
Notes
|
|
-----
|
|
|
|
Method :ref:`'highs-ds' <optimize.linprog-highs-ds>` is a wrapper
|
|
of the C++ high performance dual revised simplex implementation (HSOL)
|
|
[13]_, [14]_. Method :ref:`'highs-ipm' <optimize.linprog-highs-ipm>`
|
|
is a wrapper of a C++ implementation of an **i**\ nterior-\ **p**\ oint
|
|
**m**\ ethod [13]_; it features a crossover routine, so it is as accurate
|
|
as a simplex solver. Method :ref:`'highs' <optimize.linprog-highs>` chooses
|
|
between the two automatically. For new code involving `linprog`, we
|
|
recommend explicitly choosing one of these three method values instead of
|
|
:ref:`'interior-point' <optimize.linprog-interior-point>` (default),
|
|
:ref:`'revised simplex' <optimize.linprog-revised_simplex>`, and
|
|
:ref:`'simplex' <optimize.linprog-simplex>` (legacy).
|
|
|
|
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
|
|
----------
|
|
.. [13] Huangfu, Q., Galabova, I., Feldmeier, M., and Hall, J. A. J.
|
|
"HiGHS - high performance software for linear optimization."
|
|
https://highs.dev/
|
|
.. [14] Huangfu, Q. and Hall, J. A. J. "Parallelizing the dual revised
|
|
simplex method." Mathematical Programming Computation, 10 (1),
|
|
119-142, 2018. DOI: 10.1007/s12532-017-0130-5
|
|
.. [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.
|
|
"""
|
|
pass
|
|
|
|
|
|
def _linprog_highs_ipm_doc(c, A_ub=None, b_ub=None, A_eq=None, b_eq=None,
|
|
bounds=None, method='highs-ipm', callback=None,
|
|
maxiter=None, disp=False, presolve=True,
|
|
time_limit=None,
|
|
dual_feasibility_tolerance=None,
|
|
primal_feasibility_tolerance=None,
|
|
ipm_optimality_tolerance=None,
|
|
**unknown_options):
|
|
r"""
|
|
Linear programming: minimize a linear objective function subject to linear
|
|
equality and inequality constraints using the HiGHS interior point solver.
|
|
|
|
Linear programming solves problems of the following form:
|
|
|
|
.. math::
|
|
|
|
\min_x \ & c^T x \\
|
|
\mbox{such that} \ & A_{ub} x \leq b_{ub},\\
|
|
& A_{eq} x = b_{eq},\\
|
|
& l \leq x \leq u ,
|
|
|
|
where :math:`x` is a vector of decision variables; :math:`c`,
|
|
:math:`b_{ub}`, :math:`b_{eq}`, :math:`l`, and :math:`u` are vectors; and
|
|
:math:`A_{ub}` and :math:`A_{eq}` are matrices.
|
|
|
|
Alternatively, that's:
|
|
|
|
minimize::
|
|
|
|
c @ x
|
|
|
|
such that::
|
|
|
|
A_ub @ x <= b_ub
|
|
A_eq @ x == b_eq
|
|
lb <= x <= ub
|
|
|
|
Note that by default ``lb = 0`` and ``ub = None`` unless specified with
|
|
``bounds``.
|
|
|
|
Parameters
|
|
----------
|
|
c : 1-D array
|
|
The coefficients of the linear objective function to be minimized.
|
|
A_ub : 2-D array, optional
|
|
The inequality constraint matrix. Each row of ``A_ub`` specifies the
|
|
coefficients of a linear inequality constraint on ``x``.
|
|
b_ub : 1-D array, optional
|
|
The inequality constraint vector. Each element represents an
|
|
upper bound on the corresponding value of ``A_ub @ x``.
|
|
A_eq : 2-D array, optional
|
|
The equality constraint matrix. Each row of ``A_eq`` specifies the
|
|
coefficients of a linear equality constraint on ``x``.
|
|
b_eq : 1-D array, optional
|
|
The equality constraint vector. Each element of ``A_eq @ x`` must equal
|
|
the corresponding element of ``b_eq``.
|
|
bounds : sequence, optional
|
|
A sequence of ``(min, max)`` pairs for each element in ``x``, defining
|
|
the minimum and maximum values of that decision variable. Use ``None``
|
|
to indicate that there is no bound. By default, bounds are
|
|
``(0, None)`` (all decision variables are non-negative).
|
|
If a single tuple ``(min, max)`` is provided, then ``min`` and
|
|
``max`` will serve as bounds for all decision variables.
|
|
method : str
|
|
|
|
This is the method-specific documentation for 'highs-ipm'.
|
|
:ref:`'highs-ipm' <optimize.linprog-highs>`,
|
|
:ref:`'highs-ds' <optimize.linprog-highs-ds>`,
|
|
:ref:`'interior-point' <optimize.linprog-interior-point>` (default),
|
|
:ref:`'revised simplex' <optimize.linprog-revised_simplex>`, and
|
|
:ref:`'simplex' <optimize.linprog-simplex>` (legacy)
|
|
are also available.
|
|
|
|
Options
|
|
-------
|
|
maxiter : int
|
|
The maximum number of iterations to perform in either phase.
|
|
For :ref:`'highs-ipm' <optimize.linprog-highs-ipm>`, this does not
|
|
include the number of crossover iterations. Default is the largest
|
|
possible value for an ``int`` on the platform.
|
|
disp : bool (default: ``False``)
|
|
Set to ``True`` if indicators of optimization status are to be
|
|
printed to the console during optimization.
|
|
presolve : bool (default: ``True``)
|
|
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.
|
|
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.
|
|
dual_feasibility_tolerance : double (default: 1e-07)
|
|
The minimum of this and ``primal_feasibility_tolerance``
|
|
is used for the feasibility tolerance of
|
|
:ref:`'highs-ipm' <optimize.linprog-highs-ipm>`.
|
|
primal_feasibility_tolerance : double (default: 1e-07)
|
|
The minimum of this and ``dual_feasibility_tolerance``
|
|
is used for the feasibility tolerance of
|
|
:ref:`'highs-ipm' <optimize.linprog-highs-ipm>`.
|
|
ipm_optimality_tolerance : double (default: ``1e-08``)
|
|
Optimality tolerance for
|
|
:ref:`'highs-ipm' <optimize.linprog-highs-ipm>`.
|
|
Minimum allowable value is 1e-12.
|
|
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
|
|
-------
|
|
res : OptimizeResult
|
|
A :class:`scipy.optimize.OptimizeResult` 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 the HiGHS interior-point method, this does not include
|
|
crossover iterations.
|
|
crossover_nit : int
|
|
The number of primal/dual pushes performed during the
|
|
crossover routine for the HiGHS interior-point method.
|
|
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`.
|
|
|
|
Notes
|
|
-----
|
|
|
|
Method :ref:`'highs-ipm' <optimize.linprog-highs-ipm>`
|
|
is a wrapper of a C++ implementation of an **i**\ nterior-\ **p**\ oint
|
|
**m**\ ethod [13]_; it features a crossover routine, so it is as accurate
|
|
as a simplex solver.
|
|
Method :ref:`'highs-ds' <optimize.linprog-highs-ds>` is a wrapper
|
|
of the C++ high performance dual revised simplex implementation (HSOL)
|
|
[13]_, [14]_. Method :ref:`'highs' <optimize.linprog-highs>` chooses
|
|
between the two automatically. For new code involving `linprog`, we
|
|
recommend explicitly choosing one of these three method values instead of
|
|
:ref:`'interior-point' <optimize.linprog-interior-point>` (default),
|
|
:ref:`'revised simplex' <optimize.linprog-revised_simplex>`, and
|
|
:ref:`'simplex' <optimize.linprog-simplex>` (legacy).
|
|
|
|
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
|
|
----------
|
|
.. [13] Huangfu, Q., Galabova, I., Feldmeier, M., and Hall, J. A. J.
|
|
"HiGHS - high performance software for linear optimization."
|
|
https://highs.dev/
|
|
.. [14] Huangfu, Q. and Hall, J. A. J. "Parallelizing the dual revised
|
|
simplex method." Mathematical Programming Computation, 10 (1),
|
|
119-142, 2018. DOI: 10.1007/s12532-017-0130-5
|
|
"""
|
|
pass
|
|
|
|
|
|
def _linprog_ip_doc(c, A_ub=None, b_ub=None, A_eq=None, b_eq=None,
|
|
bounds=None, method='interior-point', callback=None,
|
|
maxiter=1000, disp=False, presolve=True,
|
|
tol=1e-8, autoscale=False, rr=True,
|
|
alpha0=.99995, beta=0.1, sparse=False,
|
|
lstsq=False, sym_pos=True, cholesky=True, pc=True,
|
|
ip=False, permc_spec='MMD_AT_PLUS_A', **unknown_options):
|
|
r"""
|
|
Linear programming: minimize a linear objective function subject to linear
|
|
equality and inequality constraints using the interior-point method of
|
|
[4]_.
|
|
|
|
.. deprecated:: 1.9.0
|
|
`method='interior-point'` will be removed in SciPy 1.11.0.
|
|
It is replaced by `method='highs'` because the latter is
|
|
faster and more robust.
|
|
|
|
Linear programming solves problems of the following form:
|
|
|
|
.. math::
|
|
|
|
\min_x \ & c^T x \\
|
|
\mbox{such that} \ & A_{ub} x \leq b_{ub},\\
|
|
& A_{eq} x = b_{eq},\\
|
|
& l \leq x \leq u ,
|
|
|
|
where :math:`x` is a vector of decision variables; :math:`c`,
|
|
:math:`b_{ub}`, :math:`b_{eq}`, :math:`l`, and :math:`u` are vectors; and
|
|
:math:`A_{ub}` and :math:`A_{eq}` are matrices.
|
|
|
|
Alternatively, that's:
|
|
|
|
minimize::
|
|
|
|
c @ x
|
|
|
|
such that::
|
|
|
|
A_ub @ x <= b_ub
|
|
A_eq @ x == b_eq
|
|
lb <= x <= ub
|
|
|
|
Note that by default ``lb = 0`` and ``ub = None`` unless specified with
|
|
``bounds``.
|
|
|
|
Parameters
|
|
----------
|
|
c : 1-D array
|
|
The coefficients of the linear objective function to be minimized.
|
|
A_ub : 2-D array, optional
|
|
The inequality constraint matrix. Each row of ``A_ub`` specifies the
|
|
coefficients of a linear inequality constraint on ``x``.
|
|
b_ub : 1-D array, optional
|
|
The inequality constraint vector. Each element represents an
|
|
upper bound on the corresponding value of ``A_ub @ x``.
|
|
A_eq : 2-D array, optional
|
|
The equality constraint matrix. Each row of ``A_eq`` specifies the
|
|
coefficients of a linear equality constraint on ``x``.
|
|
b_eq : 1-D array, optional
|
|
The equality constraint vector. Each element of ``A_eq @ x`` must equal
|
|
the corresponding element of ``b_eq``.
|
|
bounds : sequence, optional
|
|
A sequence of ``(min, max)`` pairs for each element in ``x``, defining
|
|
the minimum and maximum values of that decision variable. Use ``None``
|
|
to indicate that there is no bound. By default, bounds are
|
|
``(0, None)`` (all decision variables are non-negative).
|
|
If a single tuple ``(min, max)`` is provided, then ``min`` and
|
|
``max`` will serve as bounds for all decision variables.
|
|
method : str
|
|
This is the method-specific documentation for 'interior-point'.
|
|
:ref:`'highs' <optimize.linprog-highs>`,
|
|
:ref:`'highs-ds' <optimize.linprog-highs-ds>`,
|
|
:ref:`'highs-ipm' <optimize.linprog-highs-ipm>`,
|
|
:ref:`'revised simplex' <optimize.linprog-revised_simplex>`, and
|
|
:ref:`'simplex' <optimize.linprog-simplex>` (legacy)
|
|
are also available.
|
|
callback : callable, optional
|
|
Callback function to be executed once per iteration.
|
|
|
|
Options
|
|
-------
|
|
maxiter : int (default: 1000)
|
|
The maximum number of iterations of the algorithm.
|
|
disp : bool (default: False)
|
|
Set to ``True`` if indicators of optimization status are to be printed
|
|
to the console each iteration.
|
|
presolve : bool (default: True)
|
|
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.
|
|
tol : float (default: 1e-8)
|
|
Termination tolerance to be used for all termination criteria;
|
|
see [4]_ Section 4.5.
|
|
autoscale : bool (default: False)
|
|
Set to ``True`` to automatically perform equilibration.
|
|
Consider using this option if the numerical values in the
|
|
constraints are separated by several orders of magnitude.
|
|
rr : bool (default: True)
|
|
Set to ``False`` to disable automatic redundancy removal.
|
|
alpha0 : float (default: 0.99995)
|
|
The maximal step size for Mehrota's predictor-corrector search
|
|
direction; see :math:`\beta_{3}` of [4]_ Table 8.1.
|
|
beta : float (default: 0.1)
|
|
The desired reduction of the path parameter :math:`\mu` (see [6]_)
|
|
when Mehrota's predictor-corrector is not in use (uncommon).
|
|
sparse : bool (default: False)
|
|
Set to ``True`` if the problem is to be treated as sparse after
|
|
presolve. If either ``A_eq`` or ``A_ub`` is a sparse matrix,
|
|
this option will automatically be set ``True``, and the problem
|
|
will be treated as sparse even during presolve. If your constraint
|
|
matrices contain mostly zeros and the problem is not very small (less
|
|
than about 100 constraints or variables), consider setting ``True``
|
|
or providing ``A_eq`` and ``A_ub`` as sparse matrices.
|
|
lstsq : bool (default: ``False``)
|
|
Set to ``True`` if the problem is expected to be very poorly
|
|
conditioned. This should always be left ``False`` unless severe
|
|
numerical difficulties are encountered. Leave this at the default
|
|
unless you receive a warning message suggesting otherwise.
|
|
sym_pos : bool (default: True)
|
|
Leave ``True`` if the problem is expected to yield a well conditioned
|
|
symmetric positive definite normal equation matrix
|
|
(almost always). Leave this at the default unless you receive
|
|
a warning message suggesting otherwise.
|
|
cholesky : bool (default: True)
|
|
Set to ``True`` if the normal equations are to be solved by explicit
|
|
Cholesky decomposition followed by explicit forward/backward
|
|
substitution. This is typically faster for problems
|
|
that are numerically well-behaved.
|
|
pc : bool (default: True)
|
|
Leave ``True`` if the predictor-corrector method of Mehrota is to be
|
|
used. This is almost always (if not always) beneficial.
|
|
ip : bool (default: False)
|
|
Set to ``True`` if the improved initial point suggestion due to [4]_
|
|
Section 4.3 is desired. Whether this is beneficial or not
|
|
depends on the problem.
|
|
permc_spec : str (default: 'MMD_AT_PLUS_A')
|
|
(Has effect only with ``sparse = True``, ``lstsq = False``, ``sym_pos =
|
|
True``, and no SuiteSparse.)
|
|
A matrix is factorized in each iteration of the algorithm.
|
|
This option specifies how to permute the columns of the matrix for
|
|
sparsity preservation. Acceptable values are:
|
|
|
|
- ``NATURAL``: natural ordering.
|
|
- ``MMD_ATA``: minimum degree ordering on the structure of A^T A.
|
|
- ``MMD_AT_PLUS_A``: minimum degree ordering on the structure of A^T+A.
|
|
- ``COLAMD``: approximate minimum degree column ordering.
|
|
|
|
This option can impact the convergence of the
|
|
interior point algorithm; test different values to determine which
|
|
performs best for your problem. For more information, refer to
|
|
``scipy.sparse.linalg.splu``.
|
|
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
|
|
-------
|
|
res : OptimizeResult
|
|
A :class:`scipy.optimize.OptimizeResult` consisting of the fields:
|
|
|
|
x : 1-D 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 : 1-D array
|
|
The (nominally positive) values of the slack variables,
|
|
``b_ub - A_ub @ x``.
|
|
con : 1-D 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 limit reached.
|
|
|
|
``2`` : Problem appears to be infeasible.
|
|
|
|
``3`` : Problem appears to be unbounded.
|
|
|
|
``4`` : Numerical difficulties encountered.
|
|
|
|
message : str
|
|
A string descriptor of the exit status of the algorithm.
|
|
nit : int
|
|
The total number of iterations performed in all phases.
|
|
|
|
|
|
Notes
|
|
-----
|
|
This method implements the algorithm outlined in [4]_ with ideas from [8]_
|
|
and a structure inspired by the simpler methods of [6]_.
|
|
|
|
The primal-dual path following method begins with initial 'guesses' of
|
|
the primal and dual variables of the standard form problem and iteratively
|
|
attempts to solve the (nonlinear) Karush-Kuhn-Tucker conditions for the
|
|
problem with a gradually reduced logarithmic barrier term added to the
|
|
objective. This particular implementation uses a homogeneous self-dual
|
|
formulation, which provides certificates of infeasibility or unboundedness
|
|
where applicable.
|
|
|
|
The default initial point for the primal and dual variables is that
|
|
defined in [4]_ Section 4.4 Equation 8.22. Optionally (by setting initial
|
|
point option ``ip=True``), an alternate (potentially improved) starting
|
|
point can be calculated according to the additional recommendations of
|
|
[4]_ Section 4.4.
|
|
|
|
A search direction is calculated using the predictor-corrector method
|
|
(single correction) proposed by Mehrota and detailed in [4]_ Section 4.1.
|
|
(A potential improvement would be to implement the method of multiple
|
|
corrections described in [4]_ Section 4.2.) In practice, this is
|
|
accomplished by solving the normal equations, [4]_ Section 5.1 Equations
|
|
8.31 and 8.32, derived from the Newton equations [4]_ Section 5 Equations
|
|
8.25 (compare to [4]_ Section 4 Equations 8.6-8.8). The advantage of
|
|
solving the normal equations rather than 8.25 directly is that the
|
|
matrices involved are symmetric positive definite, so Cholesky
|
|
decomposition can be used rather than the more expensive LU factorization.
|
|
|
|
With default options, the solver used to perform the factorization depends
|
|
on third-party software availability and the conditioning of the problem.
|
|
|
|
For dense problems, solvers are tried in the following order:
|
|
|
|
1. ``scipy.linalg.cho_factor``
|
|
|
|
2. ``scipy.linalg.solve`` with option ``sym_pos=True``
|
|
|
|
3. ``scipy.linalg.solve`` with option ``sym_pos=False``
|
|
|
|
4. ``scipy.linalg.lstsq``
|
|
|
|
For sparse problems:
|
|
|
|
1. ``sksparse.cholmod.cholesky`` (if scikit-sparse and SuiteSparse are
|
|
installed)
|
|
|
|
2. ``scipy.sparse.linalg.factorized`` (if scikit-umfpack and SuiteSparse
|
|
are installed)
|
|
|
|
3. ``scipy.sparse.linalg.splu`` (which uses SuperLU distributed with SciPy)
|
|
|
|
4. ``scipy.sparse.linalg.lsqr``
|
|
|
|
If the solver fails for any reason, successively more robust (but slower)
|
|
solvers are attempted in the order indicated. Attempting, failing, and
|
|
re-starting factorization can be time consuming, so if the problem is
|
|
numerically challenging, options can be set to bypass solvers that are
|
|
failing. Setting ``cholesky=False`` skips to solver 2,
|
|
``sym_pos=False`` skips to solver 3, and ``lstsq=True`` skips
|
|
to solver 4 for both sparse and dense problems.
|
|
|
|
Potential improvements for combatting issues associated with dense
|
|
columns in otherwise sparse problems are outlined in [4]_ Section 5.3 and
|
|
[10]_ Section 4.1-4.2; the latter also discusses the alleviation of
|
|
accuracy issues associated with the substitution approach to free
|
|
variables.
|
|
|
|
After calculating the search direction, the maximum possible step size
|
|
that does not activate the non-negativity constraints is calculated, and
|
|
the smaller of this step size and unity is applied (as in [4]_ Section
|
|
4.1.) [4]_ Section 4.3 suggests improvements for choosing the step size.
|
|
|
|
The new point is tested according to the termination conditions of [4]_
|
|
Section 4.5. The same tolerance, which can be set using the ``tol`` option,
|
|
is used for all checks. (A potential improvement would be to expose
|
|
the different tolerances to be set independently.) If optimality,
|
|
unboundedness, or infeasibility is detected, the solve procedure
|
|
terminates; otherwise it repeats.
|
|
|
|
Whereas the top level ``linprog`` module expects a problem of form:
|
|
|
|
Minimize::
|
|
|
|
c @ x
|
|
|
|
Subject to::
|
|
|
|
A_ub @ x <= b_ub
|
|
A_eq @ x == b_eq
|
|
lb <= x <= ub
|
|
|
|
where ``lb = 0`` and ``ub = None`` unless set in ``bounds``. The problem
|
|
is automatically converted to the form:
|
|
|
|
Minimize::
|
|
|
|
c @ x
|
|
|
|
Subject to::
|
|
|
|
A @ x == b
|
|
x >= 0
|
|
|
|
for solution. That is, the original problem contains equality, upper-bound
|
|
and variable constraints whereas the method specific solver requires
|
|
equality constraints and variable non-negativity. ``linprog`` converts the
|
|
original problem to standard form by converting the simple bounds to upper
|
|
bound constraints, introducing non-negative slack variables for inequality
|
|
constraints, and expressing unbounded variables as the difference between
|
|
two non-negative variables. The problem is converted back to the original
|
|
form before results are reported.
|
|
|
|
References
|
|
----------
|
|
.. [4] Andersen, Erling D., and Knud D. Andersen. "The MOSEK interior point
|
|
optimizer for linear programming: an implementation of the
|
|
homogeneous algorithm." High performance optimization. Springer US,
|
|
2000. 197-232.
|
|
.. [6] Freund, Robert M. "Primal-Dual Interior-Point Methods for Linear
|
|
Programming based on Newton's Method." Unpublished Course Notes,
|
|
March 2004. Available 2/25/2017 at
|
|
https://ocw.mit.edu/courses/sloan-school-of-management/15-084j-nonlinear-programming-spring-2004/lecture-notes/lec14_int_pt_mthd.pdf
|
|
.. [8] Andersen, Erling D., and Knud D. Andersen. "Presolving in linear
|
|
programming." Mathematical Programming 71.2 (1995): 221-245.
|
|
.. [9] Bertsimas, Dimitris, and J. Tsitsiklis. "Introduction to linear
|
|
programming." Athena Scientific 1 (1997): 997.
|
|
.. [10] Andersen, Erling D., et al. Implementation of interior point
|
|
methods for large scale linear programming. HEC/Universite de
|
|
Geneve, 1996.
|
|
"""
|
|
pass
|
|
|
|
|
|
def _linprog_rs_doc(c, A_ub=None, b_ub=None, A_eq=None, b_eq=None,
|
|
bounds=None, method='interior-point', callback=None,
|
|
x0=None, maxiter=5000, disp=False, presolve=True,
|
|
tol=1e-12, autoscale=False, rr=True, maxupdate=10,
|
|
mast=False, pivot="mrc", **unknown_options):
|
|
r"""
|
|
Linear programming: minimize a linear objective function subject to linear
|
|
equality and inequality constraints using the revised simplex method.
|
|
|
|
.. deprecated:: 1.9.0
|
|
`method='revised simplex'` will be removed in SciPy 1.11.0.
|
|
It is replaced by `method='highs'` because the latter is
|
|
faster and more robust.
|
|
|
|
Linear programming solves problems of the following form:
|
|
|
|
.. math::
|
|
|
|
\min_x \ & c^T x \\
|
|
\mbox{such that} \ & A_{ub} x \leq b_{ub},\\
|
|
& A_{eq} x = b_{eq},\\
|
|
& l \leq x \leq u ,
|
|
|
|
where :math:`x` is a vector of decision variables; :math:`c`,
|
|
:math:`b_{ub}`, :math:`b_{eq}`, :math:`l`, and :math:`u` are vectors; and
|
|
:math:`A_{ub}` and :math:`A_{eq}` are matrices.
|
|
|
|
Alternatively, that's:
|
|
|
|
minimize::
|
|
|
|
c @ x
|
|
|
|
such that::
|
|
|
|
A_ub @ x <= b_ub
|
|
A_eq @ x == b_eq
|
|
lb <= x <= ub
|
|
|
|
Note that by default ``lb = 0`` and ``ub = None`` unless specified with
|
|
``bounds``.
|
|
|
|
Parameters
|
|
----------
|
|
c : 1-D array
|
|
The coefficients of the linear objective function to be minimized.
|
|
A_ub : 2-D array, optional
|
|
The inequality constraint matrix. Each row of ``A_ub`` specifies the
|
|
coefficients of a linear inequality constraint on ``x``.
|
|
b_ub : 1-D array, optional
|
|
The inequality constraint vector. Each element represents an
|
|
upper bound on the corresponding value of ``A_ub @ x``.
|
|
A_eq : 2-D array, optional
|
|
The equality constraint matrix. Each row of ``A_eq`` specifies the
|
|
coefficients of a linear equality constraint on ``x``.
|
|
b_eq : 1-D array, optional
|
|
The equality constraint vector. Each element of ``A_eq @ x`` must equal
|
|
the corresponding element of ``b_eq``.
|
|
bounds : sequence, optional
|
|
A sequence of ``(min, max)`` pairs for each element in ``x``, defining
|
|
the minimum and maximum values of that decision variable. Use ``None``
|
|
to indicate that there is no bound. By default, bounds are
|
|
``(0, None)`` (all decision variables are non-negative).
|
|
If a single tuple ``(min, max)`` is provided, then ``min`` and
|
|
``max`` will serve as bounds for all decision variables.
|
|
method : str
|
|
This is the method-specific documentation for 'revised simplex'.
|
|
:ref:`'highs' <optimize.linprog-highs>`,
|
|
:ref:`'highs-ds' <optimize.linprog-highs-ds>`,
|
|
:ref:`'highs-ipm' <optimize.linprog-highs-ipm>`,
|
|
:ref:`'interior-point' <optimize.linprog-interior-point>` (default),
|
|
and :ref:`'simplex' <optimize.linprog-simplex>` (legacy)
|
|
are also available.
|
|
callback : callable, optional
|
|
Callback function to be executed once per iteration.
|
|
x0 : 1-D array, optional
|
|
Guess values of the decision variables, which will be refined by
|
|
the optimization algorithm. This argument is currently used only by the
|
|
'revised simplex' method, and can only be used if `x0` represents a
|
|
basic feasible solution.
|
|
|
|
Options
|
|
-------
|
|
maxiter : int (default: 5000)
|
|
The maximum number of iterations to perform in either phase.
|
|
disp : bool (default: False)
|
|
Set to ``True`` if indicators of optimization status are to be printed
|
|
to the console each iteration.
|
|
presolve : bool (default: True)
|
|
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.
|
|
tol : float (default: 1e-12)
|
|
The tolerance which determines when a solution is "close enough" to
|
|
zero in Phase 1 to be considered a basic feasible solution or close
|
|
enough to positive to serve as an optimal solution.
|
|
autoscale : bool (default: False)
|
|
Set to ``True`` to automatically perform equilibration.
|
|
Consider using this option if the numerical values in the
|
|
constraints are separated by several orders of magnitude.
|
|
rr : bool (default: True)
|
|
Set to ``False`` to disable automatic redundancy removal.
|
|
maxupdate : int (default: 10)
|
|
The maximum number of updates performed on the LU factorization.
|
|
After this many updates is reached, the basis matrix is factorized
|
|
from scratch.
|
|
mast : bool (default: False)
|
|
Minimize Amortized Solve Time. If enabled, the average time to solve
|
|
a linear system using the basis factorization is measured. Typically,
|
|
the average solve time will decrease with each successive solve after
|
|
initial factorization, as factorization takes much more time than the
|
|
solve operation (and updates). Eventually, however, the updated
|
|
factorization becomes sufficiently complex that the average solve time
|
|
begins to increase. When this is detected, the basis is refactorized
|
|
from scratch. Enable this option to maximize speed at the risk of
|
|
nondeterministic behavior. Ignored if ``maxupdate`` is 0.
|
|
pivot : "mrc" or "bland" (default: "mrc")
|
|
Pivot rule: Minimum Reduced Cost ("mrc") or Bland's rule ("bland").
|
|
Choose Bland's rule if iteration limit is reached and cycling is
|
|
suspected.
|
|
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
|
|
-------
|
|
res : OptimizeResult
|
|
A :class:`scipy.optimize.OptimizeResult` consisting of the fields:
|
|
|
|
x : 1-D 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 : 1-D array
|
|
The (nominally positive) values of the slack variables,
|
|
``b_ub - A_ub @ x``.
|
|
con : 1-D 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 limit reached.
|
|
|
|
``2`` : Problem appears to be infeasible.
|
|
|
|
``3`` : Problem appears to be unbounded.
|
|
|
|
``4`` : Numerical difficulties encountered.
|
|
|
|
``5`` : Problem has no constraints; turn presolve on.
|
|
|
|
``6`` : Invalid guess provided.
|
|
|
|
message : str
|
|
A string descriptor of the exit status of the algorithm.
|
|
nit : int
|
|
The total number of iterations performed in all phases.
|
|
|
|
|
|
Notes
|
|
-----
|
|
Method *revised simplex* uses the revised simplex method as described in
|
|
[9]_, except that a factorization [11]_ of the basis matrix, rather than
|
|
its inverse, is efficiently maintained and used to solve the linear systems
|
|
at each iteration of the algorithm.
|
|
|
|
References
|
|
----------
|
|
.. [9] Bertsimas, Dimitris, and J. Tsitsiklis. "Introduction to linear
|
|
programming." Athena Scientific 1 (1997): 997.
|
|
.. [11] Bartels, Richard H. "A stabilization of the simplex method."
|
|
Journal in Numerische Mathematik 16.5 (1971): 414-434.
|
|
"""
|
|
pass
|
|
|
|
|
|
def _linprog_simplex_doc(c, A_ub=None, b_ub=None, A_eq=None, b_eq=None,
|
|
bounds=None, method='interior-point', callback=None,
|
|
maxiter=5000, disp=False, presolve=True,
|
|
tol=1e-12, autoscale=False, rr=True, bland=False,
|
|
**unknown_options):
|
|
r"""
|
|
Linear programming: minimize a linear objective function subject to linear
|
|
equality and inequality constraints using the tableau-based simplex method.
|
|
|
|
.. deprecated:: 1.9.0
|
|
`method='simplex'` will be removed in SciPy 1.11.0.
|
|
It is replaced by `method='highs'` because the latter is
|
|
faster and more robust.
|
|
|
|
Linear programming solves problems of the following form:
|
|
|
|
.. math::
|
|
|
|
\min_x \ & c^T x \\
|
|
\mbox{such that} \ & A_{ub} x \leq b_{ub},\\
|
|
& A_{eq} x = b_{eq},\\
|
|
& l \leq x \leq u ,
|
|
|
|
where :math:`x` is a vector of decision variables; :math:`c`,
|
|
:math:`b_{ub}`, :math:`b_{eq}`, :math:`l`, and :math:`u` are vectors; and
|
|
:math:`A_{ub}` and :math:`A_{eq}` are matrices.
|
|
|
|
Alternatively, that's:
|
|
|
|
minimize::
|
|
|
|
c @ x
|
|
|
|
such that::
|
|
|
|
A_ub @ x <= b_ub
|
|
A_eq @ x == b_eq
|
|
lb <= x <= ub
|
|
|
|
Note that by default ``lb = 0`` and ``ub = None`` unless specified with
|
|
``bounds``.
|
|
|
|
Parameters
|
|
----------
|
|
c : 1-D array
|
|
The coefficients of the linear objective function to be minimized.
|
|
A_ub : 2-D array, optional
|
|
The inequality constraint matrix. Each row of ``A_ub`` specifies the
|
|
coefficients of a linear inequality constraint on ``x``.
|
|
b_ub : 1-D array, optional
|
|
The inequality constraint vector. Each element represents an
|
|
upper bound on the corresponding value of ``A_ub @ x``.
|
|
A_eq : 2-D array, optional
|
|
The equality constraint matrix. Each row of ``A_eq`` specifies the
|
|
coefficients of a linear equality constraint on ``x``.
|
|
b_eq : 1-D array, optional
|
|
The equality constraint vector. Each element of ``A_eq @ x`` must equal
|
|
the corresponding element of ``b_eq``.
|
|
bounds : sequence, optional
|
|
A sequence of ``(min, max)`` pairs for each element in ``x``, defining
|
|
the minimum and maximum values of that decision variable. Use ``None``
|
|
to indicate that there is no bound. By default, bounds are
|
|
``(0, None)`` (all decision variables are non-negative).
|
|
If a single tuple ``(min, max)`` is provided, then ``min`` and
|
|
``max`` will serve as bounds for all decision variables.
|
|
method : str
|
|
This is the method-specific documentation for 'simplex'.
|
|
:ref:`'highs' <optimize.linprog-highs>`,
|
|
:ref:`'highs-ds' <optimize.linprog-highs-ds>`,
|
|
:ref:`'highs-ipm' <optimize.linprog-highs-ipm>`,
|
|
:ref:`'interior-point' <optimize.linprog-interior-point>` (default),
|
|
and :ref:`'revised simplex' <optimize.linprog-revised_simplex>`
|
|
are also available.
|
|
callback : callable, optional
|
|
Callback function to be executed once per iteration.
|
|
|
|
Options
|
|
-------
|
|
maxiter : int (default: 5000)
|
|
The maximum number of iterations to perform in either phase.
|
|
disp : bool (default: False)
|
|
Set to ``True`` if indicators of optimization status are to be printed
|
|
to the console each iteration.
|
|
presolve : bool (default: True)
|
|
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.
|
|
tol : float (default: 1e-12)
|
|
The tolerance which determines when a solution is "close enough" to
|
|
zero in Phase 1 to be considered a basic feasible solution or close
|
|
enough to positive to serve as an optimal solution.
|
|
autoscale : bool (default: False)
|
|
Set to ``True`` to automatically perform equilibration.
|
|
Consider using this option if the numerical values in the
|
|
constraints are separated by several orders of magnitude.
|
|
rr : bool (default: True)
|
|
Set to ``False`` to disable automatic redundancy removal.
|
|
bland : bool
|
|
If True, use Bland's anti-cycling rule [3]_ to choose pivots to
|
|
prevent cycling. If False, choose pivots which should lead to a
|
|
converged solution more quickly. The latter method is subject to
|
|
cycling (non-convergence) in rare instances.
|
|
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
|
|
-------
|
|
res : OptimizeResult
|
|
A :class:`scipy.optimize.OptimizeResult` consisting of the fields:
|
|
|
|
x : 1-D 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 : 1-D array
|
|
The (nominally positive) values of the slack variables,
|
|
``b_ub - A_ub @ x``.
|
|
con : 1-D 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 limit reached.
|
|
|
|
``2`` : Problem appears to be infeasible.
|
|
|
|
``3`` : Problem appears to be unbounded.
|
|
|
|
``4`` : Numerical difficulties encountered.
|
|
|
|
message : str
|
|
A string descriptor of the exit status of the algorithm.
|
|
nit : int
|
|
The total number of iterations performed in all phases.
|
|
|
|
References
|
|
----------
|
|
.. [1] Dantzig, George B., Linear programming and extensions. Rand
|
|
Corporation Research Study Princeton Univ. Press, Princeton, NJ,
|
|
1963
|
|
.. [2] Hillier, S.H. and Lieberman, G.J. (1995), "Introduction to
|
|
Mathematical Programming", McGraw-Hill, Chapter 4.
|
|
.. [3] Bland, Robert G. New finite pivoting rules for the simplex method.
|
|
Mathematics of Operations Research (2), 1977: pp. 103-107.
|
|
"""
|
|
pass
|