Coverage for /usr/lib/python3/dist-packages/scipy/optimize/_linprog_doc.py: 50%

1""" 

2Created on Sat Aug 22 19:49:17 2020 

3 

4@author: matth 

5""" 

6 

7 

8def _linprog_highs_doc(c, A_ub=None, b_ub=None, A_eq=None, b_eq=None, 

9 bounds=None, method='highs', callback=None, 

10 maxiter=None, disp=False, presolve=True, 

11 time_limit=None, 

12 dual_feasibility_tolerance=None, 

13 primal_feasibility_tolerance=None, 

14 ipm_optimality_tolerance=None, 

15 simplex_dual_edge_weight_strategy=None, 

16 mip_rel_gap=None, 

17 **unknown_options): 

18 r""" 

19 Linear programming: minimize a linear objective function subject to linear 

20 equality and inequality constraints using one of the HiGHS solvers. 

21 

22 Linear programming solves problems of the following form: 

23 

24 .. math:: 

25 

26 \min_x \ & c^T x \\ 

27 \mbox{such that} \ & A_{ub} x \leq b_{ub},\\ 

28 & A_{eq} x = b_{eq},\\ 

29 & l \leq x \leq u , 

30 

31 where :math:`x` is a vector of decision variables; :math:`c`, 

32 :math:`b_{ub}`, :math:`b_{eq}`, :math:`l`, and :math:`u` are vectors; and 

33 :math:`A_{ub}` and :math:`A_{eq}` are matrices. 

34 

35 Alternatively, that's: 

36 

37 minimize:: 

38 

39 c @ x 

40 

41 such that:: 

42 

43 A_ub @ x <= b_ub 

44 A_eq @ x == b_eq 

45 lb <= x <= ub 

46 

47 Note that by default ``lb = 0`` and ``ub = None`` unless specified with 

48 ``bounds``. 

49 

50 Parameters 

51 ---------- 

52 c : 1-D array 

53 The coefficients of the linear objective function to be minimized. 

54 A_ub : 2-D array, optional 

55 The inequality constraint matrix. Each row of ``A_ub`` specifies the 

56 coefficients of a linear inequality constraint on ``x``. 

57 b_ub : 1-D array, optional 

58 The inequality constraint vector. Each element represents an 

59 upper bound on the corresponding value of ``A_ub @ x``. 

60 A_eq : 2-D array, optional 

61 The equality constraint matrix. Each row of ``A_eq`` specifies the 

62 coefficients of a linear equality constraint on ``x``. 

63 b_eq : 1-D array, optional 

64 The equality constraint vector. Each element of ``A_eq @ x`` must equal 

65 the corresponding element of ``b_eq``. 

66 bounds : sequence, optional 

67 A sequence of ``(min, max)`` pairs for each element in ``x``, defining 

68 the minimum and maximum values of that decision variable. Use ``None`` 

69 to indicate that there is no bound. By default, bounds are 

70 ``(0, None)`` (all decision variables are non-negative). 

71 If a single tuple ``(min, max)`` is provided, then ``min`` and 

72 ``max`` will serve as bounds for all decision variables. 

73 method : str 

74 

75 This is the method-specific documentation for 'highs', which chooses 

76 automatically between 

77 :ref:`'highs-ds' <optimize.linprog-highs-ds>` and 

78 :ref:`'highs-ipm' <optimize.linprog-highs-ipm>`. 

79 :ref:`'interior-point' <optimize.linprog-interior-point>` (default), 

80 :ref:`'revised simplex' <optimize.linprog-revised_simplex>`, and 

81 :ref:`'simplex' <optimize.linprog-simplex>` (legacy) 

82 are also available. 

83 integrality : 1-D array or int, optional 

84 Indicates the type of integrality constraint on each decision variable. 

85 

86 ``0`` : Continuous variable; no integrality constraint. 

87 

88 ``1`` : Integer variable; decision variable must be an integer 

89 within `bounds`. 

90 

91 ``2`` : Semi-continuous variable; decision variable must be within 

92 `bounds` or take value ``0``. 

93 

94 ``3`` : Semi-integer variable; decision variable must be an integer 

95 within `bounds` or take value ``0``. 

96 

97 By default, all variables are continuous. 

98 

99 For mixed integrality constraints, supply an array of shape `c.shape`. 

100 To infer a constraint on each decision variable from shorter inputs, 

101 the argument will be broadcasted to `c.shape` using `np.broadcast_to`. 

102 

103 This argument is currently used only by the ``'highs'`` method and 

104 ignored otherwise. 

105 

106 Options 

107 ------- 

108 maxiter : int 

109 The maximum number of iterations to perform in either phase. 

110 For :ref:`'highs-ipm' <optimize.linprog-highs-ipm>`, this does not 

111 include the number of crossover iterations. Default is the largest 

112 possible value for an ``int`` on the platform. 

113 disp : bool (default: ``False``) 

114 Set to ``True`` if indicators of optimization status are to be 

115 printed to the console during optimization. 

116 presolve : bool (default: ``True``) 

117 Presolve attempts to identify trivial infeasibilities, 

118 identify trivial unboundedness, and simplify the problem before 

119 sending it to the main solver. It is generally recommended 

120 to keep the default setting ``True``; set to ``False`` if 

121 presolve is to be disabled. 

122 time_limit : float 

123 The maximum time in seconds allotted to solve the problem; 

124 default is the largest possible value for a ``double`` on the 

125 platform. 

126 dual_feasibility_tolerance : double (default: 1e-07) 

127 Dual feasibility tolerance for 

128 :ref:`'highs-ds' <optimize.linprog-highs-ds>`. 

129 The minimum of this and ``primal_feasibility_tolerance`` 

130 is used for the feasibility tolerance of 

131 :ref:`'highs-ipm' <optimize.linprog-highs-ipm>`. 

132 primal_feasibility_tolerance : double (default: 1e-07) 

133 Primal feasibility tolerance for 

134 :ref:`'highs-ds' <optimize.linprog-highs-ds>`. 

135 The minimum of this and ``dual_feasibility_tolerance`` 

136 is used for the feasibility tolerance of 

137 :ref:`'highs-ipm' <optimize.linprog-highs-ipm>`. 

138 ipm_optimality_tolerance : double (default: ``1e-08``) 

139 Optimality tolerance for 

140 :ref:`'highs-ipm' <optimize.linprog-highs-ipm>`. 

141 Minimum allowable value is 1e-12. 

142 simplex_dual_edge_weight_strategy : str (default: None) 

143 Strategy for simplex dual edge weights. The default, ``None``, 

144 automatically selects one of the following. 

145 

146 ``'dantzig'`` uses Dantzig's original strategy of choosing the most 

147 negative reduced cost. 

148 

149 ``'devex'`` uses the strategy described in [15]_. 

150 

151 ``steepest`` uses the exact steepest edge strategy as described in 

152 [16]_. 

153 

154 ``'steepest-devex'`` begins with the exact steepest edge strategy 

155 until the computation is too costly or inexact and then switches to 

156 the devex method. 

157 

158 Curently, ``None`` always selects ``'steepest-devex'``, but this 

159 may change as new options become available. 

160 mip_rel_gap : double (default: None) 

161 Termination criterion for MIP solver: solver will terminate when the 

162 gap between the primal objective value and the dual objective bound, 

163 scaled by the primal objective value, is <= mip_rel_gap. 

164 unknown_options : dict 

165 Optional arguments not used by this particular solver. If 

166 ``unknown_options`` is non-empty, a warning is issued listing 

167 all unused options. 

168 

169 Returns 

170 ------- 

171 res : OptimizeResult 

172 A :class:`scipy.optimize.OptimizeResult` consisting of the fields: 

173 

174 x : 1D array 

175 The values of the decision variables that minimizes the 

176 objective function while satisfying the constraints. 

177 fun : float 

178 The optimal value of the objective function ``c @ x``. 

179 slack : 1D array 

180 The (nominally positive) values of the slack, 

181 ``b_ub - A_ub @ x``. 

182 con : 1D array 

183 The (nominally zero) residuals of the equality constraints, 

184 ``b_eq - A_eq @ x``. 

185 success : bool 

186 ``True`` when the algorithm succeeds in finding an optimal 

187 solution. 

188 status : int 

189 An integer representing the exit status of the algorithm. 

190 

191 ``0`` : Optimization terminated successfully. 

192 

193 ``1`` : Iteration or time limit reached. 

194 

195 ``2`` : Problem appears to be infeasible. 

196 

197 ``3`` : Problem appears to be unbounded. 

198 

199 ``4`` : The HiGHS solver ran into a problem. 

200 

201 message : str 

202 A string descriptor of the exit status of the algorithm. 

203 nit : int 

204 The total number of iterations performed. 

205 For the HiGHS simplex method, this includes iterations in all 

206 phases. For the HiGHS interior-point method, this does not include 

207 crossover iterations. 

208 crossover_nit : int 

209 The number of primal/dual pushes performed during the 

210 crossover routine for the HiGHS interior-point method. 

211 This is ``0`` for the HiGHS simplex method. 

212 ineqlin : OptimizeResult 

213 Solution and sensitivity information corresponding to the 

214 inequality constraints, `b_ub`. A dictionary consisting of the 

215 fields: 

216 

217 residual : np.ndnarray 

218 The (nominally positive) values of the slack variables, 

219 ``b_ub - A_ub @ x``. This quantity is also commonly 

220 referred to as "slack". 

221 

222 marginals : np.ndarray 

223 The sensitivity (partial derivative) of the objective 

224 function with respect to the right-hand side of the 

225 inequality constraints, `b_ub`. 

226 

227 eqlin : OptimizeResult 

228 Solution and sensitivity information corresponding to the 

229 equality constraints, `b_eq`. A dictionary consisting of the 

230 fields: 

231 

232 residual : np.ndarray 

233 The (nominally zero) residuals of the equality constraints, 

234 ``b_eq - A_eq @ x``. 

235 

236 marginals : np.ndarray 

237 The sensitivity (partial derivative) of the objective 

238 function with respect to the right-hand side of the 

239 equality constraints, `b_eq`. 

240 

241 lower, upper : OptimizeResult 

242 Solution and sensitivity information corresponding to the 

243 lower and upper bounds on decision variables, `bounds`. 

244 

245 residual : np.ndarray 

246 The (nominally positive) values of the quantity 

247 ``x - lb`` (lower) or ``ub - x`` (upper). 

248 

249 marginals : np.ndarray 

250 The sensitivity (partial derivative) of the objective 

251 function with respect to the lower and upper 

252 `bounds`. 

253 

254 Notes 

255 ----- 

256 

257 Method :ref:`'highs-ds' <optimize.linprog-highs-ds>` is a wrapper 

258 of the C++ high performance dual revised simplex implementation (HSOL) 

259 [13]_, [14]_. Method :ref:`'highs-ipm' <optimize.linprog-highs-ipm>` 

260 is a wrapper of a C++ implementation of an **i**\ nterior-\ **p**\ oint 

261 **m**\ ethod [13]_; it features a crossover routine, so it is as accurate 

262 as a simplex solver. Method :ref:`'highs' <optimize.linprog-highs>` chooses 

263 between the two automatically. For new code involving `linprog`, we 

264 recommend explicitly choosing one of these three method values instead of 

265 :ref:`'interior-point' <optimize.linprog-interior-point>` (default), 

266 :ref:`'revised simplex' <optimize.linprog-revised_simplex>`, and 

267 :ref:`'simplex' <optimize.linprog-simplex>` (legacy). 

268 

269 The result fields `ineqlin`, `eqlin`, `lower`, and `upper` all contain 

270 `marginals`, or partial derivatives of the objective function with respect 

271 to the right-hand side of each constraint. These partial derivatives are 

272 also referred to as "Lagrange multipliers", "dual values", and 

273 "shadow prices". The sign convention of `marginals` is opposite that 

274 of Lagrange multipliers produced by many nonlinear solvers. 

275 

276 References 

277 ---------- 

278 .. [13] Huangfu, Q., Galabova, I., Feldmeier, M., and Hall, J. A. J. 

279 "HiGHS - high performance software for linear optimization." 

280 https://highs.dev/ 

281 .. [14] Huangfu, Q. and Hall, J. A. J. "Parallelizing the dual revised 

282 simplex method." Mathematical Programming Computation, 10 (1), 

283 119-142, 2018. DOI: 10.1007/s12532-017-0130-5 

284 .. [15] Harris, Paula MJ. "Pivot selection methods of the Devex LP code." 

285 Mathematical programming 5.1 (1973): 1-28. 

286 .. [16] Goldfarb, Donald, and John Ker Reid. "A practicable steepest-edge 

287 simplex algorithm." Mathematical Programming 12.1 (1977): 361-371. 

288 """ 

