Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.8/site-packages/scipy/optimize/_linprog.py: 16%
103 statements
« prev ^ index » next coverage.py v7.3.2, created at 2023-12-12 06:31 +0000
1"""
2A top-level linear programming interface.
4.. versionadded:: 0.15.0
6Functions
7---------
8.. autosummary::
9 :toctree: generated/
11 linprog
12 linprog_verbose_callback
13 linprog_terse_callback
15"""
17import numpy as np
19from ._optimize import OptimizeResult, OptimizeWarning
20from warnings import warn
21from ._linprog_highs import _linprog_highs
22from ._linprog_ip import _linprog_ip
23from ._linprog_simplex import _linprog_simplex
24from ._linprog_rs import _linprog_rs
25from ._linprog_doc import (_linprog_highs_doc, _linprog_ip_doc,
26 _linprog_rs_doc, _linprog_simplex_doc,
27 _linprog_highs_ipm_doc, _linprog_highs_ds_doc)
28from ._linprog_util import (
29 _parse_linprog, _presolve, _get_Abc, _LPProblem, _autoscale,
30 _postsolve, _check_result, _display_summary)
31from copy import deepcopy
33__all__ = ['linprog', 'linprog_verbose_callback', 'linprog_terse_callback']
35__docformat__ = "restructuredtext en"
37LINPROG_METHODS = ['simplex', 'revised simplex', 'interior-point', 'highs', 'highs-ds', 'highs-ipm']
40def linprog_verbose_callback(res):
41 """
42 A sample callback function demonstrating the linprog callback interface.
43 This callback produces detailed output to sys.stdout before each iteration
44 and after the final iteration of the simplex algorithm.
46 Parameters
47 ----------
48 res : A `scipy.optimize.OptimizeResult` consisting of the following fields:
50 x : 1-D array
51 The independent variable vector which optimizes the linear
52 programming problem.
53 fun : float
54 Value of the objective function.
55 success : bool
56 True if the algorithm succeeded in finding an optimal solution.
57 slack : 1-D array
58 The values of the slack variables. Each slack variable corresponds
59 to an inequality constraint. If the slack is zero, then the
60 corresponding constraint is active.
61 con : 1-D array
62 The (nominally zero) residuals of the equality constraints, that is,
63 ``b - A_eq @ x``
64 phase : int
65 The phase of the optimization being executed. In phase 1 a basic
66 feasible solution is sought and the T has an additional row
67 representing an alternate objective function.
68 status : int
69 An integer representing the exit status of the optimization::
71 0 : Optimization terminated successfully
72 1 : Iteration limit reached
73 2 : Problem appears to be infeasible
74 3 : Problem appears to be unbounded
75 4 : Serious numerical difficulties encountered
77 nit : int
78 The number of iterations performed.
79 message : str
80 A string descriptor of the exit status of the optimization.
81 """
82 x = res['x']
83 fun = res['fun']
84 phase = res['phase']
85 status = res['status']
86 nit = res['nit']
87 message = res['message']
88 complete = res['complete']
90 saved_printoptions = np.get_printoptions()
91 np.set_printoptions(linewidth=500,
92 formatter={'float': lambda x: "{0: 12.4f}".format(x)})
93 if status:
94 print('--------- Simplex Early Exit -------\n')
95 print('The simplex method exited early with status {0:d}'.format(status))
96 print(message)
97 elif complete:
98 print('--------- Simplex Complete --------\n')
99 print('Iterations required: {}'.format(nit))
100 else:
101 print('--------- Iteration {0:d} ---------\n'.format(nit))
103 if nit > 0:
104 if phase == 1:
105 print('Current Pseudo-Objective Value:')
106 else:
107 print('Current Objective Value:')
108 print('f = ', fun)
109 print()
110 print('Current Solution Vector:')
111 print('x = ', x)
112 print()
114 np.set_printoptions(**saved_printoptions)
117def linprog_terse_callback(res):
118 """
119 A sample callback function demonstrating the linprog callback interface.
120 This callback produces brief output to sys.stdout before each iteration
121 and after the final iteration of the simplex algorithm.
123 Parameters
124 ----------
125 res : A `scipy.optimize.OptimizeResult` consisting of the following fields:
127 x : 1-D array
128 The independent variable vector which optimizes the linear
129 programming problem.
130 fun : float
131 Value of the objective function.
132 success : bool
133 True if the algorithm succeeded in finding an optimal solution.
134 slack : 1-D array
135 The values of the slack variables. Each slack variable corresponds
136 to an inequality constraint. If the slack is zero, then the
137 corresponding constraint is active.
138 con : 1-D array
139 The (nominally zero) residuals of the equality constraints, that is,
140 ``b - A_eq @ x``.
141 phase : int
142 The phase of the optimization being executed. In phase 1 a basic
143 feasible solution is sought and the T has an additional row
144 representing an alternate objective function.
145 status : int
146 An integer representing the exit status of the optimization::
148 0 : Optimization terminated successfully
149 1 : Iteration limit reached
150 2 : Problem appears to be infeasible
151 3 : Problem appears to be unbounded
152 4 : Serious numerical difficulties encountered
154 nit : int
155 The number of iterations performed.
156 message : str
157 A string descriptor of the exit status of the optimization.
158 """
159 nit = res['nit']
160 x = res['x']
162 if nit == 0:
163 print("Iter: X:")
164 print("{0: <5d} ".format(nit), end="")
165 print(x)
168def linprog(c, A_ub=None, b_ub=None, A_eq=None, b_eq=None,
169 bounds=None, method='highs', callback=None,
170 options=None, x0=None, integrality=None):
171 r"""
172 Linear programming: minimize a linear objective function subject to linear
173 equality and inequality constraints.
175 Linear programming solves problems of the following form:
177 .. math::
179 \min_x \ & c^T x \\
180 \mbox{such that} \ & A_{ub} x \leq b_{ub},\\
181 & A_{eq} x = b_{eq},\\
182 & l \leq x \leq u ,
184 where :math:`x` is a vector of decision variables; :math:`c`,
185 :math:`b_{ub}`, :math:`b_{eq}`, :math:`l`, and :math:`u` are vectors; and
186 :math:`A_{ub}` and :math:`A_{eq}` are matrices.
188 Alternatively, that's:
190 minimize::
192 c @ x
194 such that::
196 A_ub @ x <= b_ub
197 A_eq @ x == b_eq
198 lb <= x <= ub
200 Note that by default ``lb = 0`` and ``ub = None`` unless specified with
201 ``bounds``.
203 Parameters
204 ----------
205 c : 1-D array
206 The coefficients of the linear objective function to be minimized.
207 A_ub : 2-D array, optional
208 The inequality constraint matrix. Each row of ``A_ub`` specifies the
209 coefficients of a linear inequality constraint on ``x``.
210 b_ub : 1-D array, optional
211 The inequality constraint vector. Each element represents an
212 upper bound on the corresponding value of ``A_ub @ x``.
213 A_eq : 2-D array, optional
214 The equality constraint matrix. Each row of ``A_eq`` specifies the
215 coefficients of a linear equality constraint on ``x``.
216 b_eq : 1-D array, optional
217 The equality constraint vector. Each element of ``A_eq @ x`` must equal
218 the corresponding element of ``b_eq``.
219 bounds : sequence, optional
220 A sequence of ``(min, max)`` pairs for each element in ``x``, defining
221 the minimum and maximum values of that decision variable. Use ``None``
222 to indicate that there is no bound. By default, bounds are
223 ``(0, None)`` (all decision variables are non-negative).
224 If a single tuple ``(min, max)`` is provided, then ``min`` and
225 ``max`` will serve as bounds for all decision variables.
226 method : str, optional
227 The algorithm used to solve the standard form problem.
228 :ref:`'highs' <optimize.linprog-highs>` (default),
229 :ref:`'highs-ds' <optimize.linprog-highs-ds>`,
230 :ref:`'highs-ipm' <optimize.linprog-highs-ipm>`,
231 :ref:`'interior-point' <optimize.linprog-interior-point>` (legacy),
232 :ref:`'revised simplex' <optimize.linprog-revised_simplex>` (legacy),
233 and
234 :ref:`'simplex' <optimize.linprog-simplex>` (legacy) are supported.
235 The legacy methods are deprecated and will be removed in SciPy 1.11.0.
236 callback : callable, optional
237 If a callback function is provided, it will be called at least once per
238 iteration of the algorithm. The callback function must accept a single
239 `scipy.optimize.OptimizeResult` consisting of the following fields:
241 x : 1-D array
242 The current solution vector.
243 fun : float
244 The current value of the objective function ``c @ x``.
245 success : bool
246 ``True`` when the algorithm has completed successfully.
247 slack : 1-D array
248 The (nominally positive) values of the slack,
249 ``b_ub - A_ub @ x``.
250 con : 1-D array
251 The (nominally zero) residuals of the equality constraints,
252 ``b_eq - A_eq @ x``.
253 phase : int
254 The phase of the algorithm being executed.
255 status : int
256 An integer representing the status of the algorithm.
258 ``0`` : Optimization proceeding nominally.
260 ``1`` : Iteration limit reached.
262 ``2`` : Problem appears to be infeasible.
264 ``3`` : Problem appears to be unbounded.
266 ``4`` : Numerical difficulties encountered.
268 nit : int
269 The current iteration number.
270 message : str
271 A string descriptor of the algorithm status.
273 Callback functions are not currently supported by the HiGHS methods.
275 options : dict, optional
276 A dictionary of solver options. All methods accept the following
277 options:
279 maxiter : int
280 Maximum number of iterations to perform.
281 Default: see method-specific documentation.
282 disp : bool
283 Set to ``True`` to print convergence messages.
284 Default: ``False``.
285 presolve : bool
286 Set to ``False`` to disable automatic presolve.
287 Default: ``True``.
289 All methods except the HiGHS solvers also accept:
291 tol : float
292 A tolerance which determines when a residual is "close enough" to
293 zero to be considered exactly zero.
294 autoscale : bool
295 Set to ``True`` to automatically perform equilibration.
296 Consider using this option if the numerical values in the
297 constraints are separated by several orders of magnitude.
298 Default: ``False``.
299 rr : bool
300 Set to ``False`` to disable automatic redundancy removal.
301 Default: ``True``.
302 rr_method : string
303 Method used to identify and remove redundant rows from the
304 equality constraint matrix after presolve. For problems with
305 dense input, the available methods for redundancy removal are:
307 "SVD":
308 Repeatedly performs singular value decomposition on
309 the matrix, detecting redundant rows based on nonzeros
310 in the left singular vectors that correspond with
311 zero singular values. May be fast when the matrix is
312 nearly full rank.
313 "pivot":
314 Uses the algorithm presented in [5]_ to identify
315 redundant rows.
316 "ID":
317 Uses a randomized interpolative decomposition.
318 Identifies columns of the matrix transpose not used in
319 a full-rank interpolative decomposition of the matrix.
320 None:
321 Uses "svd" if the matrix is nearly full rank, that is,
322 the difference between the matrix rank and the number
323 of rows is less than five. If not, uses "pivot". The
324 behavior of this default is subject to change without
325 prior notice.
327 Default: None.
328 For problems with sparse input, this option is ignored, and the
329 pivot-based algorithm presented in [5]_ is used.
331 For method-specific options, see
332 :func:`show_options('linprog') <show_options>`.
334 x0 : 1-D array, optional
335 Guess values of the decision variables, which will be refined by
336 the optimization algorithm. This argument is currently used only by the
337 'revised simplex' method, and can only be used if `x0` represents a
338 basic feasible solution.
340 integrality : 1-D array or int, optional
341 Indicates the type of integrality constraint on each decision variable.
343 ``0`` : Continuous variable; no integrality constraint.
345 ``1`` : Integer variable; decision variable must be an integer
346 within `bounds`.
348 ``2`` : Semi-continuous variable; decision variable must be within
349 `bounds` or take value ``0``.
351 ``3`` : Semi-integer variable; decision variable must be an integer
352 within `bounds` or take value ``0``.
354 By default, all variables are continuous.
356 For mixed integrality constraints, supply an array of shape `c.shape`.
357 To infer a constraint on each decision variable from shorter inputs,
358 the argument will be broadcasted to `c.shape` using `np.broadcast_to`.
360 This argument is currently used only by the ``'highs'`` method and
361 ignored otherwise.
363 Returns
364 -------
365 res : OptimizeResult
366 A :class:`scipy.optimize.OptimizeResult` consisting of the fields
367 below. Note that the return types of the fields may depend on whether
368 the optimization was successful, therefore it is recommended to check
369 `OptimizeResult.status` before relying on the other fields:
371 x : 1-D array
372 The values of the decision variables that minimizes the
373 objective function while satisfying the constraints.
374 fun : float
375 The optimal value of the objective function ``c @ x``.
376 slack : 1-D array
377 The (nominally positive) values of the slack variables,
378 ``b_ub - A_ub @ x``.
379 con : 1-D array
380 The (nominally zero) residuals of the equality constraints,
381 ``b_eq - A_eq @ x``.
382 success : bool
383 ``True`` when the algorithm succeeds in finding an optimal
384 solution.
385 status : int
386 An integer representing the exit status of the algorithm.
388 ``0`` : Optimization terminated successfully.
390 ``1`` : Iteration limit reached.
392 ``2`` : Problem appears to be infeasible.
394 ``3`` : Problem appears to be unbounded.
396 ``4`` : Numerical difficulties encountered.
398 nit : int
399 The total number of iterations performed in all phases.
400 message : str
401 A string descriptor of the exit status of the algorithm.
403 See Also
404 --------
405 show_options : Additional options accepted by the solvers.
407 Notes
408 -----
409 This section describes the available solvers that can be selected by the
410 'method' parameter.
412 `'highs-ds'` and
413 `'highs-ipm'` are interfaces to the
414 HiGHS simplex and interior-point method solvers [13]_, respectively.
415 `'highs'` (default) chooses between
416 the two automatically. These are the fastest linear
417 programming solvers in SciPy, especially for large, sparse problems;
418 which of these two is faster is problem-dependent.
419 The other solvers (`'interior-point'`, `'revised simplex'`, and
420 `'simplex'`) are legacy methods and will be removed in SciPy 1.11.0.
422 Method *highs-ds* is a wrapper of the C++ high performance dual
423 revised simplex implementation (HSOL) [13]_, [14]_. Method *highs-ipm*
424 is a wrapper of a C++ implementation of an **i**\ nterior-\ **p**\ oint
425 **m**\ ethod [13]_; it features a crossover routine, so it is as accurate
426 as a simplex solver. Method *highs* chooses between the two automatically.
427 For new code involving `linprog`, we recommend explicitly choosing one of
428 these three method values.
430 .. versionadded:: 1.6.0
432 Method *interior-point* uses the primal-dual path following algorithm
433 as outlined in [4]_. This algorithm supports sparse constraint matrices and
434 is typically faster than the simplex methods, especially for large, sparse
435 problems. Note, however, that the solution returned may be slightly less
436 accurate than those of the simplex methods and will not, in general,
437 correspond with a vertex of the polytope defined by the constraints.
439 .. versionadded:: 1.0.0
441 Method *revised simplex* uses the revised simplex method as described in
442 [9]_, except that a factorization [11]_ of the basis matrix, rather than
443 its inverse, is efficiently maintained and used to solve the linear systems
444 at each iteration of the algorithm.
446 .. versionadded:: 1.3.0
448 Method *simplex* uses a traditional, full-tableau implementation of
449 Dantzig's simplex algorithm [1]_, [2]_ (*not* the
450 Nelder-Mead simplex). This algorithm is included for backwards
451 compatibility and educational purposes.
453 .. versionadded:: 0.15.0
455 Before applying *interior-point*, *revised simplex*, or *simplex*,
456 a presolve procedure based on [8]_ attempts
457 to identify trivial infeasibilities, trivial unboundedness, and potential
458 problem simplifications. Specifically, it checks for:
460 - rows of zeros in ``A_eq`` or ``A_ub``, representing trivial constraints;
461 - columns of zeros in ``A_eq`` `and` ``A_ub``, representing unconstrained
462 variables;
463 - column singletons in ``A_eq``, representing fixed variables; and
464 - column singletons in ``A_ub``, representing simple bounds.
466 If presolve reveals that the problem is unbounded (e.g. an unconstrained
467 and unbounded variable has negative cost) or infeasible (e.g., a row of
468 zeros in ``A_eq`` corresponds with a nonzero in ``b_eq``), the solver
469 terminates with the appropriate status code. Note that presolve terminates
470 as soon as any sign of unboundedness is detected; consequently, a problem
471 may be reported as unbounded when in reality the problem is infeasible
472 (but infeasibility has not been detected yet). Therefore, if it is
473 important to know whether the problem is actually infeasible, solve the
474 problem again with option ``presolve=False``.
476 If neither infeasibility nor unboundedness are detected in a single pass
477 of the presolve, bounds are tightened where possible and fixed
478 variables are removed from the problem. Then, linearly dependent rows
479 of the ``A_eq`` matrix are removed, (unless they represent an
480 infeasibility) to avoid numerical difficulties in the primary solve
481 routine. Note that rows that are nearly linearly dependent (within a
482 prescribed tolerance) may also be removed, which can change the optimal
483 solution in rare cases. If this is a concern, eliminate redundancy from
484 your problem formulation and run with option ``rr=False`` or
485 ``presolve=False``.
487 Several potential improvements can be made here: additional presolve
488 checks outlined in [8]_ should be implemented, the presolve routine should
489 be run multiple times (until no further simplifications can be made), and
490 more of the efficiency improvements from [5]_ should be implemented in the
491 redundancy removal routines.
493 After presolve, the problem is transformed to standard form by converting
494 the (tightened) simple bounds to upper bound constraints, introducing
495 non-negative slack variables for inequality constraints, and expressing
496 unbounded variables as the difference between two non-negative variables.
497 Optionally, the problem is automatically scaled via equilibration [12]_.
498 The selected algorithm solves the standard form problem, and a
499 postprocessing routine converts the result to a solution to the original
500 problem.
502 References
503 ----------
504 .. [1] Dantzig, George B., Linear programming and extensions. Rand
505 Corporation Research Study Princeton Univ. Press, Princeton, NJ,
506 1963
507 .. [2] Hillier, S.H. and Lieberman, G.J. (1995), "Introduction to
508 Mathematical Programming", McGraw-Hill, Chapter 4.
509 .. [3] Bland, Robert G. New finite pivoting rules for the simplex method.
510 Mathematics of Operations Research (2), 1977: pp. 103-107.
511 .. [4] Andersen, Erling D., and Knud D. Andersen. "The MOSEK interior point
512 optimizer for linear programming: an implementation of the
513 homogeneous algorithm." High performance optimization. Springer US,
514 2000. 197-232.
515 .. [5] Andersen, Erling D. "Finding all linearly dependent rows in
516 large-scale linear programming." Optimization Methods and Software
517 6.3 (1995): 219-227.
518 .. [6] Freund, Robert M. "Primal-Dual Interior-Point Methods for Linear
519 Programming based on Newton's Method." Unpublished Course Notes,
520 March 2004. Available 2/25/2017 at
521 https://ocw.mit.edu/courses/sloan-school-of-management/15-084j-nonlinear-programming-spring-2004/lecture-notes/lec14_int_pt_mthd.pdf
522 .. [7] Fourer, Robert. "Solving Linear Programs by Interior-Point Methods."
523 Unpublished Course Notes, August 26, 2005. Available 2/25/2017 at
524 http://www.4er.org/CourseNotes/Book%20B/B-III.pdf
525 .. [8] Andersen, Erling D., and Knud D. Andersen. "Presolving in linear
526 programming." Mathematical Programming 71.2 (1995): 221-245.
527 .. [9] Bertsimas, Dimitris, and J. Tsitsiklis. "Introduction to linear
528 programming." Athena Scientific 1 (1997): 997.
529 .. [10] Andersen, Erling D., et al. Implementation of interior point
530 methods for large scale linear programming. HEC/Universite de
531 Geneve, 1996.
532 .. [11] Bartels, Richard H. "A stabilization of the simplex method."
533 Journal in Numerische Mathematik 16.5 (1971): 414-434.
534 .. [12] Tomlin, J. A. "On scaling linear programming problems."
535 Mathematical Programming Study 4 (1975): 146-166.
536 .. [13] Huangfu, Q., Galabova, I., Feldmeier, M., and Hall, J. A. J.
537 "HiGHS - high performance software for linear optimization."
538 https://highs.dev/
539 .. [14] Huangfu, Q. and Hall, J. A. J. "Parallelizing the dual revised
540 simplex method." Mathematical Programming Computation, 10 (1),
541 119-142, 2018. DOI: 10.1007/s12532-017-0130-5
543 Examples
544 --------
545 Consider the following problem:
547 .. math::
549 \min_{x_0, x_1} \ -x_0 + 4x_1 & \\
550 \mbox{such that} \ -3x_0 + x_1 & \leq 6,\\
551 -x_0 - 2x_1 & \geq -4,\\
552 x_1 & \geq -3.
554 The problem is not presented in the form accepted by `linprog`. This is
555 easily remedied by converting the "greater than" inequality
556 constraint to a "less than" inequality constraint by
557 multiplying both sides by a factor of :math:`-1`. Note also that the last
558 constraint is really the simple bound :math:`-3 \leq x_1 \leq \infty`.
559 Finally, since there are no bounds on :math:`x_0`, we must explicitly
560 specify the bounds :math:`-\infty \leq x_0 \leq \infty`, as the
561 default is for variables to be non-negative. After collecting coeffecients
562 into arrays and tuples, the input for this problem is:
564 >>> from scipy.optimize import linprog
565 >>> c = [-1, 4]
566 >>> A = [[-3, 1], [1, 2]]
567 >>> b = [6, 4]
568 >>> x0_bounds = (None, None)
569 >>> x1_bounds = (-3, None)
570 >>> res = linprog(c, A_ub=A, b_ub=b, bounds=[x0_bounds, x1_bounds])
571 >>> res.fun
572 -22.0
573 >>> res.x
574 array([10., -3.])
575 >>> res.message
576 'Optimization terminated successfully. (HiGHS Status 7: Optimal)'
578 The marginals (AKA dual values / shadow prices / Lagrange multipliers)
579 and residuals (slacks) are also available.
581 >>> res.ineqlin
582 residual: [ 3.900e+01 0.000e+00]
583 marginals: [-0.000e+00 -1.000e+00]
585 For example, because the marginal associated with the second inequality
586 constraint is -1, we expect the optimal value of the objective function
587 to decrease by ``eps`` if we add a small amount ``eps`` to the right hand
588 side of the second inequality constraint:
590 >>> eps = 0.05
591 >>> b[1] += eps
592 >>> linprog(c, A_ub=A, b_ub=b, bounds=[x0_bounds, x1_bounds]).fun
593 -22.05
595 Also, because the residual on the first inequality constraint is 39, we
596 can decrease the right hand side of the first constraint by 39 without
597 affecting the optimal solution.
599 >>> b = [6, 4] # reset to original values
600 >>> b[0] -= 39
601 >>> linprog(c, A_ub=A, b_ub=b, bounds=[x0_bounds, x1_bounds]).fun
602 -22.0
604 """
606 meth = method.lower()
607 methods = {"highs", "highs-ds", "highs-ipm",
608 "simplex", "revised simplex", "interior-point"}
610 if meth not in methods:
611 raise ValueError(f"Unknown solver '{method}'")
613 if x0 is not None and meth != "revised simplex":
614 warning_message = "x0 is used only when method is 'revised simplex'. "
615 warn(warning_message, OptimizeWarning)
617 if np.any(integrality) and not meth == "highs":
618 integrality = None
619 warning_message = ("Only `method='highs'` supports integer "
620 "constraints. Ignoring `integrality`.")
621 warn(warning_message, OptimizeWarning)
622 elif np.any(integrality):
623 integrality = np.broadcast_to(integrality, np.shape(c))
625 lp = _LPProblem(c, A_ub, b_ub, A_eq, b_eq, bounds, x0, integrality)
626 lp, solver_options = _parse_linprog(lp, options, meth)
627 tol = solver_options.get('tol', 1e-9)
629 # Give unmodified problem to HiGHS
630 if meth.startswith('highs'):
631 if callback is not None:
632 raise NotImplementedError("HiGHS solvers do not support the "
633 "callback interface.")
634 highs_solvers = {'highs-ipm': 'ipm', 'highs-ds': 'simplex',
635 'highs': None}
637 sol = _linprog_highs(lp, solver=highs_solvers[meth],
638 **solver_options)
639 sol['status'], sol['message'] = (
640 _check_result(sol['x'], sol['fun'], sol['status'], sol['slack'],
641 sol['con'], lp.bounds, tol, sol['message']))
642 sol['success'] = sol['status'] == 0
643 return OptimizeResult(sol)
645 warn(f"`method='{meth}'` is deprecated and will be removed in SciPy "
646 "1.11.0. Please use one of the HiGHS solvers (e.g. "
647 "`method='highs'`) in new code.", DeprecationWarning, stacklevel=2)
649 iteration = 0
650 complete = False # will become True if solved in presolve
651 undo = []
653 # Keep the original arrays to calculate slack/residuals for original
654 # problem.
655 lp_o = deepcopy(lp)
657 # Solve trivial problem, eliminate variables, tighten bounds, etc.
658 rr_method = solver_options.pop('rr_method', None) # need to pop these;
659 rr = solver_options.pop('rr', True) # they're not passed to methods
660 c0 = 0 # we might get a constant term in the objective
661 if solver_options.pop('presolve', True):
662 (lp, c0, x, undo, complete, status, message) = _presolve(lp, rr,
663 rr_method,
664 tol)
666 C, b_scale = 1, 1 # for trivial unscaling if autoscale is not used
667 postsolve_args = (lp_o._replace(bounds=lp.bounds), undo, C, b_scale)
669 if not complete:
670 A, b, c, c0, x0 = _get_Abc(lp, c0)
671 if solver_options.pop('autoscale', False):
672 A, b, c, x0, C, b_scale = _autoscale(A, b, c, x0)
673 postsolve_args = postsolve_args[:-2] + (C, b_scale)
675 if meth == 'simplex':
676 x, status, message, iteration = _linprog_simplex(
677 c, c0=c0, A=A, b=b, callback=callback,
678 postsolve_args=postsolve_args, **solver_options)
679 elif meth == 'interior-point':
680 x, status, message, iteration = _linprog_ip(
681 c, c0=c0, A=A, b=b, callback=callback,
682 postsolve_args=postsolve_args, **solver_options)
683 elif meth == 'revised simplex':
684 x, status, message, iteration = _linprog_rs(
685 c, c0=c0, A=A, b=b, x0=x0, callback=callback,
686 postsolve_args=postsolve_args, **solver_options)
688 # Eliminate artificial variables, re-introduce presolved variables, etc.
689 disp = solver_options.get('disp', False)
691 x, fun, slack, con = _postsolve(x, postsolve_args, complete)
693 status, message = _check_result(x, fun, status, slack, con, lp_o.bounds, tol, message)
695 if disp:
696 _display_summary(message, status, fun, iteration)
698 sol = {
699 'x': x,
700 'fun': fun,
701 'slack': slack,
702 'con': con,
703 'status': status,
704 'message': message,
705 'nit': iteration,
706 'success': status == 0}
708 return OptimizeResult(sol)