| """ | |
| 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 broadcast 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. | |
| Currently, ``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. | |
| Currently, ``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 combating 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 | |