289 pass 

290 

291 

292def _linprog_highs_ds_doc(c, A_ub=None, b_ub=None, A_eq=None, b_eq=None, 

293 bounds=None, method='highs-ds', callback=None, 

294 maxiter=None, disp=False, presolve=True, 

295 time_limit=None, 

296 dual_feasibility_tolerance=None, 

297 primal_feasibility_tolerance=None, 

298 simplex_dual_edge_weight_strategy=None, 

299 **unknown_options): 

300 r""" 

301 Linear programming: minimize a linear objective function subject to linear 

302 equality and inequality constraints using the HiGHS dual simplex solver. 

303 

304 Linear programming solves problems of the following form: 

305 

306 .. math:: 

307 

308 \min_x \ & c^T x \\ 

309 \mbox{such that} \ & A_{ub} x \leq b_{ub},\\ 

310 & A_{eq} x = b_{eq},\\ 

311 & l \leq x \leq u , 

312 

313 where :math:`x` is a vector of decision variables; :math:`c`, 

314 :math:`b_{ub}`, :math:`b_{eq}`, :math:`l`, and :math:`u` are vectors; and 

315 :math:`A_{ub}` and :math:`A_{eq}` are matrices. 

316 

317 Alternatively, that's: 

318 

319 minimize:: 

320 

321 c @ x 

322 

323 such that:: 

324 

325 A_ub @ x <= b_ub 

326 A_eq @ x == b_eq 

327 lb <= x <= ub 

328 

329 Note that by default ``lb = 0`` and ``ub = None`` unless specified with 

330 ``bounds``. 

331 

332 Parameters 

333 ---------- 

334 c : 1-D array 

335 The coefficients of the linear objective function to be minimized. 

336 A_ub : 2-D array, optional 

337 The inequality constraint matrix. Each row of ``A_ub`` specifies the 

338 coefficients of a linear inequality constraint on ``x``. 

339 b_ub : 1-D array, optional 

340 The inequality constraint vector. Each element represents an 

341 upper bound on the corresponding value of ``A_ub @ x``. 

342 A_eq : 2-D array, optional 

343 The equality constraint matrix. Each row of ``A_eq`` specifies the 

344 coefficients of a linear equality constraint on ``x``. 

345 b_eq : 1-D array, optional 

346 The equality constraint vector. Each element of ``A_eq @ x`` must equal 

347 the corresponding element of ``b_eq``. 

348 bounds : sequence, optional 

349 A sequence of ``(min, max)`` pairs for each element in ``x``, defining 

350 the minimum and maximum values of that decision variable. Use ``None`` 

351 to indicate that there is no bound. By default, bounds are 

352 ``(0, None)`` (all decision variables are non-negative). 

353 If a single tuple ``(min, max)`` is provided, then ``min`` and 

354 ``max`` will serve as bounds for all decision variables. 

355 method : str 

356 

357 This is the method-specific documentation for 'highs-ds'. 

358 :ref:`'highs' <optimize.linprog-highs>`, 

359 :ref:`'highs-ipm' <optimize.linprog-highs-ipm>`, 

360 :ref:`'interior-point' <optimize.linprog-interior-point>` (default), 

361 :ref:`'revised simplex' <optimize.linprog-revised_simplex>`, and 

362 :ref:`'simplex' <optimize.linprog-simplex>` (legacy) 

363 are also available. 

364 

365 Options 

366 ------- 

367 maxiter : int 

368 The maximum number of iterations to perform in either phase. 

369 Default is the largest possible value for an ``int`` on the platform. 

370 disp : bool (default: ``False``) 

371 Set to ``True`` if indicators of optimization status are to be 

372 printed to the console during optimization. 

373 presolve : bool (default: ``True``) 

374 Presolve attempts to identify trivial infeasibilities, 

375 identify trivial unboundedness, and simplify the problem before 

376 sending it to the main solver. It is generally recommended 

377 to keep the default setting ``True``; set to ``False`` if 

378 presolve is to be disabled. 

379 time_limit : float 

380 The maximum time in seconds allotted to solve the problem; 

381 default is the largest possible value for a ``double`` on the 

382 platform. 

383 dual_feasibility_tolerance : double (default: 1e-07) 

384 Dual feasibility tolerance for 

385 :ref:`'highs-ds' <optimize.linprog-highs-ds>`. 

386 primal_feasibility_tolerance : double (default: 1e-07) 

387 Primal feasibility tolerance for 

388 :ref:`'highs-ds' <optimize.linprog-highs-ds>`. 

389 simplex_dual_edge_weight_strategy : str (default: None) 

390 Strategy for simplex dual edge weights. The default, ``None``, 

391 automatically selects one of the following. 

392 

393 ``'dantzig'`` uses Dantzig's original strategy of choosing the most 

394 negative reduced cost. 

395 

396 ``'devex'`` uses the strategy described in [15]_. 

397 

398 ``steepest`` uses the exact steepest edge strategy as described in 

399 [16]_. 

400 

401 ``'steepest-devex'`` begins with the exact steepest edge strategy 

402 until the computation is too costly or inexact and then switches to 

403 the devex method. 

404 

405 Curently, ``None`` always selects ``'steepest-devex'``, but this 

406 may change as new options become available. 

407 unknown_options : dict 

408 Optional arguments not used by this particular solver. If 

409 ``unknown_options`` is non-empty, a warning is issued listing 

410 all unused options. 

411 

412 Returns 

413 ------- 

414 res : OptimizeResult 

415 A :class:`scipy.optimize.OptimizeResult` consisting of the fields: 

416 

417 x : 1D array 

418 The values of the decision variables that minimizes the 

419 objective function while satisfying the constraints. 

420 fun : float 

421 The optimal value of the objective function ``c @ x``. 

422 slack : 1D array 

423 The (nominally positive) values of the slack, 

424 ``b_ub - A_ub @ x``. 

425 con : 1D array 

426 The (nominally zero) residuals of the equality constraints, 

427 ``b_eq - A_eq @ x``. 

428 success : bool 

429 ``True`` when the algorithm succeeds in finding an optimal 

430 solution. 

431 status : int 

432 An integer representing the exit status of the algorithm. 

433 

434 ``0`` : Optimization terminated successfully. 

435 

436 ``1`` : Iteration or time limit reached. 

437 

438 ``2`` : Problem appears to be infeasible. 

439 

440 ``3`` : Problem appears to be unbounded. 

441 

442 ``4`` : The HiGHS solver ran into a problem. 

443 

444 message : str 

445 A string descriptor of the exit status of the algorithm. 

446 nit : int 

447 The total number of iterations performed. This includes iterations 

448 in all phases. 

449 crossover_nit : int 

450 This is always ``0`` for the HiGHS simplex method. 

451 For the HiGHS interior-point method, this is the number of 

452 primal/dual pushes performed during the crossover routine. 

453 ineqlin : OptimizeResult 

454 Solution and sensitivity information corresponding to the 

455 inequality constraints, `b_ub`. A dictionary consisting of the 

456 fields: 

457 

458 residual : np.ndnarray 

459 The (nominally positive) values of the slack variables, 

460 ``b_ub - A_ub @ x``. This quantity is also commonly 

461 referred to as "slack". 

462 

463 marginals : np.ndarray 

464 The sensitivity (partial derivative) of the objective 

465 function with respect to the right-hand side of the 

466 inequality constraints, `b_ub`. 

467 

468 eqlin : OptimizeResult 

469 Solution and sensitivity information corresponding to the 

470 equality constraints, `b_eq`. A dictionary consisting of the 

471 fields: 

472 

473 residual : np.ndarray 

474 The (nominally zero) residuals of the equality constraints, 

475 ``b_eq - A_eq @ x``. 

476 

477 marginals : np.ndarray 

478 The sensitivity (partial derivative) of the objective 

479 function with respect to the right-hand side of the 

480 equality constraints, `b_eq`. 

481 

482 lower, upper : OptimizeResult 

483 Solution and sensitivity information corresponding to the 

484 lower and upper bounds on decision variables, `bounds`. 

485 

486 residual : np.ndarray 

487 The (nominally positive) values of the quantity 

488 ``x - lb`` (lower) or ``ub - x`` (upper). 

489 

490 marginals : np.ndarray 

491 The sensitivity (partial derivative) of the objective 

492 function with respect to the lower and upper 

493 `bounds`. 

494 

495 Notes 

496 ----- 

497 

498 Method :ref:`'highs-ds' <optimize.linprog-highs-ds>` is a wrapper 

499 of the C++ high performance dual revised simplex implementation (HSOL) 

500 [13]_, [14]_. Method :ref:`'highs-ipm' <optimize.linprog-highs-ipm>` 

501 is a wrapper of a C++ implementation of an **i**\ nterior-\ **p**\ oint 

502 **m**\ ethod [13]_; it features a crossover routine, so it is as accurate 

503 as a simplex solver. Method :ref:`'highs' <optimize.linprog-highs>` chooses 

504 between the two automatically. For new code involving `linprog`, we 

505 recommend explicitly choosing one of these three method values instead of 

506 :ref:`'interior-point' <optimize.linprog-interior-point>` (default), 

507 :ref:`'revised simplex' <optimize.linprog-revised_simplex>`, and 

508 :ref:`'simplex' <optimize.linprog-simplex>` (legacy). 

509 

510 The result fields `ineqlin`, `eqlin`, `lower`, and `upper` all contain 

511 `marginals`, or partial derivatives of the objective function with respect 

512 to the right-hand side of each constraint. These partial derivatives are 

513 also referred to as "Lagrange multipliers", "dual values", and 

514 "shadow prices". The sign convention of `marginals` is opposite that 

515 of Lagrange multipliers produced by many nonlinear solvers. 

516 

517 References 

518 ---------- 

519 .. [13] Huangfu, Q., Galabova, I., Feldmeier, M., and Hall, J. A. J. 

520 "HiGHS - high performance software for linear optimization." 

521 https://highs.dev/ 

522 .. [14] Huangfu, Q. and Hall, J. A. J. "Parallelizing the dual revised 

523 simplex method." Mathematical Programming Computation, 10 (1), 

524 119-142, 2018. DOI: 10.1007/s12532-017-0130-5 

525 .. [15] Harris, Paula MJ. "Pivot selection methods of the Devex LP code." 

526 Mathematical programming 5.1 (1973): 1-28. 

527 .. [16] Goldfarb, Donald, and John Ker Reid. "A practicable steepest-edge 

528 simplex algorithm." Mathematical Programming 12.1 (1977): 361-371. 

529 """ 

