2476:
20:
915:
197:) and ways to overcome numerical instabilities. Nowadays, all commercial MILP solvers use Gomory cuts in one way or another. Gomory cuts are very efficiently generated from a simplex tableau, whereas many other types of cuts are either expensive or even NP-hard to separate. Among other general cuts for MILP, most notably
1617:
1993:
184:
in the 1950s as a method for solving integer programming and mixed-integer programming problems. However, most experts, including Gomory himself, considered them to be impractical due to numerical instability, as well as ineffective because many rounds of cuts were needed to make progress towards the
321:
338:
be integers and solving the associated relaxed linear programming problem to obtain a basic feasible solution. Geometrically, this solution will be a vertex of the convex polytope consisting of all feasible points. If this vertex is not an integer point then the method finds a hyperplane with the
128:
of the given integer program. The theory of Linear
Programming dictates that under mild assumptions (if the linear program has an optimal solution, and if the feasible region does not contain a line), one can always find an extreme point or a corner point that is optimal. The obtained
670:
339:
vertex on one side and all feasible integer points on the other. This is then added as an additional linear constraint to exclude the vertex found, creating a modified linear program. The new program is then solved and the process is repeated until an integer solution is found.
1392:
1777:
1414:
1789:
219:
1231:
910:{\displaystyle x_{i}+\sum _{j}\lfloor {\bar {a}}_{i,j}\rfloor x_{j}-\lfloor {\bar {b}}_{i}\rfloor ={\bar {b}}_{i}-\lfloor {\bar {b}}_{i}\rfloor -\sum _{j}({\bar {a}}_{i,j}-\lfloor {\bar {a}}_{i,j}\rfloor )x_{j}.}
449:
1126:
1239:
149:. A cut can be added to the relaxed linear program. Then, the current non-integer solution is no longer feasible to the relaxation. This process is repeated until an optimal integer solution is found.
1630:
224:
1779:
is negative for any integer point in the feasible region, and strictly positive for the basic feasible (non integer) solution of the relaxed linear program. Introducing a new slack variable x
1020:
1062:
80:
1612:{\displaystyle {\bar {b}}_{i}-\lfloor {\bar {b}}_{i}\rfloor -\sum _{j}({\bar {a}}_{i,j}-\lfloor {\bar {a}}_{i,j}\rfloor )x_{j}={\bar {b}}_{i}-\lfloor {\bar {b}}_{i}\rfloor >0.}
516:
1988:{\displaystyle x_{k}+\sum _{j}(\lfloor {\bar {a}}_{i,j}\rfloor -{\bar {a}}_{i,j})x_{j}=\lfloor {\bar {b}}_{i}\rfloor -{\bar {b}}_{i},\,x_{k}\geq 0,\,x_{k}{\mbox{ an integer}}.}
627:
585:
160:
can be evaluated efficiently but usual gradient methods for differentiable optimization can not be used. This situation is most typical for the concave maximization of
549:
972:
945:
662:
326:
where A is a matrix and b , c is a vector. The vector x is unknown and is to be found in order to maximize the objective while respecting the linear constraints.
168:
to a structured optimization problem in which formulations with an exponential number of variables are obtained. Generating these variables on demand by means of
152:
Cutting-plane methods for general convex continuous optimization and variants are known under various names: Kelley's method, Kelley–Cheney–Goldstein method, and
2373:
629:
with a bar to denote the last tableau produced by the simplex method. These coefficients are different from the coefficients in the matrix A and the vector b.
316:{\displaystyle {\begin{aligned}{\text{Maximize }}&c^{T}x\\{\text{Subject to }}&Ax\leq b,\\&x\geq 0,\,x_{i}{\text{ all integers}}.\end{aligned}}}
664:
which is not an integer. Rewrite the above equation so that the integer parts are added on the left side and the fractional parts are on the right side:
1131:
198:
2244:
82:. In the context of the Traveling salesman problem on three nodes, this (rather weak) inequality states that every tour must have at least two edges.
2368:
2964:
357:
1397:
must hold for any integer point in the feasible region. Furthermore, non-basic variables are equal to 0s in any basic solution and if
1387:{\displaystyle {\bar {b}}_{i}-\lfloor {\bar {b}}_{i}\rfloor -\sum _{j}({\bar {a}}_{i,j}-\lfloor {\bar {a}}_{i,j}\rfloor )x_{j}\leq 0}
1067:
2862:
2382:
1772:{\displaystyle {\bar {b}}_{i}-\lfloor {\bar {b}}_{i}\rfloor -\sum _{j}({\bar {a}}_{i,j}-\lfloor {\bar {a}}_{i,j}\rfloor )x_{j}}
210:
2237:
1627:
So the inequality above excludes the basic feasible solution and thus is a cut with the desired properties. More precisely,
2943:
2405:
2457:
2318:
977:
2425:
2177:
1025:
469:
s are the nonbasic variables (i.e. the basic solution which is an optimal solution to the relaxed linear program is
2536:
2230:
110:
2475:
2044:
165:
156:. They are popularly used for non-differentiable convex minimization, where a convex objective function and its
2813:
2091:
Gilmore, Paul C; Gomory, Ralph E (1963). "A linear programming approach to the cutting stock problem-Part II".
2011:
of a nonlinear (convex) program by a finite set of closed half spaces and to solve a sequence of approximating
2921:
2541:
133:
is tested for being an integer solution. If it is not, there is guaranteed to exist a linear inequality that
125:
26:
2857:
2825:
472:
2906:
2531:
2852:
2808:
2701:
2430:
2410:
2064:
Gilmore, Paul C; Gomory, Ralph E (1961). "A linear programming approach to the cutting stock problem".
130:
90:
2620:
590:
2591:
2253:
2024:
169:
2776:
2222:
554:
2638:
2820:
2719:
2435:
2119:
2911:
2896:
2786:
2664:
2313:
2290:
2257:
2194:
2182:
186:
920:
For any integer point in the feasible region, the left side is an integer since all the terms
2800:
2766:
2669:
2611:
2492:
2298:
2278:
2190:
2004:
521:
2219:
Chapter 9 Integer
Programming (full text). Bradley, Hax, and Magnanti (Addison-Wesley, 1977)
2847:
2674:
1233:
is negative. Therefore the common value must be less than or equal to 0. So the inequality
950:
923:
640:
161:
8:
2916:
2781:
2734:
2724:
2576:
2564:
2377:
2360:
2265:
114:
2651:
2606:
2596:
2387:
2303:
2160:
2143:
2659:
2337:
2173:
2039:
2739:
2729:
2633:
2510:
2415:
2397:
2350:
2261:
2213:
2155:
2100:
2073:
2034:
190:
2202:
2142:
Marchand, Hugues; Martin, Alexander; Weismantel, Robert; Wolsey, Laurence (2002).
1226:{\displaystyle -\sum _{j}({\bar {a}}_{i,j}-\lfloor {\bar {a}}_{i,j}\rfloor )x_{j}}
2755:
2008:
181:
124:
Cutting plane methods for MILP work by solving a non-integer linear program, the
118:
2743:
2628:
2515:
2449:
2420:
2029:
2012:
1064:
are integers. The right side of this equation is strictly less than 1: indeed,
348:
194:
2958:
2901:
2885:
1783:
for this inequality, a new constraint is added to the linear program, namely
153:
113:(MILP) problems, as well as to solve general, not necessarily differentiable
2839:
2345:
172:
is identical to performing a cutting plane on the respective dual problem.
98:
2104:
2926:
2308:
2077:
157:
138:
87:
97:
is any of a variety of optimization methods that iteratively refine a
2252:
117:
problems. The use of cutting planes to solve MILP was introduced by
189:
and co-workers showed them to be very effective in combination with
19:
2328:
444:{\displaystyle x_{i}+\sum _{j}{\bar {a}}_{i,j}x_{j}={\bar {b}}_{i}}
351:
to solve a linear program produces a set of equations of the form
16:
Optimization technique for solving (mixed) integer linear programs
2648:
106:
2185:(2008). Valid Inequalities for Mixed Integer Linear Programs.
334:
The method proceeds by first dropping the requirement that the x
164:
functions. Another common situation is the application of the
2141:
101:
or objective function by means of linear inequalities, termed
1121:{\displaystyle {\bar {b}}_{i}-\lfloor {\bar {b}}_{i}\rfloor }
342:
141:
of the true feasible set. Finding such an inequality is the
2144:"Cutting planes in integer and mixed integer programming"
23:
The intersection of the unit cube with the cutting plane
1976:
185:
solution. Things turned around when in the mid-1990s
1792:
1633:
1417:
1242:
1134:
1070:
1028:
980:
953:
926:
673:
643:
593:
557:
524:
475:
360:
222:
209:
Let an integer programming problem be formulated (in
29:
2765:
2197:(2007). Revival of the Gomory Cuts in the 1990s.
632:
1987:
1771:
1611:
1386:
1225:
1120:
1056:
1014:
966:
939:
909:
656:
621:
579:
543:
510:
443:
315:
74:
2007:. The underlying principle is to approximate the
2956:
2118:Boyd, S.; Vandenberghe, L. (18 September 2003).
2117:
1015:{\displaystyle \lfloor {\bar {a}}_{i,j}\rfloor }
1057:{\displaystyle \lfloor {\bar {b}}_{i}\rfloor }
2238:
2090:
2063:
2003:Cutting plane methods are also applicable in
105:. Such procedures are commonly used to find
2799:
2170:Nonlinear Programming: Analysis and Methods.
1916:
1894:
1847:
1819:
1753:
1725:
1678:
1656:
1600:
1578:
1537:
1509:
1462:
1440:
1362:
1334:
1287:
1265:
1207:
1179:
1115:
1093:
1051:
1029:
1009:
981:
888:
860:
813:
791:
763:
741:
725:
697:
2277:
2245:
2231:
343:Step 1: solving the relaxed linear program
2491:
2159:
1964:
1944:
1404:is not an integer for the basic solution
290:
2479:Optimization computes maxima and minima.
2120:"Localization and Cutting-plane Methods"
18:
2563:
75:{\displaystyle x_{1}+x_{2}+x_{3}\geq 2}
2957:
1998:
2883:
2699:
2675:Principal pivoting algorithm of Lemke
2562:
2490:
2276:
2226:
2201:, Vol. 149 (2007), pp. 63–66.
511:{\displaystyle x_{i}={\bar {b}}_{i}}
2965:Optimization algorithms and methods
13:
2884:
2474:
2319:Successive parabolic interpolation
14:
2976:
2700:
2639:Projective algorithm of Karmarkar
2214:"Integer Programming" Section 9.8
2207:
2634:Ellipsoid algorithm of Khachiyan
2537:Sequential quadratic programming
2374:Broyden–Fletcher–Goldfarb–Shanno
2217:Applied Mathematical Programming
633:Step 2: Find a linear constraint
622:{\displaystyle {\bar {a}}_{i,j}}
180:Cutting planes were proposed by
111:mixed integer linear programming
2187:Mathematical Programming Ser. B
329:
204:
2592:Reduced gradient (Frank–Wolfe)
2111:
2084:
2057:
1929:
1904:
1878:
1860:
1829:
1816:
1756:
1735:
1704:
1694:
1666:
1641:
1588:
1563:
1540:
1519:
1488:
1478:
1450:
1425:
1365:
1344:
1313:
1303:
1275:
1250:
1210:
1189:
1158:
1148:
1128:is strictly less than 1 while
1103:
1078:
1039:
991:
891:
870:
839:
829:
801:
776:
751:
707:
637:Consider now a basic variable
601:
580:{\displaystyle {\bar {b}}_{i}}
565:
496:
429:
391:
145:, and such an inequality is a
1:
2922:Spiral optimization algorithm
2542:Successive linear programming
2199:Annals of Operations Research
2161:10.1016/s0166-218x(01)00348-1
2050:
1622:
2660:Simplex algorithm of Dantzig
2532:Augmented Lagrangian methods
2148:Discrete Applied Mathematics
461:is a basic variable and the
7:
2045:Dantzig–Wolfe decomposition
2018:
166:Dantzig–Wolfe decomposition
10:
2981:
175:
2939:
2892:
2879:
2863:Push–relabel maximum flow
2838:
2754:
2712:
2708:
2695:
2665:Revised simplex algorithm
2647:
2619:
2605:
2575:
2571:
2558:
2524:
2503:
2499:
2486:
2472:
2448:
2396:
2359:
2336:
2327:
2289:
2285:
2272:
2168:Avriel, Mordecai (2003).
551:). We write coefficients
170:delayed column generation
2388:Symmetric rank-one (SR1)
2369:Berndt–Hall–Hall–Hausman
2912:Parallel metaheuristics
2720:Approximation algorithm
2431:Powell's dog leg method
2383:Davidon–Fletcher–Powell
2279:Unconstrained nonlinear
544:{\displaystyle x_{j}=0}
201:dominates Gomory cuts.
2897:Evolutionary algorithm
2480:
2123:(course lecture notes)
2025:Benders' decomposition
1989:
1773:
1613:
1388:
1227:
1122:
1058:
1016:
968:
941:
911:
658:
623:
581:
545:
512:
445:
317:
83:
76:
2670:Criss-cross algorithm
2493:Constrained nonlinear
2478:
2299:Golden-section search
2105:10.1287/opre.11.6.863
2005:nonlinear programming
1990:
1774:
1614:
1389:
1228:
1123:
1059:
1017:
969:
967:{\displaystyle x_{j}}
942:
940:{\displaystyle x_{i}}
912:
659:
657:{\displaystyle x_{i}}
624:
582:
546:
513:
446:
318:
137:the optimum from the
77:
22:
2587:Cutting-plane method
2189:, (2008) 112:3–44.
2172:Dover Publications.
2078:10.1287/opre.9.6.849
1790:
1631:
1415:
1240:
1132:
1068:
1026:
978:
951:
924:
671:
641:
591:
555:
522:
473:
358:
220:
95:cutting-plane method
27:
2917:Simulated annealing
2735:Integer programming
2725:Dynamic programming
2565:Convex optimization
2426:Levenberg–Marquardt
2093:Operations Research
2066:Operations Research
1999:Convex optimization
115:convex optimization
2597:Subgradient method
2481:
2406:Conjugate gradient
2314:Nelder–Mead method
2195:Cornuéjols, Gérard
2183:Cornuéjols, Gérard
1985:
1980:
1815:
1769:
1693:
1609:
1477:
1384:
1302:
1223:
1147:
1118:
1054:
1012:
964:
937:
907:
828:
696:
654:
619:
577:
541:
508:
441:
383:
313:
311:
303: all integers
143:separation problem
84:
72:
2952:
2951:
2935:
2934:
2875:
2874:
2871:
2870:
2834:
2833:
2795:
2794:
2691:
2690:
2687:
2686:
2683:
2682:
2554:
2553:
2550:
2549:
2470:
2469:
2466:
2465:
2444:
2443:
2040:Column generation
1979:
1932:
1907:
1863:
1832:
1806:
1738:
1707:
1684:
1669:
1644:
1591:
1566:
1522:
1491:
1468:
1453:
1428:
1347:
1316:
1293:
1278:
1253:
1192:
1161:
1138:
1106:
1081:
1042:
994:
873:
842:
819:
804:
779:
754:
710:
687:
604:
568:
499:
432:
394:
374:
304:
254:
230:
187:Gérard Cornuéjols
126:linear relaxation
2972:
2881:
2880:
2797:
2796:
2763:
2762:
2740:Branch and bound
2730:Greedy algorithm
2710:
2709:
2697:
2696:
2617:
2616:
2573:
2572:
2560:
2559:
2501:
2500:
2488:
2487:
2436:Truncated Newton
2351:Wolfe conditions
2334:
2333:
2287:
2286:
2274:
2273:
2247:
2240:
2233:
2224:
2223:
2165:
2163:
2154:(1–3): 387–446.
2134:
2133:
2131:
2129:
2124:
2115:
2109:
2108:
2088:
2082:
2081:
2061:
2035:Branch and bound
1994:
1992:
1991:
1986:
1981:
1978: an integer
1977:
1974:
1973:
1954:
1953:
1940:
1939:
1934:
1933:
1925:
1915:
1914:
1909:
1908:
1900:
1890:
1889:
1877:
1876:
1865:
1864:
1856:
1846:
1845:
1834:
1833:
1825:
1814:
1802:
1801:
1778:
1776:
1775:
1770:
1768:
1767:
1752:
1751:
1740:
1739:
1731:
1721:
1720:
1709:
1708:
1700:
1692:
1677:
1676:
1671:
1670:
1662:
1652:
1651:
1646:
1645:
1637:
1618:
1616:
1615:
1610:
1599:
1598:
1593:
1592:
1584:
1574:
1573:
1568:
1567:
1559:
1552:
1551:
1536:
1535:
1524:
1523:
1515:
1505:
1504:
1493:
1492:
1484:
1476:
1461:
1460:
1455:
1454:
1446:
1436:
1435:
1430:
1429:
1421:
1393:
1391:
1390:
1385:
1377:
1376:
1361:
1360:
1349:
1348:
1340:
1330:
1329:
1318:
1317:
1309:
1301:
1286:
1285:
1280:
1279:
1271:
1261:
1260:
1255:
1254:
1246:
1232:
1230:
1229:
1224:
1222:
1221:
1206:
1205:
1194:
1193:
1185:
1175:
1174:
1163:
1162:
1154:
1146:
1127:
1125:
1124:
1119:
1114:
1113:
1108:
1107:
1099:
1089:
1088:
1083:
1082:
1074:
1063:
1061:
1060:
1055:
1050:
1049:
1044:
1043:
1035:
1021:
1019:
1018:
1013:
1008:
1007:
996:
995:
987:
973:
971:
970:
965:
963:
962:
946:
944:
943:
938:
936:
935:
916:
914:
913:
908:
903:
902:
887:
886:
875:
874:
866:
856:
855:
844:
843:
835:
827:
812:
811:
806:
805:
797:
787:
786:
781:
780:
772:
762:
761:
756:
755:
747:
737:
736:
724:
723:
712:
711:
703:
695:
683:
682:
663:
661:
660:
655:
653:
652:
628:
626:
625:
620:
618:
617:
606:
605:
597:
586:
584:
583:
578:
576:
575:
570:
569:
561:
550:
548:
547:
542:
534:
533:
517:
515:
514:
509:
507:
506:
501:
500:
492:
485:
484:
450:
448:
447:
442:
440:
439:
434:
433:
425:
418:
417:
408:
407:
396:
395:
387:
382:
370:
369:
322:
320:
319:
314:
312:
305:
302:
300:
299:
276:
255:
253:Subject to
252:
243:
242:
231:
228:
199:lift-and-project
191:branch-and-bound
81:
79:
78:
73:
65:
64:
52:
51:
39:
38:
2980:
2979:
2975:
2974:
2973:
2971:
2970:
2969:
2955:
2954:
2953:
2948:
2931:
2888:
2867:
2830:
2791:
2768:
2757:
2750:
2704:
2679:
2643:
2610:
2601:
2578:
2567:
2546:
2520:
2516:Penalty methods
2511:Barrier methods
2495:
2482:
2462:
2458:Newton's method
2440:
2392:
2355:
2323:
2304:Powell's method
2281:
2268:
2251:
2210:
2138:
2137:
2127:
2125:
2122:
2116:
2112:
2089:
2085:
2062:
2058:
2053:
2021:
2013:linear programs
2009:feasible region
2001:
1975:
1969:
1965:
1949:
1945:
1935:
1924:
1923:
1922:
1910:
1899:
1898:
1897:
1885:
1881:
1866:
1855:
1854:
1853:
1835:
1824:
1823:
1822:
1810:
1797:
1793:
1791:
1788:
1787:
1782:
1763:
1759:
1741:
1730:
1729:
1728:
1710:
1699:
1698:
1697:
1688:
1672:
1661:
1660:
1659:
1647:
1636:
1635:
1634:
1632:
1629:
1628:
1625:
1594:
1583:
1582:
1581:
1569:
1558:
1557:
1556:
1547:
1543:
1525:
1514:
1513:
1512:
1494:
1483:
1482:
1481:
1472:
1456:
1445:
1444:
1443:
1431:
1420:
1419:
1418:
1416:
1413:
1412:
1402:
1372:
1368:
1350:
1339:
1338:
1337:
1319:
1308:
1307:
1306:
1297:
1281:
1270:
1269:
1268:
1256:
1245:
1244:
1243:
1241:
1238:
1237:
1217:
1213:
1195:
1184:
1183:
1182:
1164:
1153:
1152:
1151:
1142:
1133:
1130:
1129:
1109:
1098:
1097:
1096:
1084:
1073:
1072:
1071:
1069:
1066:
1065:
1045:
1034:
1033:
1032:
1027:
1024:
1023:
997:
986:
985:
984:
979:
976:
975:
958:
954:
952:
949:
948:
931:
927:
925:
922:
921:
898:
894:
876:
865:
864:
863:
845:
834:
833:
832:
823:
807:
796:
795:
794:
782:
771:
770:
769:
757:
746:
745:
744:
732:
728:
713:
702:
701:
700:
691:
678:
674:
672:
669:
668:
648:
644:
642:
639:
638:
635:
607:
596:
595:
594:
592:
589:
588:
571:
560:
559:
558:
556:
553:
552:
529:
525:
523:
520:
519:
502:
491:
490:
489:
480:
476:
474:
471:
470:
466:
459:
435:
424:
423:
422:
413:
409:
397:
386:
385:
384:
378:
365:
361:
359:
356:
355:
345:
337:
332:
310:
309:
301:
295:
291:
274:
273:
256:
251:
248:
247:
238:
234:
232:
227:
223:
221:
218:
217:
207:
178:
162:Lagrangian dual
119:Ralph E. Gomory
60:
56:
47:
43:
34:
30:
28:
25:
24:
17:
12:
11:
5:
2978:
2968:
2967:
2950:
2949:
2947:
2946:
2940:
2937:
2936:
2933:
2932:
2930:
2929:
2924:
2919:
2914:
2909:
2904:
2899:
2893:
2890:
2889:
2886:Metaheuristics
2877:
2876:
2873:
2872:
2869:
2868:
2866:
2865:
2860:
2858:Ford–Fulkerson
2855:
2850:
2844:
2842:
2836:
2835:
2832:
2831:
2829:
2828:
2826:Floyd–Warshall
2823:
2818:
2817:
2816:
2805:
2803:
2793:
2792:
2790:
2789:
2784:
2779:
2773:
2771:
2760:
2752:
2751:
2749:
2748:
2747:
2746:
2732:
2727:
2722:
2716:
2714:
2706:
2705:
2693:
2692:
2689:
2688:
2685:
2684:
2681:
2680:
2678:
2677:
2672:
2667:
2662:
2656:
2654:
2645:
2644:
2642:
2641:
2636:
2631:
2629:Affine scaling
2625:
2623:
2621:Interior point
2614:
2603:
2602:
2600:
2599:
2594:
2589:
2583:
2581:
2569:
2568:
2556:
2555:
2552:
2551:
2548:
2547:
2545:
2544:
2539:
2534:
2528:
2526:
2525:Differentiable
2522:
2521:
2519:
2518:
2513:
2507:
2505:
2497:
2496:
2484:
2483:
2473:
2471:
2468:
2467:
2464:
2463:
2461:
2460:
2454:
2452:
2446:
2445:
2442:
2441:
2439:
2438:
2433:
2428:
2423:
2418:
2413:
2408:
2402:
2400:
2394:
2393:
2391:
2390:
2385:
2380:
2371:
2365:
2363:
2357:
2356:
2354:
2353:
2348:
2342:
2340:
2331:
2325:
2324:
2322:
2321:
2316:
2311:
2306:
2301:
2295:
2293:
2283:
2282:
2270:
2269:
2250:
2249:
2242:
2235:
2227:
2221:
2220:
2209:
2208:External links
2206:
2205:
2204:
2192:
2180:
2166:
2136:
2135:
2110:
2099:(6): 863–888.
2083:
2072:(6): 849–859.
2055:
2054:
2052:
2049:
2048:
2047:
2042:
2037:
2032:
2030:Branch and cut
2027:
2020:
2017:
2000:
1997:
1996:
1995:
1984:
1972:
1968:
1963:
1960:
1957:
1952:
1948:
1943:
1938:
1931:
1928:
1921:
1918:
1913:
1906:
1903:
1896:
1893:
1888:
1884:
1880:
1875:
1872:
1869:
1862:
1859:
1852:
1849:
1844:
1841:
1838:
1831:
1828:
1821:
1818:
1813:
1809:
1805:
1800:
1796:
1780:
1766:
1762:
1758:
1755:
1750:
1747:
1744:
1737:
1734:
1727:
1724:
1719:
1716:
1713:
1706:
1703:
1696:
1691:
1687:
1683:
1680:
1675:
1668:
1665:
1658:
1655:
1650:
1643:
1640:
1624:
1621:
1620:
1619:
1608:
1605:
1602:
1597:
1590:
1587:
1580:
1577:
1572:
1565:
1562:
1555:
1550:
1546:
1542:
1539:
1534:
1531:
1528:
1521:
1518:
1511:
1508:
1503:
1500:
1497:
1490:
1487:
1480:
1475:
1471:
1467:
1464:
1459:
1452:
1449:
1442:
1439:
1434:
1427:
1424:
1400:
1395:
1394:
1383:
1380:
1375:
1371:
1367:
1364:
1359:
1356:
1353:
1346:
1343:
1336:
1333:
1328:
1325:
1322:
1315:
1312:
1305:
1300:
1296:
1292:
1289:
1284:
1277:
1274:
1267:
1264:
1259:
1252:
1249:
1220:
1216:
1212:
1209:
1204:
1201:
1198:
1191:
1188:
1181:
1178:
1173:
1170:
1167:
1160:
1157:
1150:
1145:
1141:
1137:
1117:
1112:
1105:
1102:
1095:
1092:
1087:
1080:
1077:
1053:
1048:
1041:
1038:
1031:
1011:
1006:
1003:
1000:
993:
990:
983:
961:
957:
934:
930:
918:
917:
906:
901:
897:
893:
890:
885:
882:
879:
872:
869:
862:
859:
854:
851:
848:
841:
838:
831:
826:
822:
818:
815:
810:
803:
800:
793:
790:
785:
778:
775:
768:
765:
760:
753:
750:
743:
740:
735:
731:
727:
722:
719:
716:
709:
706:
699:
694:
690:
686:
681:
677:
651:
647:
634:
631:
616:
613:
610:
603:
600:
574:
567:
564:
540:
537:
532:
528:
505:
498:
495:
488:
483:
479:
464:
457:
452:
451:
438:
431:
428:
421:
416:
412:
406:
403:
400:
393:
390:
381:
377:
373:
368:
364:
349:simplex method
344:
341:
335:
331:
328:
324:
323:
308:
298:
294:
289:
286:
283:
280:
277:
275:
272:
269:
266:
263:
260:
257:
250:
249:
246:
241:
237:
233:
229:Maximize
226:
225:
211:canonical form
206:
203:
195:branch-and-cut
177:
174:
154:bundle methods
71:
68:
63:
59:
55:
50:
46:
42:
37:
33:
15:
9:
6:
4:
3:
2:
2977:
2966:
2963:
2962:
2960:
2945:
2942:
2941:
2938:
2928:
2925:
2923:
2920:
2918:
2915:
2913:
2910:
2908:
2905:
2903:
2902:Hill climbing
2900:
2898:
2895:
2894:
2891:
2887:
2882:
2878:
2864:
2861:
2859:
2856:
2854:
2851:
2849:
2846:
2845:
2843:
2841:
2840:Network flows
2837:
2827:
2824:
2822:
2819:
2815:
2812:
2811:
2810:
2807:
2806:
2804:
2802:
2801:Shortest path
2798:
2788:
2785:
2783:
2780:
2778:
2775:
2774:
2772:
2770:
2769:spanning tree
2764:
2761:
2759:
2753:
2745:
2741:
2738:
2737:
2736:
2733:
2731:
2728:
2726:
2723:
2721:
2718:
2717:
2715:
2711:
2707:
2703:
2702:Combinatorial
2698:
2694:
2676:
2673:
2671:
2668:
2666:
2663:
2661:
2658:
2657:
2655:
2653:
2650:
2646:
2640:
2637:
2635:
2632:
2630:
2627:
2626:
2624:
2622:
2618:
2615:
2613:
2608:
2604:
2598:
2595:
2593:
2590:
2588:
2585:
2584:
2582:
2580:
2574:
2570:
2566:
2561:
2557:
2543:
2540:
2538:
2535:
2533:
2530:
2529:
2527:
2523:
2517:
2514:
2512:
2509:
2508:
2506:
2502:
2498:
2494:
2489:
2485:
2477:
2459:
2456:
2455:
2453:
2451:
2447:
2437:
2434:
2432:
2429:
2427:
2424:
2422:
2419:
2417:
2414:
2412:
2409:
2407:
2404:
2403:
2401:
2399:
2398:Other methods
2395:
2389:
2386:
2384:
2381:
2379:
2375:
2372:
2370:
2367:
2366:
2364:
2362:
2358:
2352:
2349:
2347:
2344:
2343:
2341:
2339:
2335:
2332:
2330:
2326:
2320:
2317:
2315:
2312:
2310:
2307:
2305:
2302:
2300:
2297:
2296:
2294:
2292:
2288:
2284:
2280:
2275:
2271:
2267:
2263:
2259:
2255:
2248:
2243:
2241:
2236:
2234:
2229:
2228:
2225:
2218:
2215:
2212:
2211:
2203:
2200:
2196:
2193:
2191:
2188:
2184:
2181:
2179:
2178:0-486-43227-0
2175:
2171:
2167:
2162:
2157:
2153:
2149:
2145:
2140:
2139:
2121:
2114:
2106:
2102:
2098:
2094:
2087:
2079:
2075:
2071:
2067:
2060:
2056:
2046:
2043:
2041:
2038:
2036:
2033:
2031:
2028:
2026:
2023:
2022:
2016:
2014:
2010:
2006:
1982:
1970:
1966:
1961:
1958:
1955:
1950:
1946:
1941:
1936:
1926:
1919:
1911:
1901:
1891:
1886:
1882:
1873:
1870:
1867:
1857:
1850:
1842:
1839:
1836:
1826:
1811:
1807:
1803:
1798:
1794:
1786:
1785:
1784:
1764:
1760:
1748:
1745:
1742:
1732:
1722:
1717:
1714:
1711:
1701:
1689:
1685:
1681:
1673:
1663:
1653:
1648:
1638:
1606:
1603:
1595:
1585:
1575:
1570:
1560:
1553:
1548:
1544:
1532:
1529:
1526:
1516:
1506:
1501:
1498:
1495:
1485:
1473:
1469:
1465:
1457:
1447:
1437:
1432:
1422:
1411:
1410:
1409:
1407:
1403:
1381:
1378:
1373:
1369:
1357:
1354:
1351:
1341:
1331:
1326:
1323:
1320:
1310:
1298:
1294:
1290:
1282:
1272:
1262:
1257:
1247:
1236:
1235:
1234:
1218:
1214:
1202:
1199:
1196:
1186:
1176:
1171:
1168:
1165:
1155:
1143:
1139:
1135:
1110:
1100:
1090:
1085:
1075:
1046:
1036:
1004:
1001:
998:
988:
959:
955:
932:
928:
904:
899:
895:
883:
880:
877:
867:
857:
852:
849:
846:
836:
824:
820:
816:
808:
798:
788:
783:
773:
766:
758:
748:
738:
733:
729:
720:
717:
714:
704:
692:
688:
684:
679:
675:
667:
666:
665:
649:
645:
630:
614:
611:
608:
598:
572:
562:
538:
535:
530:
526:
503:
493:
486:
481:
477:
468:
460:
436:
426:
419:
414:
410:
404:
401:
398:
388:
379:
375:
371:
366:
362:
354:
353:
352:
350:
340:
327:
306:
296:
292:
287:
284:
281:
278:
270:
267:
264:
261:
258:
244:
239:
235:
216:
215:
214:
212:
202:
200:
196:
192:
188:
183:
173:
171:
167:
163:
159:
155:
150:
148:
144:
140:
136:
132:
127:
122:
120:
116:
112:
109:solutions to
108:
104:
100:
96:
92:
89:
69:
66:
61:
57:
53:
48:
44:
40:
35:
31:
21:
2907:Local search
2853:Edmonds–Karp
2809:Bellman–Ford
2586:
2579:minimization
2411:Gauss–Newton
2361:Quasi–Newton
2346:Trust region
2254:Optimization
2216:
2198:
2186:
2169:
2151:
2147:
2126:. Retrieved
2113:
2096:
2092:
2086:
2069:
2065:
2059:
2002:
1626:
1405:
1398:
1396:
919:
636:
462:
455:
453:
346:
333:
330:General idea
325:
208:
205:Gomory's cut
182:Ralph Gomory
179:
151:
146:
142:
134:
123:
102:
99:feasible set
94:
91:optimization
88:mathematical
85:
2927:Tabu search
2338:Convergence
2309:Line search
158:subgradient
139:convex hull
2758:algorithms
2266:heuristics
2258:Algorithms
2051:References
1623:Conclusion
347:Using the
2713:Paradigms
2612:quadratic
2329:Gradients
2291:Functions
1956:≥
1930:¯
1920:−
1917:⌋
1905:¯
1895:⌊
1861:¯
1851:−
1848:⌋
1830:¯
1820:⌊
1808:∑
1754:⌋
1736:¯
1726:⌊
1723:−
1705:¯
1686:∑
1682:−
1679:⌋
1667:¯
1657:⌊
1654:−
1642:¯
1601:⌋
1589:¯
1579:⌊
1576:−
1564:¯
1538:⌋
1520:¯
1510:⌊
1507:−
1489:¯
1470:∑
1466:−
1463:⌋
1451:¯
1441:⌊
1438:−
1426:¯
1379:≤
1363:⌋
1345:¯
1335:⌊
1332:−
1314:¯
1295:∑
1291:−
1288:⌋
1276:¯
1266:⌊
1263:−
1251:¯
1208:⌋
1190:¯
1180:⌊
1177:−
1159:¯
1140:∑
1136:−
1116:⌋
1104:¯
1094:⌊
1091:−
1079:¯
1052:⌋
1040:¯
1030:⌊
1010:⌋
992:¯
982:⌊
889:⌋
871:¯
861:⌊
858:−
840:¯
821:∑
817:−
814:⌋
802:¯
792:⌊
789:−
777:¯
764:⌋
752:¯
742:⌊
739:−
726:⌋
708:¯
698:⌊
689:∑
602:¯
566:¯
497:¯
430:¯
392:¯
376:∑
282:≥
265:≤
135:separates
67:≥
2959:Category
2944:Software
2821:Dijkstra
2652:exchange
2450:Hessians
2416:Gradient
2019:See also
193:(called
2787:Kruskal
2777:BorĹŻvka
2767:Minimum
2504:General
2262:methods
176:History
131:optimum
107:integer
2649:Basis-
2607:Linear
2577:Convex
2421:Mirror
2378:L-BFGS
2264:, and
2176:
2128:27 May
454:where
213:) as:
93:, the
2848:Dinic
2756:Graph
2814:SPFA
2782:Prim
2376:and
2174:ISBN
2130:2022
1604:>
587:and
518:and
103:cuts
2744:cut
2609:and
2156:doi
2152:123
2101:doi
2074:doi
147:cut
86:In
2961::
2260:,
2256::
2150:.
2146:.
2097:11
2095:.
2068:.
2015:.
1607:0.
1408:,
1022:,
974:,
947:,
121:.
2742:/
2246:e
2239:t
2232:v
2164:.
2158::
2132:.
2107:.
2103::
2080:.
2076::
2070:9
1983:.
1971:k
1967:x
1962:,
1959:0
1951:k
1947:x
1942:,
1937:i
1927:b
1912:i
1902:b
1892:=
1887:j
1883:x
1879:)
1874:j
1871:,
1868:i
1858:a
1843:j
1840:,
1837:i
1827:a
1817:(
1812:j
1804:+
1799:k
1795:x
1781:k
1765:j
1761:x
1757:)
1749:j
1746:,
1743:i
1733:a
1718:j
1715:,
1712:i
1702:a
1695:(
1690:j
1674:i
1664:b
1649:i
1639:b
1596:i
1586:b
1571:i
1561:b
1554:=
1549:j
1545:x
1541:)
1533:j
1530:,
1527:i
1517:a
1502:j
1499:,
1496:i
1486:a
1479:(
1474:j
1458:i
1448:b
1433:i
1423:b
1406:x
1401:i
1399:x
1382:0
1374:j
1370:x
1366:)
1358:j
1355:,
1352:i
1342:a
1327:j
1324:,
1321:i
1311:a
1304:(
1299:j
1283:i
1273:b
1258:i
1248:b
1219:j
1215:x
1211:)
1203:j
1200:,
1197:i
1187:a
1172:j
1169:,
1166:i
1156:a
1149:(
1144:j
1111:i
1101:b
1086:i
1076:b
1047:i
1037:b
1005:j
1002:,
999:i
989:a
960:j
956:x
933:i
929:x
905:.
900:j
896:x
892:)
884:j
881:,
878:i
868:a
853:j
850:,
847:i
837:a
830:(
825:j
809:i
799:b
784:i
774:b
767:=
759:i
749:b
734:j
730:x
721:j
718:,
715:i
705:a
693:j
685:+
680:i
676:x
650:i
646:x
615:j
612:,
609:i
599:a
573:i
563:b
539:0
536:=
531:j
527:x
504:i
494:b
487:=
482:i
478:x
467:'
465:j
463:x
458:i
456:x
437:i
427:b
420:=
415:j
411:x
405:j
402:,
399:i
389:a
380:j
372:+
367:i
363:x
336:i
307:.
297:i
293:x
288:,
285:0
279:x
271:,
268:b
262:x
259:A
245:x
240:T
236:c
70:2
62:3
58:x
54:+
49:2
45:x
41:+
36:1
32:x
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
