415:
2771:
3382:
1959:
2526:
2119:
245:
2537:
1168:
873:
1737:
1020:
2280:
162:
2374:
1970:
689:
410:{\displaystyle {\begin{aligned}{\boldsymbol {Ax}}&={\boldsymbol {b}},\\{\boldsymbol {A}}^{\mathrm {T} }{\boldsymbol {\lambda }}+{\boldsymbol {s}}&={\boldsymbol {c}},\\{\boldsymbol {x}}&\geq {\boldsymbol {0}},\\{\boldsymbol {s}}&\geq {\boldsymbol {0}},\\{\boldsymbol {s}}^{\mathrm {T} }{\boldsymbol {x}}&=0\end{aligned}}}
2766:{\displaystyle {\begin{aligned}{\boldsymbol {x}}&={\begin{bmatrix}0&0&5&5&0\end{bmatrix}}^{\mathrm {T} },\\{\boldsymbol {\lambda }}&={\begin{bmatrix}0&-4/3\end{bmatrix}}^{\mathrm {T} },\\{\boldsymbol {s_{N}}}&={\begin{bmatrix}2/3&11/3&4/3\end{bmatrix}}^{\mathrm {T} }.\end{aligned}}}
1031:
731:
1954:{\displaystyle {\begin{aligned}{\boldsymbol {c}}&={\begin{bmatrix}-2&-3&-4&0&0\end{bmatrix}}^{\mathrm {T} },\\{\boldsymbol {A}}&={\begin{bmatrix}3&2&1&1&0\\2&5&3&0&1\end{bmatrix}},\\{\boldsymbol {b}}&={\begin{bmatrix}10\\15\end{bmatrix}}.\end{aligned}}}
899:
2934:
2951:
is directly updated after each pivot operation, for which purpose there exist several strategies such as the
ForrestâTomlin and BartelsâGolub methods. However, the amount of data representing the updates as well as numerical errors builds up over time and makes periodic refactorization necessary.
2139:
73:
2521:{\displaystyle {\begin{aligned}{\boldsymbol {B}}&={\begin{bmatrix}{\boldsymbol {A}}_{3}&{\boldsymbol {A}}_{4}\end{bmatrix}},\\{\boldsymbol {N}}&={\begin{bmatrix}{\boldsymbol {A}}_{1}&{\boldsymbol {A}}_{2}&{\boldsymbol {A}}_{5}\end{bmatrix}}.\end{aligned}}}
2114:{\displaystyle {\begin{aligned}{\boldsymbol {B}}&={\begin{bmatrix}{\boldsymbol {A}}_{4}&{\boldsymbol {A}}_{5}\end{bmatrix}},\\{\boldsymbol {N}}&={\begin{bmatrix}{\boldsymbol {A}}_{1}&{\boldsymbol {A}}_{2}&{\boldsymbol {A}}_{3}\end{bmatrix}}\end{aligned}}}
50:
The revised simplex method is mathematically equivalent to the standard simplex method but differs in implementation. Instead of maintaining a tableau which explicitly represents the constraints adjusted to a set of basic variables, it maintains a representation of a
577:
1383:
1163:{\displaystyle {\begin{aligned}{\boldsymbol {\lambda }}&=({\boldsymbol {B}}^{\mathrm {T} })^{-1}{\boldsymbol {c_{B}}},\\{\boldsymbol {s_{N}}}&={\boldsymbol {c_{N}}}-{\boldsymbol {N}}^{\mathrm {T} }{\boldsymbol {\lambda }}.\end{aligned}}}
868:{\displaystyle {\begin{aligned}{\boldsymbol {c}}&={\begin{bmatrix}{\boldsymbol {c_{B}}}\\{\boldsymbol {c_{N}}}\end{bmatrix}},\\{\boldsymbol {s}}&={\begin{bmatrix}{\boldsymbol {s_{B}}}\\{\boldsymbol {s_{N}}}\end{bmatrix}}.\end{aligned}}}
1015:{\displaystyle {\begin{aligned}{\boldsymbol {B}}^{\mathrm {T} }{\boldsymbol {\lambda }}&={\boldsymbol {c_{B}}},\\{\boldsymbol {N}}^{\mathrm {T} }{\boldsymbol {\lambda }}+{\boldsymbol {s_{N}}}&={\boldsymbol {c_{N}}},\end{aligned}}}
2853:
1489:
2275:{\displaystyle {\begin{aligned}{\boldsymbol {\lambda }}&={\begin{bmatrix}0&0\end{bmatrix}}^{\mathrm {T} },\\{\boldsymbol {s_{N}}}&={\begin{bmatrix}-2&-3&-4\end{bmatrix}}^{\mathrm {T} }.\end{aligned}}}
157:{\displaystyle {\begin{array}{rl}{\text{minimize}}&{\boldsymbol {c}}^{\mathrm {T} }{\boldsymbol {x}}\\{\text{subject to}}&{\boldsymbol {Ax}}={\boldsymbol {b}},{\boldsymbol {x}}\geq {\boldsymbol {0}}\end{array}}}
684:{\displaystyle {\boldsymbol {x}}={\begin{bmatrix}{\boldsymbol {x_{B}}}\\{\boldsymbol {x_{N}}}\end{bmatrix}}={\begin{bmatrix}{\boldsymbol {B}}^{-1}{\boldsymbol {b}}\\{\boldsymbol {0}}\end{bmatrix}}}
2858:
2542:
2379:
2144:
1975:
1742:
1036:
904:
736:
250:
1241:. Therefore, if the problem is bounded, the revised simplex method must terminate at an optimal vertex after repeated pivot operations because there are only a finite number of vertices.
3279:
1306:
2814:
Because the revised simplex method is mathematically equivalent to the simplex method, it also suffers from degeneracy, where a pivot operation does not result in a decrease in
3882:
3150:
3274:
2929:{\displaystyle {\begin{aligned}{\boldsymbol {Bz}}&={\boldsymbol {y}},\\{\boldsymbol {B}}^{\mathrm {T} }{\boldsymbol {z}}&={\boldsymbol {y}}.\end{aligned}}}
2827:, and a chain of pivot operations causes the basis to cycle. A perturbation or lexicographic strategy can be used to prevent cycling and guarantee termination.
1426:
3288:
3768:
232:
3875:
3143:
3118:
59:
representing the constraints. The matrix-oriented approach allows for greater computational efficiency by enabling sparse matrix operations.
218:
is rank-deficient, either there are redundant constraints, or the problem is infeasible. Both situations can be handled by a presolve step.
3920:
3849:
3311:
2973:
The same theorem also states that the feasible polytope has at least one vertex and that there is at least one vertex which is optimal.
3363:
3224:
3085:
3331:
67:
For the rest of the discussion, it is assumed that a linear programming problem has been converted into the following standard form:
3930:
3868:
3110:
3442:
3136:
3915:
3719:
3381:
3925:
3827:
3447:
3763:
3731:
3993:
3998:
3812:
3437:
3758:
3714:
3316:
3891:
3607:
3336:
2836:
3497:
3962:
3159:
28:
3682:
1225:
236:
3544:
1378:{\displaystyle {\frac {\partial ({\boldsymbol {c}}^{\mathrm {T} }{\boldsymbol {x}})}{\partial x_{q}}}=s_{q},}
3726:
3625:
3341:
3219:
3817:
3802:
3692:
3196:
3163:
52:
3967:
3910:
3706:
3672:
3575:
3517:
3398:
3204:
3184:
3091:
3109:. Springer Series in Operations Research and Financial Engineering (2nd ed.). New York, NY, USA:
3972:
3753:
3580:
3492:
56:
3128:
3822:
3687:
3640:
3630:
3482:
3470:
3283:
3266:
3171:
437:
3944:
3905:
3557:
3526:
3512:
3502:
3293:
44:
3209:
1695:
is reduced to zero while maintaining feasibility. The pivot operation concludes with replacing
3952:
3565:
3243:
3114:
3104:
3645:
3635:
3539:
3416:
3321:
3303:
3256:
3167:
2948:
1634:
can be arbitrarily decreased, and thus the problem is unbounded. Otherwise, select an index
3103:
Nocedal, J.; Wright, S. J. (2006). Mikosch, T. V.; Resnick, S. I.; Robinson, S. M. (eds.).
3095:
239:
for optimality. The KKT conditions of a linear programming problem in the standard form is
3860:
3661:
17:
3956:
3649:
3534:
3421:
3355:
3326:
2809:
1726:
40:
36:
3987:
3807:
3791:
1484:{\displaystyle {\boldsymbol {Bx_{B}}}+{\boldsymbol {A}}_{q}x_{q}={\boldsymbol {b}},}
3745:
3251:
3832:
3214:
184:
has full row rank and that the problem is feasible, i.e., there is at least one
78:
3234:
3940:
3554:
176:. Without loss of generality, it is assumed that the constraint matrix
3864:
3789:
3605:
3468:
3396:
3182:
3132:
3380:
1300:
will be allowed to increase from zero. It can be shown that
510:
of the feasible polytope can be identified by being a basis
1228:, a pivot operation always results in a strict decrease in
466:, respectively. The last condition, which is equivalent to
1188:
at this point, the KKT conditions are satisfied, and thus
542:
is nonsingular. Without loss of generality, assume that
1216:
into the basis at the expense of an existing column in
2991:
2989:
2810:
Simplex method § Degeneracy: stalling and cycling
2700:
2630:
2563:
2460:
2399:
2224:
2165:
2056:
1995:
1923:
1838:
1763:
878:
To satisfy the complementary slackness condition, let
819:
756:
641:
594:
2856:
2540:
2377:
2142:
1973:
1740:
1429:
1309:
1034:
902:
734:
580:
248:
76:
3939:
3898:
3744:
3705:
3671:
3660:
3618:
3553:
3525:
3511:
3481:
3430:
3409:
3354:
3302:
3265:
3242:
3233:
3195:
2928:
2765:
2520:
2274:
2124:initially, which corresponds to a feasible vertex
2113:
1953:
1483:
1377:
1162:
1014:
867:
683:
409:
156:
2131:= [0 0 0 10 15]
3876:
3144:
3067:
3055:
3043:
3031:
3019:
3007:
8:
2847:are present in the revised simplex method:
3883:
3869:
3861:
3786:
3702:
3668:
3615:
3602:
3522:
3478:
3465:
3406:
3393:
3239:
3192:
3179:
3151:
3137:
3129:
3087:A Comparison of Simplex Method Algorithms
2914:
2902:
2895:
2894:
2889:
2876:
2861:
2857:
2855:
2749:
2748:
2732:
2719:
2706:
2695:
2680:
2675:
2661:
2660:
2644:
2625:
2612:
2598:
2597:
2558:
2545:
2541:
2539:
2497:
2492:
2483:
2478:
2469:
2464:
2455:
2443:
2422:
2417:
2408:
2403:
2394:
2382:
2378:
2376:
2258:
2257:
2219:
2204:
2199:
2185:
2184:
2160:
2147:
2143:
2141:
2093:
2088:
2079:
2074:
2065:
2060:
2051:
2039:
2018:
2013:
2004:
1999:
1990:
1978:
1974:
1972:
1918:
1906:
1833:
1821:
1807:
1806:
1758:
1745:
1741:
1739:
1473:
1464:
1454:
1449:
1438:
1430:
1428:
1366:
1350:
1333:
1326:
1325:
1320:
1310:
1308:
1148:
1141:
1140:
1135:
1124:
1119:
1105:
1100:
1086:
1081:
1072:
1061:
1060:
1055:
1039:
1035:
1033:
998:
993:
979:
974:
966:
959:
958:
953:
938:
933:
921:
914:
913:
908:
903:
901:
843:
838:
827:
822:
814:
802:
780:
775:
764:
759:
751:
739:
735:
733:
668:
659:
650:
645:
636:
618:
613:
602:
597:
589:
581:
579:
500:fundamental theorem of linear programming
388:
381:
380:
375:
362:
350:
338:
326:
314:
302:
294:
287:
286:
281:
268:
253:
249:
247:
145:
137:
129:
118:
111:
102:
95:
94:
89:
81:
77:
75:
3385:Optimization computes maxima and minima.
526:chosen from the latter's columns. Since
3892:Complementarity problems and algorithms
2985:
2966:
2915:
2903:
2890:
2877:
2865:
2862:
2681:
2677:
2613:
2546:
2493:
2479:
2465:
2444:
2418:
2404:
2383:
2205:
2201:
2148:
2089:
2075:
2061:
2040:
2014:
2000:
1979:
1907:
1822:
1746:
1474:
1450:
1439:
1435:
1431:
1334:
1321:
1149:
1136:
1125:
1121:
1106:
1102:
1087:
1083:
1056:
1040:
999:
995:
980:
976:
967:
954:
939:
935:
922:
909:
844:
840:
828:
824:
803:
781:
777:
765:
761:
740:
660:
646:
619:
615:
603:
599:
582:
389:
376:
351:
327:
315:
303:
295:
282:
269:
257:
254:
138:
130:
122:
119:
103:
90:
2995:
1208:consisting of introducing a column of
1204:If the KKT conditions are violated, a
3581:Principal pivoting algorithm of Lemke
1504:must be correspondingly decreased by
7:
3916:Linear complementarity problem (LCP)
1677:. This choice effectively increases
1291:, will be moved into the basis, and
3225:Successive parabolic interpolation
2896:
2750:
2662:
2599:
2259:
2186:
1808:
1343:
1327:
1313:
1142:
1062:
960:
915:
498:By what is sometimes known as the
382:
288:
96:
25:
3545:Projective algorithm of Karmarkar
3034:, p. 370, Theorem 13.4.
3022:, p. 363, Theorem 13.2.
2301:, which means a unit increase in
493:complementary slackness condition
3540:Ellipsoid algorithm of Khachiyan
3443:Sequential quadratic programming
3280:BroydenâFletcherâGoldfarbâShanno
1731:Consider a linear program where
1224:is performed. In the absence of
669:
440:associated with the constraints
363:
339:
146:
3498:Reduced gradient (FrankâWolfe)
3046:, p. 369, Eq. 13.24.
1621:will stay nonnegative. Hence,
1338:
1316:
1272:. The corresponding column of
1069:
1051:
1:
3828:Spiral optimization algorithm
3448:Successive linear programming
3010:, p. 358, Eq. 13.4.
1727:Simplex method § Example
1388:i.e., every unit increase in
233:KarushâKuhnâTucker conditions
3566:Simplex algorithm of Dantzig
3438:Augmented Lagrangian methods
2292:as the entering index. Then
231:For linear programming, the
2368:After the pivot operation,
2365:becomes the leaving index.
2336:, respectively. Therefore,
4015:
3911:Quadratic programming (QP)
2807:
1724:
3845:
3798:
3785:
3769:Pushârelabel maximum flow
3614:
3601:
3571:Revised simplex algorithm
3477:
3464:
3405:
3392:
3378:
3191:
3178:
3068:Nocedal & Wright 2006
3056:Nocedal & Wright 2006
3044:Nocedal & Wright 2006
3032:Nocedal & Wright 2006
3020:Nocedal & Wright 2006
3008:Nocedal & Wright 2006
2939:Instead of refactorizing
1397:results in a decrease by
29:mathematical optimization
18:Revised simplex algorithm
3899:Complementarity Problems
3294:Symmetric rank-one (SR1)
3275:BerndtâHallâHallâHausman
2358:is reduced to zero, and
237:necessary and sufficient
3906:Linear programming (LP)
3818:Parallel metaheuristics
3626:Approximation algorithm
3337:Powell's dog leg method
3289:DavidonâFletcherâPowell
3185:Unconstrained nonlinear
222:Algorithmic description
3803:Evolutionary algorithm
3386:
3106:Numerical Optimization
3084:Morgan, S. S. (1997).
2930:
2767:
2522:
2276:
2115:
1955:
1485:
1379:
1164:
1016:
869:
685:
411:
158:
33:revised simplex method
3576:Criss-cross algorithm
3399:Constrained nonlinear
3384:
3205:Golden-section search
3092:University of Florida
3070:, p. 372, §13.4.
3058:, p. 381, §13.5.
2931:
2768:
2523:
2299:= [1 3]
2277:
2116:
1956:
1592:, no matter how much
1486:
1380:
1165:
1017:
870:
686:
412:
227:Optimality conditions
159:
3493:Cutting-plane method
2956:Notes and references
2854:
2831:Basis representation
2538:
2375:
2140:
1971:
1738:
1427:
1307:
1032:
900:
732:
578:
438:Lagrange multipliers
246:
74:
3994:Exchange algorithms
3945:exchange algorithms
3921:Mixed linear (MLCP)
3823:Simulated annealing
3641:Integer programming
3631:Dynamic programming
3471:Convex optimization
3332:LevenbergâMarquardt
2328:being decreased by
1025:which implies that
63:Problem formulation
3999:Linear programming
3503:Subgradient method
3387:
3312:Conjugate gradient
3220:NelderâMead method
2926:
2924:
2763:
2761:
2742:
2654:
2591:
2518:
2516:
2505:
2430:
2272:
2270:
2251:
2178:
2133:. At this moment,
2111:
2109:
2101:
2026:
1951:
1949:
1938:
1893:
1800:
1481:
1375:
1160:
1158:
1012:
1010:
893:. It follows that
865:
863:
852:
789:
681:
675:
627:
407:
405:
154:
152:
45:linear programming
3981:
3980:
3858:
3857:
3841:
3840:
3781:
3780:
3777:
3776:
3740:
3739:
3701:
3700:
3597:
3596:
3593:
3592:
3589:
3588:
3460:
3459:
3456:
3455:
3376:
3375:
3372:
3371:
3350:
3349:
3120:978-0-387-30303-1
3098:on 7 August 2011.
2531:Correspondingly,
2349:, at which point
1721:Numerical example
1357:
725:accordingly into
114:
84:
16:(Redirected from
4006:
3885:
3878:
3871:
3862:
3787:
3703:
3669:
3646:Branch and bound
3636:Greedy algorithm
3616:
3603:
3523:
3479:
3466:
3407:
3394:
3342:Truncated Newton
3257:Wolfe conditions
3240:
3193:
3180:
3153:
3146:
3139:
3130:
3124:
3099:
3094:. Archived from
3071:
3065:
3059:
3053:
3047:
3041:
3035:
3029:
3023:
3017:
3011:
3005:
2999:
2993:
2974:
2971:
2949:LU factorization
2946:
2935:
2933:
2932:
2927:
2925:
2918:
2906:
2901:
2900:
2899:
2893:
2880:
2868:
2846:
2826:
2799:Practical issues
2795:is now optimal.
2794:
2786:
2772:
2770:
2769:
2764:
2762:
2755:
2754:
2753:
2747:
2746:
2736:
2723:
2710:
2686:
2685:
2684:
2667:
2666:
2665:
2659:
2658:
2648:
2616:
2604:
2603:
2602:
2596:
2595:
2549:
2527:
2525:
2524:
2519:
2517:
2510:
2509:
2502:
2501:
2496:
2488:
2487:
2482:
2474:
2473:
2468:
2447:
2435:
2434:
2427:
2426:
2421:
2413:
2412:
2407:
2386:
2364:
2357:
2348:
2345:is increased to
2344:
2335:
2331:
2327:
2318:
2309:
2300:
2291:
2281:
2279:
2278:
2273:
2271:
2264:
2263:
2262:
2256:
2255:
2210:
2209:
2208:
2191:
2190:
2189:
2183:
2182:
2151:
2132:
2120:
2118:
2117:
2112:
2110:
2106:
2105:
2098:
2097:
2092:
2084:
2083:
2078:
2070:
2069:
2064:
2043:
2031:
2030:
2023:
2022:
2017:
2009:
2008:
2003:
1982:
1960:
1958:
1957:
1952:
1950:
1943:
1942:
1910:
1898:
1897:
1825:
1813:
1812:
1811:
1805:
1804:
1749:
1716:
1705:
1694:
1686:from zero until
1685:
1672:
1633:
1620:
1600:
1591:
1579:
1557:
1533:
1503:
1490:
1488:
1487:
1482:
1477:
1469:
1468:
1459:
1458:
1453:
1444:
1443:
1442:
1419:
1406:
1396:
1384:
1382:
1381:
1376:
1371:
1370:
1358:
1356:
1355:
1354:
1341:
1337:
1332:
1331:
1330:
1324:
1311:
1299:
1290:
1279:
1267:
1257:
1244:Select an index
1240:
1223:
1215:
1195:
1187:
1169:
1167:
1166:
1161:
1159:
1152:
1147:
1146:
1145:
1139:
1130:
1129:
1128:
1111:
1110:
1109:
1092:
1091:
1090:
1080:
1079:
1067:
1066:
1065:
1059:
1043:
1021:
1019:
1018:
1013:
1011:
1004:
1003:
1002:
985:
984:
983:
970:
965:
964:
963:
957:
944:
943:
942:
925:
920:
919:
918:
912:
892:
874:
872:
871:
866:
864:
857:
856:
849:
848:
847:
833:
832:
831:
806:
794:
793:
786:
785:
784:
770:
769:
768:
743:
724:
716:
708:
690:
688:
687:
682:
680:
679:
672:
663:
658:
657:
649:
632:
631:
624:
623:
622:
608:
607:
606:
585:
570:
562:
541:
533:
525:
517:
509:
491:, is called the
490:
479:
465:
453:
435:
427:
416:
414:
413:
408:
406:
392:
387:
386:
385:
379:
366:
354:
342:
330:
318:
306:
298:
293:
292:
291:
285:
272:
260:
217:
209:
195:
183:
175:
163:
161:
160:
155:
153:
149:
141:
133:
125:
115:
112:
106:
101:
100:
99:
93:
85:
82:
35:is a variant of
21:
4014:
4013:
4009:
4008:
4007:
4005:
4004:
4003:
3984:
3983:
3982:
3977:
3963:Revised simplex
3935:
3931:Nonlinear (NCP)
3894:
3889:
3859:
3854:
3837:
3794:
3773:
3736:
3697:
3674:
3663:
3656:
3610:
3585:
3549:
3516:
3507:
3484:
3473:
3452:
3426:
3422:Penalty methods
3417:Barrier methods
3401:
3388:
3368:
3364:Newton's method
3346:
3298:
3261:
3229:
3210:Powell's method
3187:
3174:
3157:
3127:
3121:
3102:
3083:
3079:
3074:
3066:
3062:
3054:
3050:
3042:
3038:
3030:
3026:
3018:
3014:
3006:
3002:
2994:
2987:
2983:
2978:
2977:
2972:
2968:
2963:
2958:
2940:
2923:
2922:
2907:
2888:
2885:
2884:
2869:
2852:
2851:
2840:
2833:
2815:
2812:
2806:
2801:
2788:
2787:indicates that
2783:
2777:
2760:
2759:
2741:
2740:
2727:
2714:
2696:
2694:
2687:
2676:
2672:
2671:
2653:
2652:
2636:
2626:
2624:
2617:
2609:
2608:
2590:
2589:
2584:
2579:
2574:
2569:
2559:
2557:
2550:
2536:
2535:
2515:
2514:
2504:
2503:
2491:
2489:
2477:
2475:
2463:
2456:
2448:
2440:
2439:
2429:
2428:
2416:
2414:
2402:
2395:
2387:
2373:
2372:
2359:
2356:
2350:
2346:
2343:
2337:
2333:
2329:
2326:
2320:
2317:
2311:
2308:
2302:
2293:
2286:
2269:
2268:
2250:
2249:
2241:
2233:
2220:
2218:
2211:
2200:
2196:
2195:
2177:
2176:
2171:
2161:
2159:
2152:
2138:
2137:
2125:
2108:
2107:
2100:
2099:
2087:
2085:
2073:
2071:
2059:
2052:
2044:
2036:
2035:
2025:
2024:
2012:
2010:
1998:
1991:
1983:
1969:
1968:
1948:
1947:
1937:
1936:
1930:
1929:
1919:
1911:
1903:
1902:
1892:
1891:
1886:
1881:
1876:
1871:
1865:
1864:
1859:
1854:
1849:
1844:
1834:
1826:
1818:
1817:
1799:
1798:
1793:
1788:
1780:
1772:
1759:
1757:
1750:
1736:
1735:
1729:
1723:
1714:
1707:
1703:
1696:
1692:
1687:
1683:
1678:
1669:
1662:
1655:
1649:
1635:
1622:
1617:
1608:
1602:
1598:
1593:
1581:
1577:
1559:
1550:
1541:
1535:
1531:
1527:
1512:
1505:
1500:
1494:
1460:
1448:
1434:
1425:
1424:
1408:
1404:
1398:
1394:
1389:
1362:
1346:
1342:
1319:
1312:
1305:
1304:
1297:
1292:
1288:
1281:
1273:
1264:
1259:
1245:
1229:
1217:
1209:
1206:pivot operation
1202:
1200:Pivot operation
1189:
1180:
1174:
1157:
1156:
1134:
1120:
1112:
1101:
1097:
1096:
1082:
1068:
1054:
1044:
1030:
1029:
1009:
1008:
994:
986:
975:
952:
949:
948:
934:
926:
907:
898:
897:
885:
879:
862:
861:
851:
850:
839:
835:
834:
823:
815:
807:
799:
798:
788:
787:
776:
772:
771:
760:
752:
744:
730:
729:
718:
710:
701:
695:
674:
673:
665:
664:
644:
637:
626:
625:
614:
610:
609:
598:
590:
576:
575:
564:
543:
535:
534:has full rank,
527:
519:
511:
503:
481:
476:
472:
467:
455:
441:
429:
421:
404:
403:
393:
374:
371:
370:
355:
347:
346:
331:
323:
322:
307:
280:
277:
276:
261:
244:
243:
229:
224:
211:
197:
185:
177:
168:
151:
150:
116:
108:
107:
88:
86:
72:
71:
65:
23:
22:
15:
12:
11:
5:
4012:
4010:
4002:
4001:
3996:
3986:
3985:
3979:
3978:
3976:
3975:
3970:
3965:
3960:
3949:
3947:
3937:
3936:
3934:
3933:
3928:
3923:
3918:
3913:
3908:
3902:
3900:
3896:
3895:
3890:
3888:
3887:
3880:
3873:
3865:
3856:
3855:
3853:
3852:
3846:
3843:
3842:
3839:
3838:
3836:
3835:
3830:
3825:
3820:
3815:
3810:
3805:
3799:
3796:
3795:
3792:Metaheuristics
3790:
3783:
3782:
3779:
3778:
3775:
3774:
3772:
3771:
3766:
3764:FordâFulkerson
3761:
3756:
3750:
3748:
3742:
3741:
3738:
3737:
3735:
3734:
3732:FloydâWarshall
3729:
3724:
3723:
3722:
3711:
3709:
3699:
3698:
3696:
3695:
3690:
3685:
3679:
3677:
3666:
3658:
3657:
3655:
3654:
3653:
3652:
3638:
3633:
3628:
3622:
3620:
3612:
3611:
3606:
3599:
3598:
3595:
3594:
3591:
3590:
3587:
3586:
3584:
3583:
3578:
3573:
3568:
3562:
3560:
3551:
3550:
3548:
3547:
3542:
3537:
3535:Affine scaling
3531:
3529:
3527:Interior point
3520:
3509:
3508:
3506:
3505:
3500:
3495:
3489:
3487:
3475:
3474:
3469:
3462:
3461:
3458:
3457:
3454:
3453:
3451:
3450:
3445:
3440:
3434:
3432:
3431:Differentiable
3428:
3427:
3425:
3424:
3419:
3413:
3411:
3403:
3402:
3397:
3390:
3389:
3379:
3377:
3374:
3373:
3370:
3369:
3367:
3366:
3360:
3358:
3352:
3351:
3348:
3347:
3345:
3344:
3339:
3334:
3329:
3324:
3319:
3314:
3308:
3306:
3300:
3299:
3297:
3296:
3291:
3286:
3277:
3271:
3269:
3263:
3262:
3260:
3259:
3254:
3248:
3246:
3237:
3231:
3230:
3228:
3227:
3222:
3217:
3212:
3207:
3201:
3199:
3189:
3188:
3183:
3176:
3175:
3158:
3156:
3155:
3148:
3141:
3133:
3126:
3125:
3119:
3100:
3090:(MSc thesis).
3080:
3078:
3075:
3073:
3072:
3060:
3048:
3036:
3024:
3012:
3000:
2984:
2982:
2979:
2976:
2975:
2965:
2964:
2962:
2959:
2957:
2954:
2937:
2936:
2921:
2917:
2913:
2910:
2908:
2905:
2898:
2892:
2887:
2886:
2883:
2879:
2875:
2872:
2870:
2867:
2864:
2860:
2859:
2837:linear systems
2832:
2829:
2805:
2802:
2800:
2797:
2781:
2774:
2773:
2758:
2752:
2745:
2739:
2735:
2731:
2728:
2726:
2722:
2718:
2715:
2713:
2709:
2705:
2702:
2701:
2699:
2693:
2690:
2688:
2683:
2679:
2674:
2673:
2670:
2664:
2657:
2651:
2647:
2643:
2640:
2637:
2635:
2632:
2631:
2629:
2623:
2620:
2618:
2615:
2611:
2610:
2607:
2601:
2594:
2588:
2585:
2583:
2580:
2578:
2575:
2573:
2570:
2568:
2565:
2564:
2562:
2556:
2553:
2551:
2548:
2544:
2543:
2529:
2528:
2513:
2508:
2500:
2495:
2490:
2486:
2481:
2476:
2472:
2467:
2462:
2461:
2459:
2454:
2451:
2449:
2446:
2442:
2441:
2438:
2433:
2425:
2420:
2415:
2411:
2406:
2401:
2400:
2398:
2393:
2390:
2388:
2385:
2381:
2380:
2354:
2341:
2324:
2315:
2306:
2283:
2282:
2267:
2261:
2254:
2248:
2245:
2242:
2240:
2237:
2234:
2232:
2229:
2226:
2225:
2223:
2217:
2214:
2212:
2207:
2203:
2198:
2197:
2194:
2188:
2181:
2175:
2172:
2170:
2167:
2166:
2164:
2158:
2155:
2153:
2150:
2146:
2145:
2122:
2121:
2104:
2096:
2091:
2086:
2082:
2077:
2072:
2068:
2063:
2058:
2057:
2055:
2050:
2047:
2045:
2042:
2038:
2037:
2034:
2029:
2021:
2016:
2011:
2007:
2002:
1997:
1996:
1994:
1989:
1986:
1984:
1981:
1977:
1976:
1962:
1961:
1946:
1941:
1935:
1932:
1931:
1928:
1925:
1924:
1922:
1917:
1914:
1912:
1909:
1905:
1904:
1901:
1896:
1890:
1887:
1885:
1882:
1880:
1877:
1875:
1872:
1870:
1867:
1866:
1863:
1860:
1858:
1855:
1853:
1850:
1848:
1845:
1843:
1840:
1839:
1837:
1832:
1829:
1827:
1824:
1820:
1819:
1816:
1810:
1803:
1797:
1794:
1792:
1789:
1787:
1784:
1781:
1779:
1776:
1773:
1771:
1768:
1765:
1764:
1762:
1756:
1753:
1751:
1748:
1744:
1743:
1722:
1719:
1717:in the basis.
1712:
1701:
1690:
1681:
1667:
1660:
1653:
1640:
1615:
1606:
1601:is increased,
1596:
1575:
1548:
1539:
1529:
1525:
1510:
1498:
1492:
1491:
1480:
1476:
1472:
1467:
1463:
1457:
1452:
1447:
1441:
1437:
1433:
1402:
1392:
1386:
1385:
1374:
1369:
1365:
1361:
1353:
1349:
1345:
1340:
1336:
1329:
1323:
1318:
1315:
1295:
1286:
1270:entering index
1262:
1201:
1198:
1178:
1171:
1170:
1155:
1151:
1144:
1138:
1133:
1127:
1123:
1118:
1115:
1113:
1108:
1104:
1099:
1098:
1095:
1089:
1085:
1078:
1075:
1071:
1064:
1058:
1053:
1050:
1047:
1045:
1042:
1038:
1037:
1023:
1022:
1007:
1001:
997:
992:
989:
987:
982:
978:
973:
969:
962:
956:
951:
950:
947:
941:
937:
932:
929:
927:
924:
917:
911:
906:
905:
883:
876:
875:
860:
855:
846:
842:
837:
836:
830:
826:
821:
820:
818:
813:
810:
808:
805:
801:
800:
797:
792:
783:
779:
774:
773:
767:
763:
758:
757:
755:
750:
747:
745:
742:
738:
737:
699:
692:
691:
678:
671:
667:
666:
662:
656:
653:
648:
643:
642:
640:
635:
630:
621:
617:
612:
611:
605:
601:
596:
595:
593:
588:
584:
474:
470:
418:
417:
402:
399:
396:
394:
391:
384:
378:
373:
372:
369:
365:
361:
358:
356:
353:
349:
348:
345:
341:
337:
334:
332:
329:
325:
324:
321:
317:
313:
310:
308:
305:
301:
297:
290:
284:
279:
278:
275:
271:
267:
264:
262:
259:
256:
252:
251:
228:
225:
223:
220:
165:
164:
148:
144:
140:
136:
132:
128:
124:
121:
117:
110:
109:
105:
98:
92:
87:
80:
79:
64:
61:
41:simplex method
37:George Dantzig
24:
14:
13:
10:
9:
6:
4:
3:
2:
4011:
4000:
3997:
3995:
3992:
3991:
3989:
3974:
3971:
3969:
3966:
3964:
3961:
3958:
3954:
3951:
3950:
3948:
3946:
3942:
3938:
3932:
3929:
3927:
3924:
3922:
3919:
3917:
3914:
3912:
3909:
3907:
3904:
3903:
3901:
3897:
3893:
3886:
3881:
3879:
3874:
3872:
3867:
3866:
3863:
3851:
3848:
3847:
3844:
3834:
3831:
3829:
3826:
3824:
3821:
3819:
3816:
3814:
3811:
3809:
3808:Hill climbing
3806:
3804:
3801:
3800:
3797:
3793:
3788:
3784:
3770:
3767:
3765:
3762:
3760:
3757:
3755:
3752:
3751:
3749:
3747:
3746:Network flows
3743:
3733:
3730:
3728:
3725:
3721:
3718:
3717:
3716:
3713:
3712:
3710:
3708:
3707:Shortest path
3704:
3694:
3691:
3689:
3686:
3684:
3681:
3680:
3678:
3676:
3675:spanning tree
3670:
3667:
3665:
3659:
3651:
3647:
3644:
3643:
3642:
3639:
3637:
3634:
3632:
3629:
3627:
3624:
3623:
3621:
3617:
3613:
3609:
3608:Combinatorial
3604:
3600:
3582:
3579:
3577:
3574:
3572:
3569:
3567:
3564:
3563:
3561:
3559:
3556:
3552:
3546:
3543:
3541:
3538:
3536:
3533:
3532:
3530:
3528:
3524:
3521:
3519:
3514:
3510:
3504:
3501:
3499:
3496:
3494:
3491:
3490:
3488:
3486:
3480:
3476:
3472:
3467:
3463:
3449:
3446:
3444:
3441:
3439:
3436:
3435:
3433:
3429:
3423:
3420:
3418:
3415:
3414:
3412:
3408:
3404:
3400:
3395:
3391:
3383:
3365:
3362:
3361:
3359:
3357:
3353:
3343:
3340:
3338:
3335:
3333:
3330:
3328:
3325:
3323:
3320:
3318:
3315:
3313:
3310:
3309:
3307:
3305:
3304:Other methods
3301:
3295:
3292:
3290:
3287:
3285:
3281:
3278:
3276:
3273:
3272:
3270:
3268:
3264:
3258:
3255:
3253:
3250:
3249:
3247:
3245:
3241:
3238:
3236:
3232:
3226:
3223:
3221:
3218:
3216:
3213:
3211:
3208:
3206:
3203:
3202:
3200:
3198:
3194:
3190:
3186:
3181:
3177:
3173:
3169:
3165:
3161:
3154:
3149:
3147:
3142:
3140:
3135:
3134:
3131:
3122:
3116:
3112:
3108:
3107:
3101:
3097:
3093:
3089:
3088:
3082:
3081:
3076:
3069:
3064:
3061:
3057:
3052:
3049:
3045:
3040:
3037:
3033:
3028:
3025:
3021:
3016:
3013:
3009:
3004:
3001:
2997:
2992:
2990:
2986:
2980:
2970:
2967:
2960:
2955:
2953:
2950:
2947:, usually an
2945:
2944:
2919:
2911:
2909:
2881:
2873:
2871:
2850:
2849:
2848:
2845:
2844:
2838:
2835:Two types of
2830:
2828:
2825:
2824:
2820:
2819:
2811:
2803:
2798:
2796:
2793:
2792:
2785:
2784:
2756:
2743:
2737:
2733:
2729:
2724:
2720:
2716:
2711:
2707:
2703:
2697:
2691:
2689:
2668:
2655:
2649:
2645:
2641:
2638:
2633:
2627:
2621:
2619:
2605:
2592:
2586:
2581:
2576:
2571:
2566:
2560:
2554:
2552:
2534:
2533:
2532:
2511:
2506:
2498:
2484:
2470:
2457:
2452:
2450:
2436:
2431:
2423:
2409:
2396:
2391:
2389:
2371:
2370:
2369:
2366:
2362:
2353:
2340:
2323:
2314:
2305:
2298:
2297:
2289:
2265:
2252:
2246:
2243:
2238:
2235:
2230:
2227:
2221:
2215:
2213:
2192:
2179:
2173:
2168:
2162:
2156:
2154:
2136:
2135:
2134:
2130:
2129:
2102:
2094:
2080:
2066:
2053:
2048:
2046:
2032:
2027:
2019:
2005:
1992:
1987:
1985:
1967:
1966:
1965:
1944:
1939:
1933:
1926:
1920:
1915:
1913:
1899:
1894:
1888:
1883:
1878:
1873:
1868:
1861:
1856:
1851:
1846:
1841:
1835:
1830:
1828:
1814:
1801:
1795:
1790:
1785:
1782:
1777:
1774:
1769:
1766:
1760:
1754:
1752:
1734:
1733:
1732:
1728:
1720:
1718:
1715:
1711:
1704:
1700:
1693:
1684:
1676:
1675:leaving index
1670:
1663:
1656:
1648:
1644:
1638:
1632:
1631:
1627:
1626:
1619:
1618:
1610:
1609:
1599:
1590:
1586:
1585:
1578:
1574:
1570:
1569:
1564:
1563:
1556:
1552:
1551:
1543:
1542:
1532:
1524:
1520:
1519:
1514:
1513:
1502:
1501:
1478:
1470:
1465:
1461:
1455:
1445:
1423:
1422:
1421:
1418:
1417:
1413:
1412:
1405:
1395:
1372:
1367:
1363:
1359:
1351:
1347:
1303:
1302:
1301:
1298:
1289:
1285:
1278:
1277:
1271:
1265:
1256:
1252:
1248:
1242:
1239:
1238:
1234:
1233:
1227:
1222:
1221:
1214:
1213:
1207:
1199:
1197:
1194:
1193:
1186:
1182:
1181:
1153:
1131:
1116:
1114:
1093:
1076:
1073:
1048:
1046:
1028:
1027:
1026:
1005:
990:
988:
971:
945:
930:
928:
896:
895:
894:
891:
887:
886:
858:
853:
816:
811:
809:
795:
790:
753:
748:
746:
728:
727:
726:
723:
722:
715:
714:
707:
703:
702:
676:
654:
651:
638:
633:
628:
591:
586:
574:
573:
572:
569:
568:
560:
559:
554:
553:
548:
547:
540:
539:
532:
531:
524:
523:
516:
515:
508:
507:
501:
496:
494:
489:
485:
477:
464:
460:
459:
452:
451:
446:
445:
439:
434:
433:
426:
425:
400:
397:
395:
367:
359:
357:
343:
335:
333:
319:
311:
309:
299:
273:
265:
263:
242:
241:
240:
238:
234:
226:
221:
219:
216:
215:
208:
207:
202:
201:
194:
190:
189:
182:
181:
173:
172:
142:
134:
126:
70:
69:
68:
62:
60:
58:
54:
48:
46:
42:
38:
34:
30:
19:
3813:Local search
3759:EdmondsâKarp
3715:BellmanâFord
3570:
3485:minimization
3317:GaussâNewton
3267:QuasiâNewton
3252:Trust region
3160:Optimization
3105:
3096:the original
3086:
3077:Bibliography
3063:
3051:
3039:
3027:
3015:
3003:
2969:
2942:
2941:
2938:
2842:
2841:
2834:
2822:
2821:
2817:
2816:
2813:
2790:
2789:
2779:
2778:
2775:
2530:
2367:
2360:
2351:
2338:
2321:
2312:
2303:
2295:
2294:
2287:
2284:
2127:
2126:
2123:
1963:
1730:
1709:
1708:
1698:
1697:
1688:
1679:
1674:
1665:
1658:
1651:
1646:
1642:
1636:
1629:
1628:
1624:
1623:
1613:
1612:
1604:
1603:
1594:
1588:
1583:
1582:
1572:
1571:
1567:
1566:
1561:
1560:
1554:
1546:
1545:
1537:
1536:
1522:
1521:
1517:
1516:
1508:
1507:
1496:
1495:
1493:
1415:
1414:
1410:
1409:
1400:
1390:
1387:
1293:
1283:
1282:
1275:
1274:
1269:
1260:
1254:
1250:
1246:
1243:
1236:
1235:
1231:
1230:
1219:
1218:
1211:
1210:
1205:
1203:
1196:is optimal.
1191:
1190:
1184:
1176:
1175:
1172:
1024:
889:
881:
880:
877:
720:
719:
712:
711:
709:. Partition
705:
697:
696:
693:
571:is given by
566:
565:
557:
556:
551:
550:
545:
544:
537:
536:
529:
528:
521:
520:
513:
512:
505:
504:
502:, a vertex
499:
497:
492:
487:
483:
468:
462:
457:
456:
449:
448:
443:
442:
431:
430:
423:
422:
419:
230:
213:
212:
205:
204:
199:
198:
192:
187:
186:
179:
178:
170:
169:
166:
66:
49:
32:
26:
3968:Criss-cross
3926:Mixed (MCP)
3833:Tabu search
3244:Convergence
3215:Line search
2996:Morgan 1997
2776:A positive
2310:results in
1534:subject to
3988:Categories
3664:algorithms
3172:heuristics
3164:Algorithms
2981:References
2839:involving
2808:See also:
2804:Degeneracy
1725:See also:
1258:such that
1226:degeneracy
196:such that
113:subject to
3619:Paradigms
3518:quadratic
3235:Gradients
3197:Functions
2639:−
2614:λ
2244:−
2236:−
2228:−
2149:λ
1783:−
1775:−
1767:−
1344:∂
1314:∂
1150:λ
1132:−
1074:−
1041:λ
968:λ
923:λ
652:−
360:≥
336:≥
296:λ
235:are both
143:≥
3850:Software
3727:Dijkstra
3558:exchange
3356:Hessians
3322:Gradient
3111:Springer
1639:= argmin
1420:. Since
480:for all
436:are the
83:minimize
3957:Dantzig
3953:Simplex
3693:Kruskal
3683:BorĆŻvka
3673:Minimum
3410:General
3168:methods
2285:Choose
1673:as the
1671:> 0}
1268:as the
563:. Then
555:
549:= [
482:1 <
55:of the
3555:Basis-
3513:Linear
3483:Convex
3327:Mirror
3284:L-BFGS
3170:, and
3117:
1558:. Let
1266:< 0
694:where
420:where
167:where
57:matrix
31:, the
3973:Lemke
3941:Basis
3754:Dinic
3662:Graph
2998:, §2.
2961:Notes
1706:with
1580:. If
1249:<
561:]
486:<
210:. If
53:basis
3720:SPFA
3688:Prim
3282:and
3115:ISBN
2332:and
2319:and
1964:Let
717:and
454:and
428:and
43:for
3650:cut
3515:and
2363:= 5
2290:= 3
1611:â Î
1544:â Î
1407:in
1173:If
518:of
478:= 0
174:â â
39:'s
27:In
3990::
3166:,
3162::
3113:.
2988:^
2717:11
1934:15
1927:10
1664:|
1641:1â€
1587:â€
1565:=
1553:â„
1515:=
1280:,
1253:â€
1183:â„
888:=
704:â„
495:.
461:â„
447:=
444:Ax
203:=
200:Ax
191:â„
47:.
3959:)
3955:(
3943:-
3884:e
3877:t
3870:v
3648:/
3152:e
3145:t
3138:v
3123:.
2943:B
2920:.
2916:y
2912:=
2904:z
2897:T
2891:B
2882:,
2878:y
2874:=
2866:z
2863:B
2843:B
2823:x
2818:c
2791:x
2782:N
2780:s
2757:.
2751:T
2744:]
2738:3
2734:/
2730:4
2725:3
2721:/
2712:3
2708:/
2704:2
2698:[
2692:=
2682:N
2678:s
2669:,
2663:T
2656:]
2650:3
2646:/
2642:4
2634:0
2628:[
2622:=
2606:,
2600:T
2593:]
2587:0
2582:5
2577:5
2572:0
2567:0
2561:[
2555:=
2547:x
2512:.
2507:]
2499:5
2494:A
2485:2
2480:A
2471:1
2466:A
2458:[
2453:=
2445:N
2437:,
2432:]
2424:4
2419:A
2410:3
2405:A
2397:[
2392:=
2384:B
2361:p
2355:5
2352:x
2347:5
2342:3
2339:x
2334:3
2330:1
2325:5
2322:x
2316:4
2313:x
2307:3
2304:x
2296:d
2288:q
2266:.
2260:T
2253:]
2247:4
2239:3
2231:2
2222:[
2216:=
2206:N
2202:s
2193:,
2187:T
2180:]
2174:0
2169:0
2163:[
2157:=
2128:x
2103:]
2095:3
2090:A
2081:2
2076:A
2067:1
2062:A
2054:[
2049:=
2041:N
2033:,
2028:]
2020:5
2015:A
2006:4
2001:A
1993:[
1988:=
1980:B
1945:.
1940:]
1921:[
1916:=
1908:b
1900:,
1895:]
1889:1
1884:0
1879:3
1874:5
1869:2
1862:0
1857:1
1852:1
1847:2
1842:3
1836:[
1831:=
1823:A
1815:,
1809:T
1802:]
1796:0
1791:0
1786:4
1778:3
1770:2
1761:[
1755:=
1747:c
1713:q
1710:A
1702:p
1699:A
1691:p
1689:x
1682:q
1680:x
1668:i
1666:d
1661:i
1659:d
1657:/
1654:i
1652:x
1650:{
1647:m
1645:â€
1643:i
1637:p
1630:x
1625:c
1616:B
1614:x
1607:B
1605:x
1597:q
1595:x
1589:0
1584:d
1576:q
1573:A
1568:B
1562:d
1555:0
1549:B
1547:x
1540:B
1538:x
1530:q
1528:x
1526:q
1523:A
1518:B
1511:B
1509:x
1506:Î
1499:B
1497:x
1479:,
1475:b
1471:=
1466:q
1462:x
1456:q
1451:A
1446:+
1440:B
1436:x
1432:B
1416:x
1411:c
1403:q
1401:s
1399:â
1393:q
1391:x
1373:,
1368:q
1364:s
1360:=
1352:q
1348:x
1339:)
1335:x
1328:T
1322:c
1317:(
1296:q
1294:x
1287:q
1284:A
1276:A
1263:q
1261:s
1255:n
1251:q
1247:m
1237:x
1232:c
1220:B
1212:N
1192:x
1185:0
1179:N
1177:s
1154:.
1143:T
1137:N
1126:N
1122:c
1117:=
1107:N
1103:s
1094:,
1088:B
1084:c
1077:1
1070:)
1063:T
1057:B
1052:(
1049:=
1006:,
1000:N
996:c
991:=
981:N
977:s
972:+
961:T
955:N
946:,
940:B
936:c
931:=
916:T
910:B
890:0
884:B
882:s
859:.
854:]
845:N
841:s
829:B
825:s
817:[
812:=
804:s
796:,
791:]
782:N
778:c
766:B
762:c
754:[
749:=
741:c
721:s
713:c
706:0
700:B
698:x
677:]
670:0
661:b
655:1
647:B
639:[
634:=
629:]
620:N
616:x
604:B
600:x
592:[
587:=
583:x
567:x
558:N
552:B
546:A
538:B
530:A
522:A
514:B
506:x
488:n
484:i
475:i
473:x
471:i
469:s
463:0
458:x
450:b
432:s
424:λ
401:0
398:=
390:x
383:T
377:s
368:,
364:0
352:s
344:,
340:0
328:x
320:,
316:c
312:=
304:s
300:+
289:T
283:A
274:,
270:b
266:=
258:x
255:A
214:A
206:b
193:0
188:x
180:A
171:A
147:0
139:x
135:,
131:b
127:=
123:x
120:A
104:x
97:T
91:c
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.