530 pass 

531 

532 

533def _linprog_highs_ipm_doc(c, A_ub=None, b_ub=None, A_eq=None, b_eq=None, 

534 bounds=None, method='highs-ipm', callback=None, 

535 maxiter=None, disp=False, presolve=True, 

536 time_limit=None, 

537 dual_feasibility_tolerance=None, 

538 primal_feasibility_tolerance=None, 

539 ipm_optimality_tolerance=None, 

540 **unknown_options): 

541 r""" 

542 Linear programming: minimize a linear objective function subject to linear 

543 equality and inequality constraints using the HiGHS interior point solver. 

544 

545 Linear programming solves problems of the following form: 

546 

547 .. math:: 

548 

549 \min_x \ & c^T x \\ 

550 \mbox{such that} \ & A_{ub} x \leq b_{ub},\\ 

551 & A_{eq} x = b_{eq},\\ 

552 & l \leq x \leq u , 

553 

554 where :math:`x` is a vector of decision variables; :math:`c`, 

555 :math:`b_{ub}`, :math:`b_{eq}`, :math:`l`, and :math:`u` are vectors; and 

556 :math:`A_{ub}` and :math:`A_{eq}` are matrices. 

557 

558 Alternatively, that's: 

559 

560 minimize:: 

561 

562 c @ x 

563 

564 such that:: 

565 

566 A_ub @ x <= b_ub 

567 A_eq @ x == b_eq 

568 lb <= x <= ub 

569 

570 Note that by default ``lb = 0`` and ``ub = None`` unless specified with 

571 ``bounds``. 

572 

573 Parameters 

574 ---------- 

575 c : 1-D array 

576 The coefficients of the linear objective function to be minimized. 

577 A_ub : 2-D array, optional 

578 The inequality constraint matrix. Each row of ``A_ub`` specifies the 

579 coefficients of a linear inequality constraint on ``x``. 

580 b_ub : 1-D array, optional 

581 The inequality constraint vector. Each element represents an 

582 upper bound on the corresponding value of ``A_ub @ x``. 

583 A_eq : 2-D array, optional 

584 The equality constraint matrix. Each row of ``A_eq`` specifies the 

585 coefficients of a linear equality constraint on ``x``. 

586 b_eq : 1-D array, optional 

587 The equality constraint vector. Each element of ``A_eq @ x`` must equal 

588 the corresponding element of ``b_eq``. 

589 bounds : sequence, optional 

590 A sequence of ``(min, max)`` pairs for each element in ``x``, defining 

591 the minimum and maximum values of that decision variable. Use ``None`` 

592 to indicate that there is no bound. By default, bounds are 

593 ``(0, None)`` (all decision variables are non-negative). 

594 If a single tuple ``(min, max)`` is provided, then ``min`` and 

595 ``max`` will serve as bounds for all decision variables. 

596 method : str 

597 

598 This is the method-specific documentation for 'highs-ipm'. 

599 :ref:`'highs-ipm' <optimize.linprog-highs>`, 

600 :ref:`'highs-ds' <optimize.linprog-highs-ds>`, 

601 :ref:`'interior-point' <optimize.linprog-interior-point>` (default), 

602 :ref:`'revised simplex' <optimize.linprog-revised_simplex>`, and 

603 :ref:`'simplex' <optimize.linprog-simplex>` (legacy) 

604 are also available. 

605 

606 Options 

607 ------- 

608 maxiter : int 

609 The maximum number of iterations to perform in either phase. 

610 For :ref:`'highs-ipm' <optimize.linprog-highs-ipm>`, this does not 

611 include the number of crossover iterations. Default is the largest 

612 possible value for an ``int`` on the platform. 

613 disp : bool (default: ``False``) 

614 Set to ``True`` if indicators of optimization status are to be 

615 printed to the console during optimization. 

616 presolve : bool (default: ``True``) 

617 Presolve attempts to identify trivial infeasibilities, 

618 identify trivial unboundedness, and simplify the problem before 

619 sending it to the main solver. It is generally recommended 

620 to keep the default setting ``True``; set to ``False`` if 

621 presolve is to be disabled. 

622 time_limit : float 

623 The maximum time in seconds allotted to solve the problem; 

624 default is the largest possible value for a ``double`` on the 

625 platform. 

626 dual_feasibility_tolerance : double (default: 1e-07) 

627 The minimum of this and ``primal_feasibility_tolerance`` 

628 is used for the feasibility tolerance of 

629 :ref:`'highs-ipm' <optimize.linprog-highs-ipm>`. 

630 primal_feasibility_tolerance : double (default: 1e-07) 

631 The minimum of this and ``dual_feasibility_tolerance`` 

632 is used for the feasibility tolerance of 

633 :ref:`'highs-ipm' <optimize.linprog-highs-ipm>`. 

634 ipm_optimality_tolerance : double (default: ``1e-08``) 

635 Optimality tolerance for 

636 :ref:`'highs-ipm' <optimize.linprog-highs-ipm>`. 

637 Minimum allowable value is 1e-12. 

638 unknown_options : dict 

639 Optional arguments not used by this particular solver. If 

640 ``unknown_options`` is non-empty, a warning is issued listing 

641 all unused options. 

642 

643 Returns 

644 ------- 

645 res : OptimizeResult 

646 A :class:`scipy.optimize.OptimizeResult` consisting of the fields: 

647 

648 x : 1D array 

649 The values of the decision variables that minimizes the 

650 objective function while satisfying the constraints. 

651 fun : float 

652 The optimal value of the objective function ``c @ x``. 

653 slack : 1D array 

654 The (nominally positive) values of the slack, 

655 ``b_ub - A_ub @ x``. 

656 con : 1D array 

657 The (nominally zero) residuals of the equality constraints, 

658 ``b_eq - A_eq @ x``. 

659 success : bool 

660 ``True`` when the algorithm succeeds in finding an optimal 

661 solution. 

662 status : int 

663 An integer representing the exit status of the algorithm. 

664 

665 ``0`` : Optimization terminated successfully. 

666 

667 ``1`` : Iteration or time limit reached. 

668 

669 ``2`` : Problem appears to be infeasible. 

670 

671 ``3`` : Problem appears to be unbounded. 

672 

673 ``4`` : The HiGHS solver ran into a problem. 

674 

675 message : str 

676 A string descriptor of the exit status of the algorithm. 

677 nit : int 

678 The total number of iterations performed. 

679 For the HiGHS interior-point method, this does not include 

680 crossover iterations. 

681 crossover_nit : int 

682 The number of primal/dual pushes performed during the 

683 crossover routine for the HiGHS interior-point method. 

684 ineqlin : OptimizeResult 

685 Solution and sensitivity information corresponding to the 

686 inequality constraints, `b_ub`. A dictionary consisting of the 

687 fields: 

688 

689 residual : np.ndnarray 

690 The (nominally positive) values of the slack variables, 

691 ``b_ub - A_ub @ x``. This quantity is also commonly 

692 referred to as "slack". 

693 

694 marginals : np.ndarray 

695 The sensitivity (partial derivative) of the objective 

696 function with respect to the right-hand side of the 

697 inequality constraints, `b_ub`. 

698 

699 eqlin : OptimizeResult 

700 Solution and sensitivity information corresponding to the 

701 equality constraints, `b_eq`. A dictionary consisting of the 

702 fields: 

703 

704 residual : np.ndarray 

705 The (nominally zero) residuals of the equality constraints, 

706 ``b_eq - A_eq @ x``. 

707 

708 marginals : np.ndarray 

709 The sensitivity (partial derivative) of the objective 

710 function with respect to the right-hand side of the 

711 equality constraints, `b_eq`. 

712 

713 lower, upper : OptimizeResult 

714 Solution and sensitivity information corresponding to the 

715 lower and upper bounds on decision variables, `bounds`. 

716 

717 residual : np.ndarray 

718 The (nominally positive) values of the quantity 

719 ``x - lb`` (lower) or ``ub - x`` (upper). 

720 

721 marginals : np.ndarray 

722 The sensitivity (partial derivative) of the objective 

723 function with respect to the lower and upper 

724 `bounds`. 

725 

726 Notes 

727 ----- 

728 

729 Method :ref:`'highs-ipm' <optimize.linprog-highs-ipm>` 

730 is a wrapper of a C++ implementation of an **i**\ nterior-\ **p**\ oint 

731 **m**\ ethod [13]_; it features a crossover routine, so it is as accurate 

732 as a simplex solver. 

733 Method :ref:`'highs-ds' <optimize.linprog-highs-ds>` is a wrapper 

734 of the C++ high performance dual revised simplex implementation (HSOL) 

735 [13]_, [14]_. Method :ref:`'highs' <optimize.linprog-highs>` chooses 

736 between the two automatically. For new code involving `linprog`, we 

737 recommend explicitly choosing one of these three method values instead of 

738 :ref:`'interior-point' <optimize.linprog-interior-point>` (default), 

739 :ref:`'revised simplex' <optimize.linprog-revised_simplex>`, and 

740 :ref:`'simplex' <optimize.linprog-simplex>` (legacy). 

741 

742 The result fields `ineqlin`, `eqlin`, `lower`, and `upper` all contain 

743 `marginals`, or partial derivatives of the objective function with respect 

744 to the right-hand side of each constraint. These partial derivatives are 

745 also referred to as "Lagrange multipliers", "dual values", and 

746 "shadow prices". The sign convention of `marginals` is opposite that 

747 of Lagrange multipliers produced by many nonlinear solvers. 

748 

749 References 

750 ---------- 

751 .. [13] Huangfu, Q., Galabova, I., Feldmeier, M., and Hall, J. A. J. 

752 "HiGHS - high performance software for linear optimization." 

753 https://highs.dev/ 

754 .. [14] Huangfu, Q. and Hall, J. A. J. "Parallelizing the dual revised 

755 simplex method." Mathematical Programming Computation, 10 (1), 

756 119-142, 2018. DOI: 10.1007/s12532-017-0130-5 

757 """ 

