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