1897:
3251:
1210:
1371:. For example, one may wish to stop branching when the gap between the upper and lower bounds becomes smaller than a certain threshold. This is used when the solution is "good enough for practical purposes" and can greatly reduce the computations required. This type of solution is particularly applicable when the cost function used is
1762:
382:
may be safely discarded from the search and the recursion stops. This pruning step is usually implemented by maintaining a global variable that records the minimum upper bound seen among all instances examined so far.
34:) is a method for solving optimization problems by breaking them down into smaller sub-problems and using a bounding function to eliminate sub-problems that cannot contain the optimal solution. It is an
2051:
2008:
72:
The algorithm depends on efficient estimation of the lower and upper bounds of regions/branches of the search space. If no bounds are available, the algorithm degenerates to an exhaustive search.
1891:
1848:
1805:
1945:
2303:
594:. The depth-first variant is recommended when no good heuristic is available for producing an initial solution, because it quickly produces full solutions, and therefore upper bounds.
2211:
2146:
1571:
2402:
2369:
1518:
1618:
1186:
1470:
2336:
2271:
2179:
2114:
1157:
65:
of this tree, which represent subsets of the solution set. Before enumerating the candidate solutions of a branch, the branch is checked against upper and lower estimated
2238:
2081:
1681:
1673:
1646:
540:, do nothing; since the lower bound on this node is greater than the upper bound of the problem, it will never lead to the optimal solution, and can be discarded.
3148:
2491:
2526:
1896:
3019:
217:
enumeration of candidate solutions and testing them all. To improve on the performance of brute-force search, a B&B algorithm keeps track of
3143:
2647:
3739:
332:
represents a single candidate solution. (Optionally, if it does not, the operation may choose to return some feasible solution from among
2053:
with a value of 276.667. We test the other endpoints by sweeping the line over the region and find this is the maximum over the reals.
2881:
Hazimeh, Hussein; Mazumder, Rahul; Saab, Ali (2020). "Sparse
Regression at Scale: Branch-and-Bound rooted in First-Order Optimization".
270:
to prevent the algorithm from visiting the same candidate solution twice, but this is not required. However, an optimal solution among
2013:
69:
on the optimal solution, and is discarded if it cannot produce a better solution than the best one found so far by the algorithm.
3637:
3157:
2622:
1954:
403:
on nodes of the search tree, as well as a problem-specific branching rule. As such, the generic algorithm presented here is a
3012:
2933:
3744:
3718:
3180:
1853:
1810:
1767:
1907:
3232:
3093:
2686:
1678:
The first step is to relax the integer constraint. We have two extreme points for the first equation that form a line:
1951:
so the solution lies on one of the vertices of the region. We can find the intersection using row reduction, which is
3200:
2743:
2718:
391:
The following is the skeleton of a generic branch and bound algorithm for minimizing an arbitrary objective function
3311:
3005:
2499:
563:
3250:
2567:
2276:
3588:
1285:
2539:
2184:
3696:
3316:
229:
Turning these principles into a concrete algorithm for a specific optimization problem requires some kind of
3632:
3600:
2902:
Nowozin, Sebastian; Lampert, Christoph H. (2011). "Structured
Learning and Prediction in Computer Vision".
2119:
1524:
1279:
225:" the search space, eliminating candidate solutions that it can prove will not contain an optimal solution.
3681:
3306:
2374:
2341:
1311:
1273:
2690:
1477:
3627:
3583:
3476:
3205:
3185:
2618:
1577:
559:
158:
104:
84:
53:. A branch-and-bound algorithm consists of a systematic enumeration of candidate solutions by means of
46:
3395:
1162:
586:
that sorts nodes on their lower bound. Examples of best-first search algorithms with this premise are
448:
will denote the best solution found so far, and will be used as an upper bound on candidate solutions.
3366:
3028:
1423:
50:
3551:
2997:
2916:
1381:
and so is not known precisely but rather only known to lie within a range of values with a specific
3413:
2804:
Fukunaga, Keinosuke; Narendra, Patrenahalli M. (1975). "A branch and bound algorithm for computing
2535:
358:
provides an upper bound for the optimal objective value over the whole space of feasible solutions.
222:
2988:â Free easy-to-use GUI program intended for solving linear, integer and goal programming problems.
2456:
A. H. Land and A. G. Doig (1960). "An automatic method of solving discrete programming problems".
2308:
2243:
2151:
2086:
1140:
3595:
3494:
3210:
2658:
2426:
1291:
587:
451:
Initialize a queue to hold a partial solution with none of the variables of the problem assigned.
3686:
3671:
3561:
3439:
3088:
3065:
3032:
2911:
2790:
2437:
2432:
1406:
571:
1757:{\displaystyle {\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}={\begin{bmatrix}50\\0\end{bmatrix}}}
3575:
3541:
3444:
3386:
3267:
3073:
3053:
2994:â (Coin-or branch and cut) is an open-source mixed integer programming solver written in C++.
2840:
1345:
1306:
1268:
404:
362:
Using these operations, a B&B algorithm performs a top-down recursive search through the
92:
42:
3622:
3449:
3361:
2216:
2059:
1651:
1624:
1326:
1301:
567:
38:
1231:
287:
computes a lower bound on the value of any candidate solution in the space represented by
8:
3691:
3556:
3509:
3499:
3351:
3339:
3152:
3135:
3040:
2643:
1398:
1354:
1263:
1193:
1189:
58:
2950:
99:
optimization problems. The name "branch and bound" first occurred in the work of Little
3426:
3381:
3371:
3162:
3078:
2882:
2863:
2821:
2783:
2778:
2611:
2473:
1295:
1118:
575:
214:
135:
54:
3434:
3112:
2969:
2929:
2774:
2739:
2714:
1360:
1336:
1331:
579:
2867:
3504:
3408:
3285:
3190:
3172:
3125:
3036:
2965:
2921:
2855:
2825:
2813:
2590:
2582:
2465:
1340:
1122:
1095:
called as subroutines must be provided as applicable to the problem. The functions
3530:
1349:
1126:
1114:
143:
80:
233:
that represents sets of candidate solutions. Such a representation is called an
3518:
3403:
3290:
3224:
3195:
2566:
Little, John D. C.; Murty, Katta G.; Sweeney, Dura W.; Karel, Caroline (1963).
2418:
1321:
583:
230:
3733:
3676:
3660:
2682:
2422:
1316:
267:
2859:
2817:
1196:
techniques in order to provide guaranteed enclosures of the global minimum.
395:. To obtain an actual algorithm from this, one requires a bounding function
195:
It recursively splits the search space into smaller spaces, then minimizing
3614:
3120:
2985:
2655:
Tutorials on
Emerging Methodologies and Applications in Operations Research
2413:
1235:
2586:
3701:
3083:
1948:
1382:
363:
2595:
2338:
and there are no feasible solutions. Therefore, the maximum is 276 with
2925:
2477:
1378:
366:
of instances formed by the branch operation. Upon visiting an instance
76:
2056:
We choose the variable with the maximum fractional part, in this case
3027:
2148:. We have reached an integer solution so we move to the other branch
1368:
1224:
591:
412:
237:
of the problem. Denote the set of candidate solutions of an instance
35:
2469:
2083:
becomes the parameter for the branch and bound method. We branch to
1397:
present a generalization of branch and bound that also subsumes the
221:
on the minimum that it is trying to find, and uses these bounds to "
3103:
2991:
2887:
1220:
1061:// otherwise, bound(N_i) > B so we prune the branch; step 3.3.1
3423:
1256:
248:. The instance representation has to come with three operations:
96:
16:
Optimization by eliminating non optimal solutions to sub-problems
119:
that maximizes or minimizes the value of a real-valued function
259:
produces two or more instances that each represent a subset of
1372:
603:
2046:{\displaystyle {\begin{bmatrix}23.333\\26.667\end{bmatrix}}}
968:// Step 3.3: node represents a branch of candidate solutions
191:. A B&B algorithm operates according to two principles:
115:
The goal of a branch-and-bound algorithm is to find a value
57:: the set of candidate solutions is thought of as forming a
2841:"A branch and bound algorithm for feature subset selection"
2612:
Branch and bound methods for the traveling salesman problem
2951:"General branch and bound, and its relation to Aâ and AOâ"
2733:
2455:
378:
is equal or greater than the current upper bound; if so,
95:, and has become the most commonly used tool for solving
2734:
Jaulin, L.; Kieffer, M.; Didrit, O.; Walter, E. (2001).
2003:{\displaystyle {\begin{bmatrix}70/3\\80/3\end{bmatrix}}}
956:// else, node is a single candidate which is not optimum
146:. The rest of this section assumes that minimization of
2565:
1402:
614:// assuming the objective function f is to be minimized
88:
2904:
Foundations and Trends in
Computer Graphics and Vision
2022:
1963:
1916:
1862:
1819:
1776:
1733:
1690:
582:
branch and bound algorithm can be obtained by using a
61:
with the full set at the root. The algorithm explores
2377:
2344:
2311:
2279:
2246:
2219:
2187:
2154:
2122:
2089:
2062:
2016:
1957:
1910:
1856:
1813:
1807:. We can form the second line with the vector points
1770:
1684:
1654:
1627:
1580:
1527:
1480:
1426:
1165:
1143:
3540:
2880:
2773:
2528:
Branch and Bound
AlgorithmsâPrinciples and Examples
1886:{\displaystyle {\begin{bmatrix}70\\0\end{bmatrix}}}
1843:{\displaystyle {\begin{bmatrix}0\\40\end{bmatrix}}}
1800:{\displaystyle {\begin{bmatrix}0\\50\end{bmatrix}}}
1417:Branch and bound can be used to solve this problem
1188:, branch and bound algorithms can be combined with
2949:Nau, Dana S.; Kumar, Vipin; Kanal, Laveen (1984).
2782:
2396:
2363:
2330:
2297:
2265:
2232:
2205:
2173:
2140:
2108:
2075:
2045:
2002:
1940:{\displaystyle {\begin{bmatrix}0\\0\end{bmatrix}}}
1939:
1885:
1842:
1799:
1756:
1667:
1640:
1612:
1565:
1512:
1464:
1180:
1151:
277:must be contained in at least one of the subsets.)
2692:Algorithms and Data Structures: The Basic Toolbox
2641:
2568:"An algorithm for the traveling salesman problem"
606:-like pseudocode implementation of the above is:
206:on these smaller spaces; the splitting is called
3731:
2839:Narendra, Patrenahalli M.; Fukunaga, K. (1977).
2838:
2803:
2648:"Parallel Algorithm Design for Branch and Bound"
971:// "child_branch" represents N_i above
611:// C++-like implementation of branch and bound,
2681:
1388:
1367:Branch-and-bound may also be a base of various
490:is the best solution so far. Record it and set
130:, called an objective function, among some set
2901:
2713:. Englewood Cliff, New Jersey: Prentice-Hall.
2621:Graduate School of Industrial Administration.
422:to the optimization problem. Store its value,
3013:
2948:
2425:methods that is used extensively for solving
3574:
2421:, a hybrid between branch-and-bound and the
2292:
2280:
2200:
2188:
2135:
2123:
3052:
2761:Global Optimization using Interval Analysis
2520:
2518:
2516:
3020:
3006:
2298:{\displaystyle \langle 22,27.4286\rangle }
161:, since one can find the maximum value of
3266:
2915:
2886:
2609:
2594:
1168:
3254:Optimization computes maxima and minima.
2561:
2559:
2513:
2449:
2206:{\displaystyle \langle 22.75,27\rangle }
1895:
782:// problem-specific queue initialization
3338:
2789:. Courier Dover Publications. pp.
2657:. Kluwer Academic Press. Archived from
2637:
2635:
2524:
1412:
1087:In the above pseudocode, the functions
468:represents a single candidate solution
3732:
2758:
2628:from the original on October 20, 2012.
1255:This approach is used for a number of
854:// "node" represents N above
3658:
3474:
3450:Principal pivoting algorithm of Lemke
3337:
3265:
3051:
3001:
2708:
2556:
2141:{\displaystyle \langle 24,26\rangle }
1566:{\displaystyle 4x_{1}+7x_{2}\leq 280}
1363:, scenes shooting arrangement problem
440:. (If no heuristic is available, set
2632:
1203:
1117:as written, and could correspond to
83:whilst carrying out research at the
3740:Optimization algorithms and methods
2642:Bader, David A.; Hart, William E.;
2397:{\displaystyle x_{2}\longmapsto 26}
2364:{\displaystyle x_{1}\longmapsto 24}
1357:, including Chinese Postman problem
13:
3659:
3249:
3094:Successive parabolic interpolation
1513:{\displaystyle x_{1}+x_{2}\leq 50}
562:data structures can be used. This
386:
157:is desired; this assumption comes
14:
3756:
3475:
3414:Projective algorithm of Karmarkar
2979:
2610:Balas, Egon; Toth, Paolo (1983).
2213:. We have a decimal so we branch
1613:{\displaystyle x_{1},x_{2}\geq 0}
1129:in the C++ programming language.
75:The method was first proposed by
3409:Ellipsoid algorithm of Khachiyan
3312:Sequential quadratic programming
3149:BroydenâFletcherâGoldfarbâShanno
1208:
1181:{\displaystyle \mathbb {R} ^{n}}
1145:
399:, that computes lower bounds of
213:Branching alone would amount to
2942:
2895:
2874:
2832:
2797:
2767:
2752:
1465:{\displaystyle Z=5x_{1}+6x_{2}}
1199:
1132:
566:-based implementation yields a
454:Loop until the queue is empty:
142:is called the search space, or
3367:Reduced gradient (FrankâWolfe)
2848:IEEE Transactions on Computers
2810:IEEE Transactions on Computers
2727:
2702:
2675:
2603:
2484:
2388:
2355:
1286:Maximum satisfiability problem
1223:format but may read better as
266:. (Typically, the subsets are
1:
3697:Spiral optimization algorithm
3317:Successive linear programming
2653:. In Greenberg, H. J. (ed.).
2443:
597:
3435:Simplex algorithm of Dantzig
3307:Augmented Lagrangian methods
2970:10.1016/0004-3702(84)90004-3
2331:{\displaystyle x_{1}\geq 23}
2266:{\displaystyle x_{1}\leq 22}
2174:{\displaystyle x_{2}\geq 27}
2109:{\displaystyle x_{2}\leq 26}
1389:Relation to other algorithms
1280:Quadratic assignment problem
1152:{\displaystyle \mathbf {x} }
7:
2781:; Miller, Louis W. (2003).
2407:
1312:Computational phylogenetics
1274:Travelling salesman problem
869:represents_single_candidate
110:
10:
3761:
3745:Combinatorial optimization
2763:. New York: Marcel Dekker.
2619:Carnegie Mellon University
2305:. We try the other branch
574:(LIFO queue) will yield a
172:by finding the minimum of
159:without loss of generality
105:traveling salesman problem
85:London School of Economics
47:combinatorial optimization
3714:
3667:
3654:
3638:Pushârelabel maximum flow
3613:
3529:
3487:
3483:
3470:
3440:Revised simplex algorithm
3422:
3394:
3380:
3350:
3346:
3333:
3299:
3278:
3274:
3261:
3247:
3223:
3171:
3134:
3111:
3102:
3064:
3060:
3047:
2736:Applied Interval Analysis
51:mathematical optimization
3163:Symmetric rank-one (SR1)
3144:BerndtâHallâHallâHausman
2698:. Springer. p. 249.
2536:University of Copenhagen
608:
347:returns a solution then
3687:Parallel metaheuristics
3495:Approximation algorithm
3206:Powell's dog leg method
3158:DavidonâFletcherâPowell
3054:Unconstrained nonlinear
2958:Artificial Intelligence
2860:10.1109/TC.1977.1674939
2818:10.1109/t-c.1975.224297
2427:integer linear programs
1472:with these constraints
1292:Nearest neighbor search
1232:converting this section
3672:Evolutionary algorithm
3255:
2775:Conway, Richard Walter
2525:Clausen, Jens (1999).
2433:Evolutionary algorithm
2398:
2365:
2332:
2299:
2267:
2234:
2207:
2175:
2142:
2110:
2077:
2047:
2004:
1941:
1901:
1887:
1844:
1801:
1758:
1669:
1642:
1614:
1567:
1514:
1466:
1182:
1153:
620:branch_and_bound_solve
3445:Criss-cross algorithm
3268:Constrained nonlinear
3253:
3074:Golden-section search
2808:-nearest neighbors".
2759:Hansen, E.R. (1992).
2709:Moore, R. E. (1966).
2587:10.1287/opre.11.6.972
2399:
2366:
2333:
2300:
2273:and we find 274.571 @
2268:
2235:
2233:{\displaystyle x_{1}}
2208:
2176:
2143:
2111:
2078:
2076:{\displaystyle x_{2}}
2048:
2005:
1942:
1899:
1888:
1845:
1802:
1759:
1670:
1668:{\displaystyle x_{2}}
1643:
1641:{\displaystyle x_{1}}
1615:
1568:
1515:
1467:
1379:statistical estimates
1346:Structured prediction
1307:Cutting stock problem
1269:Nonlinear programming
1183:
1154:
833:CandidateSolutionTree
770:CandidateSolutionTree
746:CombinatorialSolution
701:CombinatorialSolution
617:CombinatorialSolution
523:. For each of these:
516:to produce new nodes
405:higher-order function
49:problems, as well as
3362:Cutting-plane method
2785:Theory of Scheduling
2738:. Berlin: Springer.
2644:Phillips, Cynthia A.
2534:(Technical report).
2375:
2342:
2309:
2277:
2244:
2217:
2185:
2181:. We obtain 275.75 @
2152:
2120:
2087:
2060:
2014:
1955:
1908:
1854:
1811:
1768:
1682:
1652:
1625:
1578:
1525:
1478:
1424:
1413:Optimization Example
1377:or is the result of
1327:0/1 knapsack problem
1322:Parameter estimation
1302:Flow shop scheduling
1163:
1141:
1111:lower_bound_function
1013:lower_bound_function
650:lower_bound_function
626:CombinatorialProblem
588:Dijkstra's algorithm
568:breadth-first search
370:, it checks whether
93:discrete programming
3692:Simulated annealing
3510:Integer programming
3500:Dynamic programming
3340:Convex optimization
3201:LevenbergâMarquardt
2779:Maxwell, William L.
2575:Operations Research
1904:The third point is
1409:search algorithms.
1355:Arc routing problem
1264:Integer programming
1125:and other types of
1093:populate_candidates
1028:problem_upper_bound
935:problem_upper_bound
908:problem_upper_bound
791:populate_candidates
725:problem_upper_bound
668:problem_upper_bound
590:and its descendant
328:determines whether
136:candidate solutions
3372:Subgradient method
3256:
3181:Conjugate gradient
3089:NelderâMead method
2926:10.1561/0600000033
2438:Alphaâbeta pruning
2394:
2361:
2328:
2295:
2263:
2230:
2203:
2171:
2138:
2106:
2073:
2043:
2037:
2000:
1994:
1949:convex hull region
1937:
1931:
1902:
1883:
1877:
1840:
1834:
1797:
1791:
1754:
1748:
1719:
1665:
1638:
1610:
1563:
1510:
1462:
1296:Keinosuke Fukunaga
1234:, if appropriate.
1178:
1149:
1119:lambda expressions
1103:objective_function
941:objective_function
887:objective_function
755:heuristic_solution
737:heuristic_solution
731:objective_function
704:heuristic_solution
638:objective_function
558:Several different
415:, find a solution
134:of admissible, or
55:state space search
3727:
3726:
3710:
3709:
3650:
3649:
3646:
3645:
3609:
3608:
3570:
3569:
3466:
3465:
3462:
3461:
3458:
3457:
3329:
3328:
3325:
3324:
3245:
3244:
3241:
3240:
3219:
3218:
2935:978-1-60198-457-9
2711:Interval Analysis
2116:and obtain 276 @
1361:Talent Scheduling
1337:Feature selection
1332:Set cover problem
1253:
1252:
1190:interval analysis
1123:function pointers
1113:) are treated as
635:ObjectiveFunction
89:British Petroleum
3752:
3656:
3655:
3572:
3571:
3538:
3537:
3515:Branch and bound
3505:Greedy algorithm
3485:
3484:
3472:
3471:
3392:
3391:
3348:
3347:
3335:
3334:
3276:
3275:
3263:
3262:
3211:Truncated Newton
3126:Wolfe conditions
3109:
3108:
3062:
3061:
3049:
3048:
3022:
3015:
3008:
2999:
2998:
2974:
2973:
2955:
2946:
2940:
2939:
2919:
2910:(3â4): 185â365.
2899:
2893:
2892:
2890:
2878:
2872:
2871:
2845:
2836:
2830:
2829:
2807:
2801:
2795:
2794:
2788:
2771:
2765:
2764:
2756:
2750:
2749:
2731:
2725:
2724:
2706:
2700:
2699:
2697:
2679:
2673:
2672:
2670:
2669:
2663:
2652:
2639:
2630:
2629:
2627:
2616:
2607:
2601:
2600:
2598:
2572:
2563:
2554:
2553:
2551:
2550:
2544:
2538:. Archived from
2533:
2522:
2511:
2510:
2508:
2507:
2498:. Archived from
2488:
2482:
2481:
2453:
2403:
2401:
2400:
2395:
2387:
2386:
2370:
2368:
2367:
2362:
2354:
2353:
2337:
2335:
2334:
2329:
2321:
2320:
2304:
2302:
2301:
2296:
2272:
2270:
2269:
2264:
2256:
2255:
2239:
2237:
2236:
2231:
2229:
2228:
2212:
2210:
2209:
2204:
2180:
2178:
2177:
2172:
2164:
2163:
2147:
2145:
2144:
2139:
2115:
2113:
2112:
2107:
2099:
2098:
2082:
2080:
2079:
2074:
2072:
2071:
2052:
2050:
2049:
2044:
2042:
2041:
2009:
2007:
2006:
2001:
1999:
1998:
1988:
1973:
1946:
1944:
1943:
1938:
1936:
1935:
1892:
1890:
1889:
1884:
1882:
1881:
1849:
1847:
1846:
1841:
1839:
1838:
1806:
1804:
1803:
1798:
1796:
1795:
1763:
1761:
1760:
1755:
1753:
1752:
1724:
1723:
1716:
1715:
1702:
1701:
1674:
1672:
1671:
1666:
1664:
1663:
1647:
1645:
1644:
1639:
1637:
1636:
1619:
1617:
1616:
1611:
1603:
1602:
1590:
1589:
1572:
1570:
1569:
1564:
1556:
1555:
1540:
1539:
1519:
1517:
1516:
1511:
1503:
1502:
1490:
1489:
1471:
1469:
1468:
1463:
1461:
1460:
1445:
1444:
1341:machine learning
1248:
1245:
1239:
1230:You can help by
1212:
1211:
1204:
1187:
1185:
1184:
1179:
1177:
1176:
1171:
1158:
1156:
1155:
1150:
1148:
1127:callable objects
1115:function objects
1112:
1108:
1104:
1100:
1094:
1090:
1083:
1080:
1077:
1074:
1071:
1068:
1065:
1062:
1059:
1056:
1053:
1050:
1047:
1044:
1041:
1038:
1035:
1032:
1029:
1026:
1023:
1020:
1017:
1014:
1011:
1008:
1005:
1002:
999:
996:
993:
990:
987:
984:
981:
978:
975:
972:
969:
966:
963:
960:
957:
954:
951:
948:
945:
942:
939:
936:
933:
930:
927:
924:
921:
918:
915:
912:
909:
906:
903:
900:
897:
894:
891:
888:
885:
882:
879:
876:
873:
870:
867:
864:
861:
858:
855:
852:
849:
846:
843:
840:
837:
834:
831:
828:
825:
822:
819:
816:
813:
810:
807:
804:
801:
798:
795:
792:
789:
786:
783:
780:
777:
774:
771:
768:
765:
762:
759:
756:
753:
750:
747:
744:
741:
738:
735:
732:
729:
726:
723:
720:
717:
714:
711:
708:
705:
702:
699:
696:
693:
690:
687:
684:
681:
678:
675:
672:
669:
666:
663:
662:// Step 1 above.
660:
657:
654:
651:
648:
647:BoundingFunction
645:
642:
639:
636:
633:
630:
627:
624:
621:
618:
615:
612:
549:
539:
522:
515:
504:
489:
485:
471:
467:
460:
447:
443:
439:
421:
402:
398:
394:
381:
377:
369:
357:
346:
338:
331:
327:
317:
310:
306:
290:
286:
276:
265:
258:
247:
240:
205:
190:
171:
156:
141:
133:
129:
118:
20:Branch and bound
3760:
3759:
3755:
3754:
3753:
3751:
3750:
3749:
3730:
3729:
3728:
3723:
3706:
3663:
3642:
3605:
3566:
3543:
3532:
3525:
3479:
3454:
3418:
3385:
3376:
3353:
3342:
3321:
3295:
3291:Penalty methods
3286:Barrier methods
3270:
3257:
3237:
3233:Newton's method
3215:
3167:
3130:
3098:
3079:Powell's method
3056:
3043:
3026:
2982:
2977:
2953:
2947:
2943:
2936:
2917:10.1.1.636.2651
2900:
2896:
2879:
2875:
2843:
2837:
2833:
2805:
2802:
2798:
2772:
2768:
2757:
2753:
2746:
2732:
2728:
2721:
2707:
2703:
2695:
2680:
2676:
2667:
2665:
2661:
2650:
2640:
2633:
2625:
2614:
2608:
2604:
2570:
2564:
2557:
2548:
2546:
2542:
2531:
2523:
2514:
2505:
2503:
2490:
2489:
2485:
2470:10.2307/1910129
2454:
2450:
2446:
2410:
2382:
2378:
2376:
2373:
2372:
2349:
2345:
2343:
2340:
2339:
2316:
2312:
2310:
2307:
2306:
2278:
2275:
2274:
2251:
2247:
2245:
2242:
2241:
2224:
2220:
2218:
2215:
2214:
2186:
2183:
2182:
2159:
2155:
2153:
2150:
2149:
2121:
2118:
2117:
2094:
2090:
2088:
2085:
2084:
2067:
2063:
2061:
2058:
2057:
2036:
2035:
2029:
2028:
2018:
2017:
2015:
2012:
2011:
1993:
1992:
1984:
1978:
1977:
1969:
1959:
1958:
1956:
1953:
1952:
1930:
1929:
1923:
1922:
1912:
1911:
1909:
1906:
1905:
1876:
1875:
1869:
1868:
1858:
1857:
1855:
1852:
1851:
1833:
1832:
1826:
1825:
1815:
1814:
1812:
1809:
1808:
1790:
1789:
1783:
1782:
1772:
1771:
1769:
1766:
1765:
1747:
1746:
1740:
1739:
1729:
1728:
1718:
1717:
1711:
1707:
1704:
1703:
1697:
1693:
1686:
1685:
1683:
1680:
1679:
1675:are integers.
1659:
1655:
1653:
1650:
1649:
1632:
1628:
1626:
1623:
1622:
1598:
1594:
1585:
1581:
1579:
1576:
1575:
1551:
1547:
1535:
1531:
1526:
1523:
1522:
1498:
1494:
1485:
1481:
1479:
1476:
1475:
1456:
1452:
1440:
1436:
1425:
1422:
1421:
1415:
1391:
1350:computer vision
1249:
1243:
1240:
1229:
1213:
1209:
1202:
1172:
1167:
1166:
1164:
1161:
1160:
1159:is a vector of
1144:
1142:
1139:
1138:
1135:
1110:
1106:
1102:
1096:
1092:
1089:heuristic_solve
1088:
1085:
1084:
1081:
1078:
1076:current_optimum
1075:
1072:
1069:
1066:
1063:
1060:
1057:
1054:
1051:
1048:
1045:
1042:
1039:
1037:candidate_queue
1036:
1033:
1030:
1027:
1024:
1021:
1018:
1015:
1012:
1009:
1006:
1003:
1000:
998:candidate_nodes
997:
994:
991:
988:
985:
982:
979:
976:
973:
970:
967:
964:
961:
958:
955:
952:
949:
947:current_optimum
946:
943:
940:
937:
934:
931:
928:
925:
922:
919:
917:current_optimum
916:
913:
910:
907:
904:
901:
898:
895:
892:
889:
886:
883:
880:
877:
874:
871:
868:
865:
862:
859:
856:
853:
850:
847:
844:
842:candidate_queue
841:
838:
835:
832:
829:
827:// Step 3 above
826:
823:
820:
817:
814:
812:candidate_queue
811:
808:
805:
802:
799:
796:
793:
790:
787:
785:candidate_queue
784:
781:
778:
776:candidate_queue
775:
772:
769:
766:
763:
761:// Step 2 above
760:
757:
754:
751:
749:current_optimum
748:
745:
742:
739:
736:
733:
730:
727:
724:
721:
718:
715:
712:
710:heuristic_solve
709:
706:
703:
700:
697:
694:
691:
688:
685:
682:
679:
676:
673:
670:
667:
664:
661:
658:
655:
652:
649:
646:
643:
640:
637:
634:
631:
628:
625:
622:
619:
616:
613:
610:
600:
548:
544:
533:
527:
521:
517:
513:
491:
487:
473:
469:
465:
458:
445:
441:
436:
423:
420:
416:
400:
396:
392:
389:
387:Generic version
379:
371:
367:
348:
340:
337:
333:
329:
321:
316:
312:
308:
292:
288:
280:
275:
271:
264:
260:
252:
246:
242:
238:
196:
173:
162:
147:
144:feasible region
139:
131:
120:
116:
113:
39:design paradigm
17:
12:
11:
5:
3758:
3748:
3747:
3742:
3725:
3724:
3722:
3721:
3715:
3712:
3711:
3708:
3707:
3705:
3704:
3699:
3694:
3689:
3684:
3679:
3674:
3668:
3665:
3664:
3661:Metaheuristics
3652:
3651:
3648:
3647:
3644:
3643:
3641:
3640:
3635:
3633:FordâFulkerson
3630:
3625:
3619:
3617:
3611:
3610:
3607:
3606:
3604:
3603:
3601:FloydâWarshall
3598:
3593:
3592:
3591:
3580:
3578:
3568:
3567:
3565:
3564:
3559:
3554:
3548:
3546:
3535:
3527:
3526:
3524:
3523:
3522:
3521:
3507:
3502:
3497:
3491:
3489:
3481:
3480:
3468:
3467:
3464:
3463:
3460:
3459:
3456:
3455:
3453:
3452:
3447:
3442:
3437:
3431:
3429:
3420:
3419:
3417:
3416:
3411:
3406:
3404:Affine scaling
3400:
3398:
3396:Interior point
3389:
3378:
3377:
3375:
3374:
3369:
3364:
3358:
3356:
3344:
3343:
3331:
3330:
3327:
3326:
3323:
3322:
3320:
3319:
3314:
3309:
3303:
3301:
3300:Differentiable
3297:
3296:
3294:
3293:
3288:
3282:
3280:
3272:
3271:
3259:
3258:
3248:
3246:
3243:
3242:
3239:
3238:
3236:
3235:
3229:
3227:
3221:
3220:
3217:
3216:
3214:
3213:
3208:
3203:
3198:
3193:
3188:
3183:
3177:
3175:
3169:
3168:
3166:
3165:
3160:
3155:
3146:
3140:
3138:
3132:
3131:
3129:
3128:
3123:
3117:
3115:
3106:
3100:
3099:
3097:
3096:
3091:
3086:
3081:
3076:
3070:
3068:
3058:
3057:
3045:
3044:
3025:
3024:
3017:
3010:
3002:
2996:
2995:
2989:
2981:
2980:External links
2978:
2976:
2975:
2941:
2934:
2894:
2873:
2854:(9): 917â922.
2831:
2812:(7): 750â753.
2796:
2766:
2751:
2744:
2726:
2719:
2701:
2687:Sanders, Peter
2683:Mehlhorn, Kurt
2674:
2631:
2602:
2581:(6): 972â989.
2555:
2512:
2483:
2464:(3): 497â520.
2447:
2445:
2442:
2441:
2440:
2435:
2430:
2419:Branch-and-cut
2416:
2409:
2406:
2393:
2390:
2385:
2381:
2360:
2357:
2352:
2348:
2327:
2324:
2319:
2315:
2294:
2291:
2288:
2285:
2282:
2262:
2259:
2254:
2250:
2227:
2223:
2202:
2199:
2196:
2193:
2190:
2170:
2167:
2162:
2158:
2137:
2134:
2131:
2128:
2125:
2105:
2102:
2097:
2093:
2070:
2066:
2040:
2034:
2031:
2030:
2027:
2024:
2023:
2021:
1997:
1991:
1987:
1983:
1980:
1979:
1976:
1972:
1968:
1965:
1964:
1962:
1934:
1928:
1925:
1924:
1921:
1918:
1917:
1915:
1900:the two lines.
1880:
1874:
1871:
1870:
1867:
1864:
1863:
1861:
1837:
1831:
1828:
1827:
1824:
1821:
1820:
1818:
1794:
1788:
1785:
1784:
1781:
1778:
1777:
1775:
1751:
1745:
1742:
1741:
1738:
1735:
1734:
1732:
1727:
1722:
1714:
1710:
1706:
1705:
1700:
1696:
1692:
1691:
1689:
1662:
1658:
1635:
1631:
1609:
1606:
1601:
1597:
1593:
1588:
1584:
1562:
1559:
1554:
1550:
1546:
1543:
1538:
1534:
1530:
1509:
1506:
1501:
1497:
1493:
1488:
1484:
1459:
1455:
1451:
1448:
1443:
1439:
1435:
1432:
1429:
1414:
1411:
1390:
1387:
1365:
1364:
1358:
1352:
1343:
1334:
1329:
1324:
1319:
1314:
1309:
1304:
1299:
1289:
1283:
1277:
1271:
1266:
1251:
1250:
1216:
1214:
1207:
1201:
1198:
1175:
1170:
1147:
1134:
1131:
680:numeric_limits
609:
599:
596:
584:priority queue
556:
555:
554:
553:
552:
551:
546:
541:
531:
519:
506:
462:
461:off the queue.
452:
449:
444:to infinity.)
434:
418:
388:
385:
360:
359:
335:
319:
314:
278:
273:
262:
244:
231:data structure
227:
226:
211:
112:
109:
15:
9:
6:
4:
3:
2:
3757:
3746:
3743:
3741:
3738:
3737:
3735:
3720:
3717:
3716:
3713:
3703:
3700:
3698:
3695:
3693:
3690:
3688:
3685:
3683:
3680:
3678:
3677:Hill climbing
3675:
3673:
3670:
3669:
3666:
3662:
3657:
3653:
3639:
3636:
3634:
3631:
3629:
3626:
3624:
3621:
3620:
3618:
3616:
3615:Network flows
3612:
3602:
3599:
3597:
3594:
3590:
3587:
3586:
3585:
3582:
3581:
3579:
3577:
3576:Shortest path
3573:
3563:
3560:
3558:
3555:
3553:
3550:
3549:
3547:
3545:
3544:spanning tree
3539:
3536:
3534:
3528:
3520:
3516:
3513:
3512:
3511:
3508:
3506:
3503:
3501:
3498:
3496:
3493:
3492:
3490:
3486:
3482:
3478:
3477:Combinatorial
3473:
3469:
3451:
3448:
3446:
3443:
3441:
3438:
3436:
3433:
3432:
3430:
3428:
3425:
3421:
3415:
3412:
3410:
3407:
3405:
3402:
3401:
3399:
3397:
3393:
3390:
3388:
3383:
3379:
3373:
3370:
3368:
3365:
3363:
3360:
3359:
3357:
3355:
3349:
3345:
3341:
3336:
3332:
3318:
3315:
3313:
3310:
3308:
3305:
3304:
3302:
3298:
3292:
3289:
3287:
3284:
3283:
3281:
3277:
3273:
3269:
3264:
3260:
3252:
3234:
3231:
3230:
3228:
3226:
3222:
3212:
3209:
3207:
3204:
3202:
3199:
3197:
3194:
3192:
3189:
3187:
3184:
3182:
3179:
3178:
3176:
3174:
3173:Other methods
3170:
3164:
3161:
3159:
3156:
3154:
3150:
3147:
3145:
3142:
3141:
3139:
3137:
3133:
3127:
3124:
3122:
3119:
3118:
3116:
3114:
3110:
3107:
3105:
3101:
3095:
3092:
3090:
3087:
3085:
3082:
3080:
3077:
3075:
3072:
3071:
3069:
3067:
3063:
3059:
3055:
3050:
3046:
3042:
3038:
3034:
3030:
3023:
3018:
3016:
3011:
3009:
3004:
3003:
3000:
2993:
2990:
2987:
2984:
2983:
2971:
2967:
2963:
2959:
2952:
2945:
2937:
2931:
2927:
2923:
2918:
2913:
2909:
2905:
2898:
2889:
2884:
2877:
2869:
2865:
2861:
2857:
2853:
2849:
2842:
2835:
2827:
2823:
2819:
2815:
2811:
2800:
2792:
2787:
2786:
2780:
2776:
2770:
2762:
2755:
2747:
2745:1-85233-219-0
2741:
2737:
2730:
2722:
2720:0-13-476853-1
2716:
2712:
2705:
2694:
2693:
2688:
2684:
2678:
2664:on 2017-08-13
2660:
2656:
2649:
2645:
2638:
2636:
2624:
2620:
2613:
2606:
2597:
2592:
2588:
2584:
2580:
2576:
2569:
2562:
2560:
2545:on 2015-09-23
2541:
2537:
2530:
2529:
2521:
2519:
2517:
2502:on 2021-02-24
2501:
2497:
2496:www.lse.ac.uk
2493:
2487:
2479:
2475:
2471:
2467:
2463:
2459:
2452:
2448:
2439:
2436:
2434:
2431:
2428:
2424:
2423:cutting plane
2420:
2417:
2415:
2412:
2411:
2405:
2391:
2383:
2379:
2358:
2350:
2346:
2325:
2322:
2317:
2313:
2289:
2286:
2283:
2260:
2257:
2252:
2248:
2225:
2221:
2197:
2194:
2191:
2168:
2165:
2160:
2156:
2132:
2129:
2126:
2103:
2100:
2095:
2091:
2068:
2064:
2054:
2038:
2032:
2025:
2019:
1995:
1989:
1985:
1981:
1974:
1970:
1966:
1960:
1950:
1932:
1926:
1919:
1913:
1898:
1894:
1878:
1872:
1865:
1859:
1835:
1829:
1822:
1816:
1792:
1786:
1779:
1773:
1749:
1743:
1736:
1730:
1725:
1720:
1712:
1708:
1698:
1694:
1687:
1676:
1660:
1656:
1633:
1629:
1620:
1607:
1604:
1599:
1595:
1591:
1586:
1582:
1573:
1560:
1557:
1552:
1548:
1544:
1541:
1536:
1532:
1528:
1520:
1507:
1504:
1499:
1495:
1491:
1486:
1482:
1473:
1457:
1453:
1449:
1446:
1441:
1437:
1433:
1430:
1427:
1418:
1410:
1408:
1404:
1400:
1396:
1386:
1384:
1380:
1376:
1375:
1370:
1362:
1359:
1356:
1353:
1351:
1347:
1344:
1342:
1338:
1335:
1333:
1330:
1328:
1325:
1323:
1320:
1318:
1317:Set inversion
1315:
1313:
1310:
1308:
1305:
1303:
1300:
1297:
1293:
1290:
1287:
1284:
1281:
1278:
1275:
1272:
1270:
1267:
1265:
1262:
1261:
1260:
1258:
1247:
1244:February 2023
1238:is available.
1237:
1233:
1227:
1226:
1222:
1217:This section
1215:
1206:
1205:
1197:
1195:
1191:
1173:
1130:
1128:
1124:
1120:
1116:
1099:
1055:// Step 3.3.2
743:// B = f(x_h)
607:
605:
595:
593:
589:
585:
581:
578:algorithm. A
577:
573:
569:
565:
561:
550:on the queue.
542:
538:
534:
525:
524:
511:
507:
502:
498:
494:
484:
480:
476:
463:
456:
455:
453:
450:
437:
430:
426:
414:
410:
409:
408:
406:
384:
375:
365:
355:
351:
344:
325:
320:
304:
300:
296:
284:
279:
269:
256:
251:
250:
249:
236:
232:
224:
220:
216:
212:
209:
203:
199:
194:
193:
192:
188:
184:
180:
176:
169:
165:
160:
154:
150:
145:
137:
127:
123:
108:
106:
102:
98:
94:
90:
87:sponsored by
86:
82:
78:
73:
70:
68:
64:
60:
56:
52:
48:
44:
40:
37:
33:
29:
25:
21:
3682:Local search
3628:EdmondsâKarp
3584:BellmanâFord
3514:
3354:minimization
3186:GaussâNewton
3136:QuasiâNewton
3121:Trust region
3029:Optimization
2964:(1): 29â58.
2961:
2957:
2944:
2907:
2903:
2897:
2876:
2851:
2847:
2834:
2809:
2799:
2784:
2769:
2760:
2754:
2735:
2729:
2710:
2704:
2691:
2677:
2666:. Retrieved
2659:the original
2654:
2605:
2596:1721.1/46828
2578:
2574:
2547:. Retrieved
2540:the original
2527:
2504:. Retrieved
2500:the original
2495:
2492:"Staff News"
2486:
2461:
2458:Econometrica
2457:
2451:
2414:Backtracking
2055:
1947:. This is a
1903:
1677:
1621:
1574:
1521:
1474:
1419:
1416:
1394:
1392:
1373:
1366:
1254:
1241:
1236:Editing help
1218:
1200:Applications
1136:
1133:Improvements
1097:
1086:
1049:child_branch
1019:child_branch
986:child_branch
601:
557:
543:Else, store
536:
529:
509:
500:
496:
492:
482:
478:
474:
457:Take a node
432:
428:
424:
390:
373:
361:
353:
349:
342:
323:
302:
298:
294:
282:
254:
234:
228:
218:
207:
201:
197:
186:
182:
178:
174:
167:
163:
152:
148:
125:
121:
114:
100:
91:in 1960 for
74:
71:
66:
62:
31:
27:
23:
19:
18:
3702:Tabu search
3113:Convergence
3084:Line search
1383:probability
878:// Step 3.2
830:// Step 3.1
576:depth-first
291:, that is,
215:brute-force
81:Alison Doig
59:rooted tree
3734:Categories
3533:algorithms
3041:heuristics
3033:Algorithms
2888:2004.06152
2668:2015-09-16
2617:(Report).
2549:2014-08-13
2506:2018-10-08
2444:References
1407:alpha-beta
1369:heuristics
1259:problems:
1194:contractor
983:&&
598:Pseudocode
580:best-first
564:FIFO queue
352:(solution(
138:. The set
77:Ailsa Land
3488:Paradigms
3387:quadratic
3104:Gradients
3066:Functions
2912:CiteSeerX
2389:⟼
2356:⟼
2323:≥
2293:⟩
2281:⟨
2258:≤
2201:⟩
2189:⟨
2166:≥
2136:⟩
2124:⟨
2101:≤
1605:≥
1558:≤
1505:≤
1420:Maximize
1288:(MAX-SAT)
929:candidate
899:candidate
653:/*bound*/
592:A* search
413:heuristic
341:solution(
322:solution(
208:branching
36:algorithm
3719:Software
3596:Dijkstra
3427:exchange
3225:Hessians
3191:Gradient
2868:26204315
2689:(2008).
2646:(2004).
2623:Archived
2408:See also
692:infinity
411:Using a
307:for all
268:disjoint
235:instance
111:Overview
63:branches
43:discrete
3562:Kruskal
3552:BorĹŻvka
3542:Minimum
3279:General
3037:methods
2826:5941649
2478:1910129
2290:27.4286
1257:NP-hard
1043:enqueue
797:problem
716:problem
629:problem
535:) >
486:, then
481:) <
253:branch(
103:on the
97:NP-hard
28:B&B
3424:Basis-
3382:Linear
3352:Convex
3196:Mirror
3153:L-BFGS
3039:, and
2932:
2914:
2866:
2824:
2742:
2717:
2476:
2033:26.667
2026:23.333
1395:et al.
1219:is in
1105:) and
1073:return
722:// x_h
698:// = B
689:>::
686:double
665:double
528:bound(
510:branch
508:Else,
372:bound(
339:.) If
293:bound(
281:bound(
219:bounds
101:et al.
67:bounds
3623:Dinic
3531:Graph
2954:(PDF)
2883:arXiv
2864:S2CID
2844:(PDF)
2822:S2CID
2791:56â61
2696:(PDF)
2662:(PDF)
2651:(PDF)
2626:(PDF)
2615:(PDF)
2571:(PDF)
2543:(PDF)
2532:(PDF)
2474:JSTOR
2192:22.75
2010:, or
1374:noisy
1282:(QAP)
1276:(TSP)
1225:prose
1137:When
1107:bound
1025:<=
818:empty
803:while
764:queue
641:/*f*/
572:stack
560:queue
397:bound
223:prune
181:) = â
30:, or
3589:SPFA
3557:Prim
3151:and
2986:LiPS
2930:ISBN
2852:C-26
2740:ISBN
2715:ISBN
2371:and
1850:and
1764:and
1648:and
1405:and
1393:Nau
1294:(by
1221:list
1192:and
1091:and
992:node
980:auto
962:else
923:node
905:<
893:node
863:node
836:node
773:>
767:<
683:<
570:. A
472:and
364:tree
297:) â¤
79:and
45:and
41:for
3519:cut
3384:and
2992:Cbc
2966:doi
2922:doi
2856:doi
2814:doi
2591:hdl
2583:doi
2466:doi
2240:to
1893:.
1561:280
1348:in
1339:in
974:for
932:();
902:())
872:())
851:();
848:pop
821:())
674:std
604:C++
526:If
512:on
464:If
311:in
241:by
32:BnB
3736::
3035:,
3031::
2962:23
2960:.
2956:.
2928:.
2920:.
2906:.
2862:.
2850:.
2846:.
2820:.
2777:;
2685:;
2634:^
2589:.
2579:11
2577:.
2573:.
2558:^
2515:^
2494:.
2472:.
2462:28
2460:.
2404:.
2392:26
2359:24
2326:23
2284:22
2261:22
2198:27
2169:27
2133:26
2127:24
2104:26
1982:80
1967:70
1866:70
1830:40
1787:50
1737:50
1508:50
1403:B*
1401:,
1399:A*
1385:.
1121:,
1052:);
1007:if
950:);
881:if
857:if
800:);
740:);
719:);
677:::
602:A
495:â
427:=
407:.
356:))
107:.
26:,
24:BB
3517:/
3021:e
3014:t
3007:v
2972:.
2968::
2938:.
2924::
2908:6
2891:.
2885::
2870:.
2858::
2828:.
2816::
2806:k
2793:.
2748:.
2723:.
2671:.
2599:.
2593::
2585::
2552:.
2509:.
2480:.
2468::
2429:.
2384:2
2380:x
2351:1
2347:x
2318:1
2314:x
2287:,
2253:1
2249:x
2226:1
2222:x
2195:,
2161:2
2157:x
2130:,
2096:2
2092:x
2069:2
2065:x
2039:]
2020:[
1996:]
1990:3
1986:/
1975:3
1971:/
1961:[
1933:]
1927:0
1920:0
1914:[
1879:]
1873:0
1860:[
1836:]
1823:0
1817:[
1793:]
1780:0
1774:[
1750:]
1744:0
1731:[
1726:=
1721:]
1713:2
1709:x
1699:1
1695:x
1688:[
1661:2
1657:x
1634:1
1630:x
1608:0
1600:2
1596:x
1592:,
1587:1
1583:x
1553:2
1549:x
1545:7
1542:+
1537:1
1533:x
1529:4
1500:2
1496:x
1492:+
1487:1
1483:x
1458:2
1454:x
1450:6
1447:+
1442:1
1438:x
1434:5
1431:=
1428:Z
1298:)
1246:)
1242:(
1228:.
1174:n
1169:R
1146:x
1109:(
1101:(
1098:f
1082:}
1079:;
1070:}
1067:}
1064:}
1058:}
1046:(
1040:.
1034:{
1031:)
1022:)
1016:(
1010:(
1004:{
1001:)
995:.
989::
977:(
965:{
959:}
953:}
944:(
938:=
926:.
920:=
914:{
911:)
896:.
890:(
884:(
875:{
866:.
860:(
845:.
839:=
824:{
815:.
809:!
806:(
794:(
788:=
779:;
758:;
752:=
734:(
728:=
713:(
707:=
695:;
671:=
659:{
656:)
644:,
632:,
623:(
547:i
545:N
537:B
532:i
530:N
520:i
518:N
514:N
505:.
503:)
501:x
499:(
497:f
493:B
488:x
483:B
479:x
477:(
475:f
470:x
466:N
459:N
446:B
442:B
438:)
435:h
433:x
431:(
429:f
425:B
419:h
417:x
401:f
393:f
380:I
376:)
374:I
368:I
354:I
350:f
345:)
343:I
336:I
334:S
330:I
326:)
324:I
318:.
315:I
313:S
309:x
305:)
303:x
301:(
299:f
295:I
289:I
285:)
283:I
274:I
272:S
263:I
261:S
257:)
255:I
245:I
243:S
239:I
210:.
204:)
202:x
200:(
198:f
189:)
187:x
185:(
183:f
179:x
177:(
175:g
170:)
168:x
166:(
164:f
155:)
153:x
151:(
149:f
140:S
132:S
128:)
126:x
124:(
122:f
117:x
22:(
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.