758 pass 

759 

760 

761def _linprog_ip_doc(c, A_ub=None, b_ub=None, A_eq=None, b_eq=None, 

762 bounds=None, method='interior-point', callback=None, 

763 maxiter=1000, disp=False, presolve=True, 

764 tol=1e-8, autoscale=False, rr=True, 

765 alpha0=.99995, beta=0.1, sparse=False, 

766 lstsq=False, sym_pos=True, cholesky=True, pc=True, 

767 ip=False, permc_spec='MMD_AT_PLUS_A', **unknown_options): 

768 r""" 

769 Linear programming: minimize a linear objective function subject to linear 

770 equality and inequality constraints using the interior-point method of 

771 [4]_. 

772 

773 .. deprecated:: 1.9.0 

774 `method='interior-point'` will be removed in SciPy 1.11.0. 

775 It is replaced by `method='highs'` because the latter is 

776 faster and more robust. 

777 

778 Linear programming solves problems of the following form: 

779 

780 .. math:: 

781 

782 \min_x \ & c^T x \\ 

783 \mbox{such that} \ & A_{ub} x \leq b_{ub},\\ 

784 & A_{eq} x = b_{eq},\\ 

785 & l \leq x \leq u , 

786 

787 where :math:`x` is a vector of decision variables; :math:`c`, 

788 :math:`b_{ub}`, :math:`b_{eq}`, :math:`l`, and :math:`u` are vectors; and 

789 :math:`A_{ub}` and :math:`A_{eq}` are matrices. 

790 

791 Alternatively, that's: 

792 

793 minimize:: 

794 

795 c @ x 

796 

797 such that:: 

798 

799 A_ub @ x <= b_ub 

800 A_eq @ x == b_eq 

801 lb <= x <= ub 

802 

803 Note that by default ``lb = 0`` and ``ub = None`` unless specified with 

804 ``bounds``. 

805 

806 Parameters 

807 ---------- 

808 c : 1-D array 

809 The coefficients of the linear objective function to be minimized. 

810 A_ub : 2-D array, optional 

811 The inequality constraint matrix. Each row of ``A_ub`` specifies the 

812 coefficients of a linear inequality constraint on ``x``. 

813 b_ub : 1-D array, optional 

814 The inequality constraint vector. Each element represents an 

815 upper bound on the corresponding value of ``A_ub @ x``. 

816 A_eq : 2-D array, optional 

817 The equality constraint matrix. Each row of ``A_eq`` specifies the 

818 coefficients of a linear equality constraint on ``x``. 

819 b_eq : 1-D array, optional 

820 The equality constraint vector. Each element of ``A_eq @ x`` must equal 

821 the corresponding element of ``b_eq``. 

822 bounds : sequence, optional 

823 A sequence of ``(min, max)`` pairs for each element in ``x``, defining 

824 the minimum and maximum values of that decision variable. Use ``None`` 

825 to indicate that there is no bound. By default, bounds are 

826 ``(0, None)`` (all decision variables are non-negative). 

827 If a single tuple ``(min, max)`` is provided, then ``min`` and 

828 ``max`` will serve as bounds for all decision variables. 

829 method : str 

830 This is the method-specific documentation for 'interior-point'. 

831 :ref:`'highs' <optimize.linprog-highs>`, 

832 :ref:`'highs-ds' <optimize.linprog-highs-ds>`, 

833 :ref:`'highs-ipm' <optimize.linprog-highs-ipm>`, 

834 :ref:`'revised simplex' <optimize.linprog-revised_simplex>`, and 

835 :ref:`'simplex' <optimize.linprog-simplex>` (legacy) 

836 are also available. 

837 callback : callable, optional 

838 Callback function to be executed once per iteration. 

839 

840 Options 

841 ------- 

842 maxiter : int (default: 1000) 

843 The maximum number of iterations of the algorithm. 

844 disp : bool (default: False) 

845 Set to ``True`` if indicators of optimization status are to be printed 

846 to the console each iteration. 

847 presolve : bool (default: True) 

848 Presolve attempts to identify trivial infeasibilities, 

849 identify trivial unboundedness, and simplify the problem before 

850 sending it to the main solver. It is generally recommended 

851 to keep the default setting ``True``; set to ``False`` if 

852 presolve is to be disabled. 

853 tol : float (default: 1e-8) 

854 Termination tolerance to be used for all termination criteria; 

855 see [4]_ Section 4.5. 

856 autoscale : bool (default: False) 

857 Set to ``True`` to automatically perform equilibration. 

858 Consider using this option if the numerical values in the 

859 constraints are separated by several orders of magnitude. 

860 rr : bool (default: True) 

861 Set to ``False`` to disable automatic redundancy removal. 

862 alpha0 : float (default: 0.99995) 

863 The maximal step size for Mehrota's predictor-corrector search 

864 direction; see :math:`\beta_{3}` of [4]_ Table 8.1. 

865 beta : float (default: 0.1) 

866 The desired reduction of the path parameter :math:`\mu` (see [6]_) 

867 when Mehrota's predictor-corrector is not in use (uncommon). 

868 sparse : bool (default: False) 

869 Set to ``True`` if the problem is to be treated as sparse after 

870 presolve. If either ``A_eq`` or ``A_ub`` is a sparse matrix, 

871 this option will automatically be set ``True``, and the problem 

872 will be treated as sparse even during presolve. If your constraint 

873 matrices contain mostly zeros and the problem is not very small (less 

874 than about 100 constraints or variables), consider setting ``True`` 

875 or providing ``A_eq`` and ``A_ub`` as sparse matrices. 

876 lstsq : bool (default: ``False``) 

877 Set to ``True`` if the problem is expected to be very poorly 

878 conditioned. This should always be left ``False`` unless severe 

879 numerical difficulties are encountered. Leave this at the default 

880 unless you receive a warning message suggesting otherwise. 

881 sym_pos : bool (default: True) 

882 Leave ``True`` if the problem is expected to yield a well conditioned 

883 symmetric positive definite normal equation matrix 

884 (almost always). Leave this at the default unless you receive 

885 a warning message suggesting otherwise. 

886 cholesky : bool (default: True) 

887 Set to ``True`` if the normal equations are to be solved by explicit 

888 Cholesky decomposition followed by explicit forward/backward 

889 substitution. This is typically faster for problems 

890 that are numerically well-behaved. 

891 pc : bool (default: True) 

892 Leave ``True`` if the predictor-corrector method of Mehrota is to be 

893 used. This is almost always (if not always) beneficial. 

894 ip : bool (default: False) 

895 Set to ``True`` if the improved initial point suggestion due to [4]_ 

896 Section 4.3 is desired. Whether this is beneficial or not 

897 depends on the problem. 

898 permc_spec : str (default: 'MMD_AT_PLUS_A') 

899 (Has effect only with ``sparse = True``, ``lstsq = False``, ``sym_pos = 

900 True``, and no SuiteSparse.) 

901 A matrix is factorized in each iteration of the algorithm. 

902 This option specifies how to permute the columns of the matrix for 

903 sparsity preservation. Acceptable values are: 

904 

905 - ``NATURAL``: natural ordering. 

906 - ``MMD_ATA``: minimum degree ordering on the structure of A^T A. 

907 - ``MMD_AT_PLUS_A``: minimum degree ordering on the structure of A^T+A. 

908 - ``COLAMD``: approximate minimum degree column ordering. 

909 

910 This option can impact the convergence of the 

911 interior point algorithm; test different values to determine which 

912 performs best for your problem. For more information, refer to 

913 ``scipy.sparse.linalg.splu``. 

914 unknown_options : dict 

915 Optional arguments not used by this particular solver. If 

916 `unknown_options` is non-empty a warning is issued listing all 

917 unused options. 

918 

919 Returns 

920 ------- 

921 res : OptimizeResult 

922 A :class:`scipy.optimize.OptimizeResult` consisting of the fields: 

923 

924 x : 1-D array 

925 The values of the decision variables that minimizes the 

926 objective function while satisfying the constraints. 

927 fun : float 

928 The optimal value of the objective function ``c @ x``. 

929 slack : 1-D array 

930 The (nominally positive) values of the slack variables, 

931 ``b_ub - A_ub @ x``. 

932 con : 1-D array 

933 The (nominally zero) residuals of the equality constraints, 

934 ``b_eq - A_eq @ x``. 

935 success : bool 

936 ``True`` when the algorithm succeeds in finding an optimal 

937 solution. 

938 status : int 

939 An integer representing the exit status of the algorithm. 

940 

941 ``0`` : Optimization terminated successfully. 

942 

943 ``1`` : Iteration limit reached. 

944 

945 ``2`` : Problem appears to be infeasible. 

946 

947 ``3`` : Problem appears to be unbounded. 

948 

949 ``4`` : Numerical difficulties encountered. 

950 

951 message : str 

952 A string descriptor of the exit status of the algorithm. 

953 nit : int 

954 The total number of iterations performed in all phases. 

955 

956 

957 Notes 

958 ----- 

959 This method implements the algorithm outlined in [4]_ with ideas from [8]_ 

960 and a structure inspired by the simpler methods of [6]_. 

961 

962 The primal-dual path following method begins with initial 'guesses' of 

963 the primal and dual variables of the standard form problem and iteratively 

964 attempts to solve the (nonlinear) Karush-Kuhn-Tucker conditions for the 

965 problem with a gradually reduced logarithmic barrier term added to the 

966 objective. This particular implementation uses a homogeneous self-dual 

967 formulation, which provides certificates of infeasibility or unboundedness 

968 where applicable. 

969 

970 The default initial point for the primal and dual variables is that 

971 defined in [4]_ Section 4.4 Equation 8.22. Optionally (by setting initial 

972 point option ``ip=True``), an alternate (potentially improved) starting 

973 point can be calculated according to the additional recommendations of 

974 [4]_ Section 4.4. 

975 

976 A search direction is calculated using the predictor-corrector method 

977 (single correction) proposed by Mehrota and detailed in [4]_ Section 4.1. 

978 (A potential improvement would be to implement the method of multiple 

979 corrections described in [4]_ Section 4.2.) In practice, this is 

980 accomplished by solving the normal equations, [4]_ Section 5.1 Equations 

981 8.31 and 8.32, derived from the Newton equations [4]_ Section 5 Equations 

982 8.25 (compare to [4]_ Section 4 Equations 8.6-8.8). The advantage of 

983 solving the normal equations rather than 8.25 directly is that the 

984 matrices involved are symmetric positive definite, so Cholesky 

985 decomposition can be used rather than the more expensive LU factorization. 

986 

987 With default options, the solver used to perform the factorization depends 

988 on third-party software availability and the conditioning of the problem. 

989 

990 For dense problems, solvers are tried in the following order: 

991 

992 1. ``scipy.linalg.cho_factor`` 

993 

994 2. ``scipy.linalg.solve`` with option ``sym_pos=True`` 

995 

996 3. ``scipy.linalg.solve`` with option ``sym_pos=False`` 

997 

998 4. ``scipy.linalg.lstsq`` 

999 

1000 For sparse problems: 

1001 

1002 1. ``sksparse.cholmod.cholesky`` (if scikit-sparse and SuiteSparse are 

1003 installed) 

1004 

1005 2. ``scipy.sparse.linalg.factorized`` (if scikit-umfpack and SuiteSparse 

1006 are installed) 

1007 

1008 3. ``scipy.sparse.linalg.splu`` (which uses SuperLU distributed with SciPy) 

1009 

1010 4. ``scipy.sparse.linalg.lsqr`` 

1011 

1012 If the solver fails for any reason, successively more robust (but slower) 

1013 solvers are attempted in the order indicated. Attempting, failing, and 

1014 re-starting factorization can be time consuming, so if the problem is 

1015 numerically challenging, options can be set to bypass solvers that are 

1016 failing. Setting ``cholesky=False`` skips to solver 2, 

1017 ``sym_pos=False`` skips to solver 3, and ``lstsq=True`` skips 

1018 to solver 4 for both sparse and dense problems. 

1019 

1020 Potential improvements for combatting issues associated with dense 

1021 columns in otherwise sparse problems are outlined in [4]_ Section 5.3 and 

1022 [10]_ Section 4.1-4.2; the latter also discusses the alleviation of 

1023 accuracy issues associated with the substitution approach to free 

1024 variables. 

1025 

1026 After calculating the search direction, the maximum possible step size 

1027 that does not activate the non-negativity constraints is calculated, and 

1028 the smaller of this step size and unity is applied (as in [4]_ Section 

1029 4.1.) [4]_ Section 4.3 suggests improvements for choosing the step size. 

1030 

1031 The new point is tested according to the termination conditions of [4]_ 

1032 Section 4.5. The same tolerance, which can be set using the ``tol`` option, 

1033 is used for all checks. (A potential improvement would be to expose 

1034 the different tolerances to be set independently.) If optimality, 

1035 unboundedness, or infeasibility is detected, the solve procedure 

1036 terminates; otherwise it repeats. 

1037 

1038 Whereas the top level ``linprog`` module expects a problem of form: 

1039 

1040 Minimize:: 

1041 

1042 c @ x 

1043 

1044 Subject to:: 

1045 

1046 A_ub @ x <= b_ub 

1047 A_eq @ x == b_eq 

1048 lb <= x <= ub 

1049 

1050 where ``lb = 0`` and ``ub = None`` unless set in ``bounds``. The problem 

1051 is automatically converted to the form: 

1052 

1053 Minimize:: 

1054 

1055 c @ x 

1056 

1057 Subject to:: 

1058 

1059 A @ x == b 

1060 x >= 0 

1061 

1062 for solution. That is, the original problem contains equality, upper-bound 

1063 and variable constraints whereas the method specific solver requires 

1064 equality constraints and variable non-negativity. ``linprog`` converts the 

1065 original problem to standard form by converting the simple bounds to upper 

1066 bound constraints, introducing non-negative slack variables for inequality 

1067 constraints, and expressing unbounded variables as the difference between 

1068 two non-negative variables. The problem is converted back to the original 

1069 form before results are reported. 

1070 

1071 References 

1072 ---------- 

1073 .. [4] Andersen, Erling D., and Knud D. Andersen. "The MOSEK interior point 

1074 optimizer for linear programming: an implementation of the 

1075 homogeneous algorithm." High performance optimization. Springer US, 

1076 2000. 197-232. 

1077 .. [6] Freund, Robert M. "Primal-Dual Interior-Point Methods for Linear 

1078 Programming based on Newton's Method." Unpublished Course Notes, 

1079 March 2004. Available 2/25/2017 at 

1080 https://ocw.mit.edu/courses/sloan-school-of-management/15-084j-nonlinear-programming-spring-2004/lecture-notes/lec14_int_pt_mthd.pdf 

1081 .. [8] Andersen, Erling D., and Knud D. Andersen. "Presolving in linear 

1082 programming." Mathematical Programming 71.2 (1995): 221-245. 

1083 .. [9] Bertsimas, Dimitris, and J. Tsitsiklis. "Introduction to linear 

1084 programming." Athena Scientific 1 (1997): 997. 

1085 .. [10] Andersen, Erling D., et al. Implementation of interior point 

1086 methods for large scale linear programming. HEC/Universite de 

1087 Geneve, 1996. 

1088 """ 

