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