1089 pass 

1090 

1091 

1092def _linprog_rs_doc(c, A_ub=None, b_ub=None, A_eq=None, b_eq=None, 

1093 bounds=None, method='interior-point', callback=None, 

1094 x0=None, maxiter=5000, disp=False, presolve=True, 

1095 tol=1e-12, autoscale=False, rr=True, maxupdate=10, 

1096 mast=False, pivot="mrc", **unknown_options): 

1097 r""" 

1098 Linear programming: minimize a linear objective function subject to linear 

1099 equality and inequality constraints using the revised simplex method. 

1100 

1101 .. deprecated:: 1.9.0 

1102 `method='revised simplex'` will be removed in SciPy 1.11.0. 

1103 It is replaced by `method='highs'` because the latter is 

1104 faster and more robust. 

1105 

1106 Linear programming solves problems of the following form: 

1107 

1108 .. math:: 

1109 

1110 \min_x \ & c^T x \\ 

1111 \mbox{such that} \ & A_{ub} x \leq b_{ub},\\ 

1112 & A_{eq} x = b_{eq},\\ 

1113 & l \leq x \leq u , 

1114 

1115 where :math:`x` is a vector of decision variables; :math:`c`, 

1116 :math:`b_{ub}`, :math:`b_{eq}`, :math:`l`, and :math:`u` are vectors; and 

1117 :math:`A_{ub}` and :math:`A_{eq}` are matrices. 

1118 

1119 Alternatively, that's: 

1120 

1121 minimize:: 

1122 

1123 c @ x 

1124 

1125 such that:: 

1126 

1127 A_ub @ x <= b_ub 

1128 A_eq @ x == b_eq 

1129 lb <= x <= ub 

1130 

1131 Note that by default ``lb = 0`` and ``ub = None`` unless specified with 

1132 ``bounds``. 

1133 

1134 Parameters 

1135 ---------- 

1136 c : 1-D array 

1137 The coefficients of the linear objective function to be minimized. 

1138 A_ub : 2-D array, optional 

1139 The inequality constraint matrix. Each row of ``A_ub`` specifies the 

1140 coefficients of a linear inequality constraint on ``x``. 

1141 b_ub : 1-D array, optional 

1142 The inequality constraint vector. Each element represents an 

1143 upper bound on the corresponding value of ``A_ub @ x``. 

1144 A_eq : 2-D array, optional 

1145 The equality constraint matrix. Each row of ``A_eq`` specifies the 

1146 coefficients of a linear equality constraint on ``x``. 

1147 b_eq : 1-D array, optional 

1148 The equality constraint vector. Each element of ``A_eq @ x`` must equal 

1149 the corresponding element of ``b_eq``. 

1150 bounds : sequence, optional 

1151 A sequence of ``(min, max)`` pairs for each element in ``x``, defining 

1152 the minimum and maximum values of that decision variable. Use ``None`` 

1153 to indicate that there is no bound. By default, bounds are 

1154 ``(0, None)`` (all decision variables are non-negative). 

1155 If a single tuple ``(min, max)`` is provided, then ``min`` and 

1156 ``max`` will serve as bounds for all decision variables. 

1157 method : str 

1158 This is the method-specific documentation for 'revised simplex'. 

1159 :ref:`'highs' <optimize.linprog-highs>`, 

1160 :ref:`'highs-ds' <optimize.linprog-highs-ds>`, 

1161 :ref:`'highs-ipm' <optimize.linprog-highs-ipm>`, 

1162 :ref:`'interior-point' <optimize.linprog-interior-point>` (default), 

1163 and :ref:`'simplex' <optimize.linprog-simplex>` (legacy) 

1164 are also available. 

1165 callback : callable, optional 

1166 Callback function to be executed once per iteration. 

1167 x0 : 1-D array, optional 

1168 Guess values of the decision variables, which will be refined by 

1169 the optimization algorithm. This argument is currently used only by the 

1170 'revised simplex' method, and can only be used if `x0` represents a 

1171 basic feasible solution. 

1172 

1173 Options 

1174 ------- 

1175 maxiter : int (default: 5000) 

1176 The maximum number of iterations to perform in either phase. 

1177 disp : bool (default: False) 

1178 Set to ``True`` if indicators of optimization status are to be printed 

1179 to the console each iteration. 

1180 presolve : bool (default: True) 

1181 Presolve attempts to identify trivial infeasibilities, 

1182 identify trivial unboundedness, and simplify the problem before 

1183 sending it to the main solver. It is generally recommended 

1184 to keep the default setting ``True``; set to ``False`` if 

1185 presolve is to be disabled. 

1186 tol : float (default: 1e-12) 

1187 The tolerance which determines when a solution is "close enough" to 

1188 zero in Phase 1 to be considered a basic feasible solution or close 

1189 enough to positive to serve as an optimal solution. 

1190 autoscale : bool (default: False) 

1191 Set to ``True`` to automatically perform equilibration. 

1192 Consider using this option if the numerical values in the 

1193 constraints are separated by several orders of magnitude. 

1194 rr : bool (default: True) 

1195 Set to ``False`` to disable automatic redundancy removal. 

1196 maxupdate : int (default: 10) 

1197 The maximum number of updates performed on the LU factorization. 

1198 After this many updates is reached, the basis matrix is factorized 

1199 from scratch. 

1200 mast : bool (default: False) 

1201 Minimize Amortized Solve Time. If enabled, the average time to solve 

1202 a linear system using the basis factorization is measured. Typically, 

1203 the average solve time will decrease with each successive solve after 

1204 initial factorization, as factorization takes much more time than the 

1205 solve operation (and updates). Eventually, however, the updated 

1206 factorization becomes sufficiently complex that the average solve time 

1207 begins to increase. When this is detected, the basis is refactorized 

1208 from scratch. Enable this option to maximize speed at the risk of 

1209 nondeterministic behavior. Ignored if ``maxupdate`` is 0. 

1210 pivot : "mrc" or "bland" (default: "mrc") 

1211 Pivot rule: Minimum Reduced Cost ("mrc") or Bland's rule ("bland"). 

1212 Choose Bland's rule if iteration limit is reached and cycling is 

1213 suspected. 

1214 unknown_options : dict 

1215 Optional arguments not used by this particular solver. If 

1216 `unknown_options` is non-empty a warning is issued listing all 

1217 unused options. 

1218 

1219 Returns 

1220 ------- 

1221 res : OptimizeResult 

1222 A :class:`scipy.optimize.OptimizeResult` consisting of the fields: 

1223 

1224 x : 1-D array 

1225 The values of the decision variables that minimizes the 

1226 objective function while satisfying the constraints. 

1227 fun : float 

1228 The optimal value of the objective function ``c @ x``. 

1229 slack : 1-D array 

1230 The (nominally positive) values of the slack variables, 

1231 ``b_ub - A_ub @ x``. 

1232 con : 1-D array 

1233 The (nominally zero) residuals of the equality constraints, 

1234 ``b_eq - A_eq @ x``. 

1235 success : bool 

1236 ``True`` when the algorithm succeeds in finding an optimal 

1237 solution. 

1238 status : int 

1239 An integer representing the exit status of the algorithm. 

1240 

1241 ``0`` : Optimization terminated successfully. 

1242 

1243 ``1`` : Iteration limit reached. 

1244 

1245 ``2`` : Problem appears to be infeasible. 

1246 

1247 ``3`` : Problem appears to be unbounded. 

1248 

1249 ``4`` : Numerical difficulties encountered. 

1250 

1251 ``5`` : Problem has no constraints; turn presolve on. 

1252 

1253 ``6`` : Invalid guess provided. 

1254 

1255 message : str 

1256 A string descriptor of the exit status of the algorithm. 

1257 nit : int 

1258 The total number of iterations performed in all phases. 

1259 

1260 

1261 Notes 

1262 ----- 

1263 Method *revised simplex* uses the revised simplex method as described in 

1264 [9]_, except that a factorization [11]_ of the basis matrix, rather than 

1265 its inverse, is efficiently maintained and used to solve the linear systems 

1266 at each iteration of the algorithm. 

1267 

1268 References 

1269 ---------- 

1270 .. [9] Bertsimas, Dimitris, and J. Tsitsiklis. "Introduction to linear 

1271 programming." Athena Scientific 1 (1997): 997. 

1272 .. [11] Bartels, Richard H. "A stabilization of the simplex method." 

1273 Journal in Numerische Mathematik 16.5 (1971): 414-434. 

1274 """ 

1275 pass 

1276 

1277 

1278def _linprog_simplex_doc(c, A_ub=None, b_ub=None, A_eq=None, b_eq=None, 

1279 bounds=None, method='interior-point', callback=None, 

1280 maxiter=5000, disp=False, presolve=True, 

1281 tol=1e-12, autoscale=False, rr=True, bland=False, 

1282 **unknown_options): 

1283 r""" 

1284 Linear programming: minimize a linear objective function subject to linear 

1285 equality and inequality constraints using the tableau-based simplex method. 

1286 

1287 .. deprecated:: 1.9.0 

1288 `method='simplex'` will be removed in SciPy 1.11.0. 

1289 It is replaced by `method='highs'` because the latter is 

1290 faster and more robust. 

1291 

1292 Linear programming solves problems of the following form: 

1293 

1294 .. math:: 

1295 

1296 \min_x \ & c^T x \\ 

1297 \mbox{such that} \ & A_{ub} x \leq b_{ub},\\ 

1298 & A_{eq} x = b_{eq},\\ 

1299 & l \leq x \leq u , 

1300 

1301 where :math:`x` is a vector of decision variables; :math:`c`, 

1302 :math:`b_{ub}`, :math:`b_{eq}`, :math:`l`, and :math:`u` are vectors; and 

1303 :math:`A_{ub}` and :math:`A_{eq}` are matrices.