557:
416:
5609:
1500:
assigned to a route and whether a driver is assigned to a particular train or subway. The zero–one programming technique has been successfully applied to solve a project selection problem in which projects are mutually exclusive and/or technologically interdependent. It is used in a special case of integer programming, in which all the decision variables are integers. Variable can assume only the values zero or one.
247:
258:
2510:
726:
123:
3647:
Short-term memory can consist of previously tried solutions while medium-term memory can consist of values for the integer constrained variables that have resulted in high objective values (assuming the ILP is a maximization problem). Finally, long-term memory can guide the search towards integer values that have not previously been tried.
2381:
411:{\displaystyle {\begin{aligned}&{\underset {\mathbf {x} \in \mathbb {Z} ^{n}}{\text{maximize}}}&&\mathbf {c} ^{\mathrm {T} }\mathbf {x} \\&{\text{subject to}}&&A\mathbf {x} +\mathbf {s} =\mathbf {b} ,\\&&&\mathbf {s} \geq \mathbf {0} ,\\&&&\mathbf {x} \geq \mathbf {0} ,\end{aligned}}}
1039:
3682:
for the traveling salesman problem. A disadvantage of heuristic methods is that if they fail to find a solution, it cannot be determined whether it is because there is no feasible solution or whether the algorithm simply was unable to find one. Further, it is usually impossible to quantify how close
1499:
These problems involve service and vehicle scheduling in transportation networks. For example, a problem may involve assigning buses or subways to individual routes so that a timetable can be met, and also to equip them with drivers. Here binary decision variables indicate whether a bus or subway is
731:
The feasible integer points are shown in red, and the red dashed lines indicate their convex hull, which is the smallest convex polyhedron that contains all of these points. The blue lines together with the coordinate axes define the polyhedron of the LP relaxation, which is given by the inequalities
3646:
can be used to search for solutions to ILPs. To use tabu search to solve ILPs, moves can be defined as incrementing or decrementing an integer constrained variable of a feasible solution while keeping all other integer-constrained variables constant. The unrestricted variables are then solved for.
2576:
feasible, although not necessarily optimal, solution can be returned. Further, the solutions of the LP relaxations can be used to provide a worst-case estimate of how far from optimality the returned solution is. Finally, branch and bound methods can be used to return multiple optimal solutions.
2575:
method that combines both branch and bound and cutting plane methods. Branch and bound algorithms have a number of advantages over algorithms that only use cutting planes. One advantage is that the algorithms can be terminated early and as long as at least one integral solution has been found, a
1508:
Territorial partitioning or districting problems consist of partitioning a geographical region into districts in order to plan some operations while considering different criteria or constraints. Some requirements for this problem are: contiguity, compactness, balance or equity, respect of natural
1517:
The goal of these problems is to design a network of lines to install so that a predefined set of communication requirements are met and the total cost of the network is minimal. This requires optimizing both the topology of the network along with setting the capacities of the various lines. In
1490:
and involves determining production yield for several crops that can share resources (e.g. land, labor, capital, seeds, fertilizer, etc.). A possible objective is to maximize the total production, without exceeding the available resources. In some cases, this can be expressed in terms of a linear
1530:
mobile networks involves distributing available frequencies across the antennas so that users can be served and interference is minimized between the antennas. This problem can be formulated as an integer linear program in which binary variables indicate whether a frequency is assigned to an
1071:
to either 0 or 1, any feasible solution to the integer program is a subset of vertices. The first constraint implies that at least one end point of every edge is included in this subset. Therefore, the solution describes a vertex cover. Additionally given some vertex cover C,
242:{\displaystyle {\begin{aligned}&{\underset {\mathbf {x} \in \mathbb {Z} ^{n}}{\text{maximize}}}&&\mathbf {c} ^{\mathrm {T} }\mathbf {x} \\&{\text{subject to}}&&A\mathbf {x} \leq \mathbf {b} ,\\&&&\mathbf {x} \geq \mathbf {0} \end{aligned}}}
570:
1453:
2505:{\displaystyle {\begin{aligned}&\Rightarrow B^{-1}=\pm B^{\mathrm {adj} }{\text{ is integral.}}\\&\Rightarrow \mathbf {x} _{0}=B^{-1}b{\text{ is integral.}}\\&\Rightarrow {\text{Every basic feasible solution is integral.}}\end{aligned}}}
887:
5108:
KouteckĂ˝, Martin; Levin, Asaf; Onn, Shmuel (2018). "A parameterized strongly polynomial algorithm for block structured integer programs". In
Chatzigiannakis, Ioannis; Kaklamanis, Christos; Marx, Dániel; Sannella, Donald (eds.).
2297:
1518:
many cases, the capacities are constrained to be integer quantities. Usually there are, depending on the technology used, additional restrictions that can be modeled as linear inequalities with integer or binary variables.
479:
3241:
732:
without the integrality constraint. The goal of the optimization is to move the black dashed line as far upward while still touching the polyhedron. The optimal solutions of the integer problem are the points
3335:
721:{\displaystyle {\begin{aligned}{\underset {x,y\in \mathbb {Z} }{\text{maximize}}}\quad &y\\{\text{subject to}}\quad &-x+y\leq 1\\&3x+2y\leq 12\\&2x+3y\leq 12\\&x,y\geq 0\end{aligned}}}
1626:
3428:
1509:
boundaries, and socio-economic homogeneity. Some applications for this type of problem include: political districting, school districting, health services districting and waste management districting.
3067:
1581:
of the ILP), and then round the entries of the solution to the LP relaxation. But, not only may this solution not be optimal, it may not even be feasible; that is, it may violate some constraint.
3146:
1317:
2386:
2204:
892:
575:
263:
128:
2695:
2009:
520:
1309:
3509:
5506:
1806:
1659:
2332:
1907:
1034:{\displaystyle {\begin{aligned}\min \sum _{v\in V}y_{v}\\y_{v}+y_{u}&\geq 1&&\forall uv\in E\\y_{v}&\in \mathbb {Z^{+}} &&\forall v\in V\end{aligned}}}
3601:
2982:. In the latter case, the problem is reduced to a bounded number of lower-dimensional problems. The run-time complexity of the algorithm has been improved in several steps:
2134:
1264:
3556:
2945:
2744:
2662:
2632:
1929:
1773:
1751:
1701:
546:
115:
4091:
2564:, which work by solving the LP relaxation and then adding linear constraints that drive the solution towards being integer without excluding any integer feasible points.
1149:
5377:
826:
3785:
has a row where both columns have nonzero entries. Equivalently, the vertices correspond to variables, and two variables form an edge if they share an inequality. The
1478:
These considerations occur frequently in practice and so integer linear programming can be used in many applications areas, some of which are briefly described below.
5501:
879:
1123:
3628:
2972:
2811:
1218:
1176:
1097:
1069:
794:
762:
4171:
4151:
4131:
4111:
4046:
4026:
4006:
3986:
3958:
3938:
3918:
3894:
3874:
3850:
3826:
3806:
3783:
3763:
3743:
3709:
2905:
2885:
2860:
2835:
2722:
2602:
2558:
2530:
2376:
2356:
2154:
2092:
2072:
2052:
2032:
1969:
1949:
1721:
1679:
2532:
of an ILP is totally unimodular, rather than use an ILP algorithm, the simplex method can be used to solve the LP relaxation and the solution will be integer.
68:. In particular, the special case of 0–1 integer linear programming, in which unknowns are binary, and only the restrictions must be satisfied, is one of
2209:
2921:). In the general case, where each variable can be an arbitrary integer, complete enumeration is impossible. Here, Lenstra's algorithm uses ideas from
1486:
Mixed-integer programming has many applications in industrial productions, including job-shop modelling. One important example happens in agricultural
424:
4308:
2560:
is not totally unimodular, there are a variety of algorithms that can be used to solve integer linear programs exactly. One class of algorithms are
5515:
5995:
4731:
Proceedings of the AMS Special
Session on Algebraic and Geometric Methods in Applied Discrete Mathematics held in San Antonio, TX, January 11, 2015
1230:) involves problems in which the variables are restricted to be either 0 or 1. Any bounded integer variable can be expressed as a combination of
5370:
5323:
5304:
5285:
5258:
5239:
5220:
5201:
5182:
5160:
4992:
4955:
4341:
4235:
2910:
In the special case of 0-1 ILP, Lenstra's algorithm is equivalent to complete enumeration: the number of all possible solutions is fixed (2
6097:
6076:
5538:
3154:
5590:
5451:
3667:
5558:
3251:
4756:
4523:
4362:
828:
with objective value of 2.8. If the solution of the relaxation is rounded to the nearest integers, it is not feasible for the ILP.
69:
3438:(MILP) - programs in which some variables are integer and some variables are real. The original algorithm of Lenstra has run-time
1592:
5669:
5363:
3345:
4506:
Schouwenaars, T.; Valenti, M.; Feron, E.; How, J. (2005). "Implementation and Flight Test
Results of MILP-based UAV Guidance".
39:
2989:
5946:
5608:
4596:
Bast, Hannah; Brosi, Patrick; Storandt, Sabine (2017-10-05). "Efficient
Generation of Geographically Accurate Transit Maps".
4291:
2925:. It transforms the original problem into an equivalent one with the following property: either the existence of a solution
6102:
6054:
5674:
5111:
45th
International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9–13, 2018, Prague, Czech Republic
3075:
1578:
5990:
5958:
2159:
1471:
3960:
be the number of variables of the integer program. Then it was shown in 2018 that integer programming can be solved in
1467:
The integer variables represent quantities that can only be integer. For example, it is not possible to build 3.7 cars.
6039:
5664:
3679:
2864:
5985:
5941:
5543:
4733:. Contemporary Mathematics. Vol. 685. Providence, Rhode Island: American Mathematical Society. pp. 55–95.
2667:
1974:
5834:
5563:
484:
58:
5724:
1269:
5386:
4182:
3965:
3441:
2838:
35:
5909:
2750:(the number of variables) is a fixed constant, then the feasibility problem can be solved in time polynomial in
1778:
1631:
1151:
thus giving us a feasible solution to the integer program. Thus we can conclude that if we minimize the sum of
548:) and replacing variables that are not sign-constrained with the difference of two sign-constrained variables.
5771:
4549:"Flight formation of UAVs in presence of moving obstacles using fast-dynamic mixed integer linear programming"
4396:"Optimal scheduling of a renewable micro-grid in an isolated load area using mixed-integer linear programming"
1589:
While in general the solution to LP relaxation will not be guaranteed to be integral, if the ILP has the form
1448:{\displaystyle x=x_{1}+2x_{2}+4x_{3}+\cdots +2^{\lfloor \log _{2}U\rfloor }x_{\lfloor \log _{2}U\rfloor +1}.}
5953:
5852:
5568:
1551:
5446:
6044:
6029:
5919:
5797:
5423:
5390:
5273:
4682:
4315:
4275:
2775:
5933:
5899:
5802:
5744:
5625:
5431:
5411:
4251:
2302:
1811:
3642:, many problem instances are intractable and so heuristic methods must be used instead. For example,
2638:-by-1 integer vector. We focus on the feasibility problem, which is to decide whether there exists an
5980:
5807:
5719:
4944:"Complexity of efficient and envy-free resource allocation: few agents, resources, or utility levels"
4722:
4560:
4464:
4452:
4407:
4395:
4187:
3721:, which is the case in many applications. The sparsity of the matrix can be measured as follows. The
2783:
2561:
5355:
4687:
3561:
6049:
5914:
5857:
5709:
5697:
5510:
5493:
5398:
5170:
4358:
3961:
3659:
2922:
2779:
2101:
1487:
1463:
There are two main reasons for using integer variables when modeling problems as a linear program:
1237:
3518:
2928:
2727:
2645:
2615:
1912:
1756:
1734:
1684:
556:
529:
98:
5784:
5753:
5739:
5729:
5520:
5114:
5113:. LIPIcs. Vol. 107. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. pp. 85:1–85:14.
5090:
4998:
4920:
4873:
4836:
4809:
4734:
4726:
4646:
4597:
4529:
4488:
4051:
1128:
54:
49:
5436:
4380:
4781:
3515:
is the binary encoding size of the problem. Using techniques from later algorithms, the factor
799:
5792:
5470:
5319:
5300:
5281:
5254:
5235:
5216:
5197:
5178:
5156:
4988:
4951:
4912:
4865:
4801:
4752:
4700:
4670:
4638:
4578:
4519:
4480:
4433:
4337:
4287:
4279:
4231:
2095:
1728:
1727:, then every basic feasible solution is integral. Consequently, the solution returned by the
1724:
1540:
523:
846:
5872:
5862:
5766:
5643:
5548:
5530:
5483:
5394:
5269:
5148:
5124:
5082:
5016:
4980:
4939:
4904:
4855:
4845:
4793:
4744:
4692:
4630:
4568:
4511:
4472:
4423:
4415:
4223:
4212:
3672:
2568:
1102:
4766:
3606:
3511:, where n is the number of integer variables, d is the number of continuous variables, and
2950:
2789:
1731:
is guaranteed to be integral. To show that every basic feasible solution is integral, let
1196:
1154:
1075:
1047:
767:
735:
5888:
5339:
4762:
4208:
2814:
2771:
2335:
1554:
17:
4948:
Proceedings of the Twenty-Fifth
International Joint Conference on Artificial Intelligence
4893:"An application of simultaneous diophantine approximation in combinatorial optimization"
4564:
4468:
4453:"Distributed energy resource system optimisation using mixed integer linear programming"
4411:
1220:, are constrained to be integers, while other variables are allowed to be non-integers.
5876:
5761:
5648:
5582:
5553:
5278:
50 Years of
Integer Programming 1958-2008: From the Early Years to the State-of-the-Art
5070:
4827:
4336:. International Series in Operations Research & Management Science. Vol. 130.
4156:
4136:
4116:
4096:
4031:
4011:
3991:
3971:
3943:
3923:
3903:
3879:
3859:
3835:
3811:
3791:
3768:
3748:
3728:
3694:
2890:
2870:
2845:
2820:
2707:
2587:
2572:
2543:
2515:
2361:
2341:
2139:
2077:
2057:
2037:
2017:
1954:
1934:
1706:
1664:
4971:
Bredereck, Robert; Kaczmarczyk, Andrzej; Knop, Dušan; Niedermeier, Rolf (2019-06-17).
6091:
6034:
6018:
5094:
5002:
4943:
4877:
3713:
3654:
2767:
1562:
1545:
95:. An integer linear program in canonical form is expressed thus (note that it is the
4973:"High-Multiplicity Fair Allocation: Lenstra Empowered by N-fold Integer Programming"
4924:
4533:
4492:
4394:
Morais, Hugo; Kádár, Péter; Faria, Pedro; Vale, Zita A.; Khodr, H. M. (2010-01-01).
5972:
5478:
4979:. EC '19. Phoenix, AZ, USA: Association for Computing Machinery. pp. 505–523.
3718:
2292:{\displaystyle B^{-1}={\frac {B^{\mathrm {adj} }}{\det(B)}}=\pm B^{\mathrm {adj} }}
837:
5046:
4813:
5129:
4419:
474:{\displaystyle \mathbf {c} \in \mathbb {R} ^{n},\mathbf {b} \in \mathbb {R} ^{m}}
6059:
5441:
4725:; SoberĂłn, Pablo (2017). "Helly's theorem: new variations and applications". In
4718:
4476:
4227:
3643:
1559:
1470:
The integer variables represent decisions (e.g. whether to include an edge in a
1231:
796:
that both have an objective value of 2. The unique optimum of the relaxation is
65:
4573:
4548:
4515:
3853:
3829:
2978:-th variable) belongs to an interval whose length is bounded by a function of
5017:"Integer Programming, Lattice Algorithms, and Deterministic Volume Estimation
4916:
4869:
4805:
4704:
4642:
4582:
4484:
4437:
4133:. Moreover, in contrast to the classical result of Lenstra, where the number
4984:
2813:
constraints is feasible; a method combining this result with algorithms for
3678:
There are also a variety of other problem-specific heuristics, such as the
4972:
4797:
2913:), and checking the feasibility of each solution can be done in time poly(
1909:
be the elements corresponding to the basis columns for the basic solution
5461:
4696:
4428:
4860:
5781:
5086:
4908:
4748:
4650:
4618:
3639:
522:
is a matrix. As with linear programs, ILPs not in standard form can be
75:
If some decision variables are not discrete, the problem is known as a
43:
5276:; Gerhard Reinelt; Giovanni Rinaldi; Laurence A. Wolsey, eds. (2009).
1573:
The naive way to solve an ILP is to simply remove the constraint that
4892:
2786:
asserts that an integer program is feasible whenever every subset of
4850:
4832:"Polynomiality for Bin Packing with a Constant Number of Item Types"
4831:
4634:
840:
to integer programming that will serve as the proof of NP-hardness.
5345:
5119:
5029:
4977:
Proceedings of the 2019 ACM Conference on
Economics and Computation
4739:
4602:
42:
program in which some or all of the variables are restricted to be
3236:{\displaystyle n^{2.5n}\cdot 2^{O(n)}\cdot (m\cdot \log V)^{O(1)}}
5350:
5030:"The Subspace Flatness Conjecture and Faster Integer Programming"
3342:
Reis and
Rothvoss presented an improved algorithm with run-time
4093:. In particular, the time is independent of the right-hand side
3151:
Frank and Tardos presented an improved algorithm with run-time
2817:
can be used to solve integer programs in time that is linear in
6016:
5832:
5695:
5623:
5409:
5359:
3330:{\displaystyle n^{n}\cdot 2^{O(n)}\cdot (m\cdot \log V)^{O(1)}}
4190: – Polynomial equation whose integer solutions are sought
1527:
1491:
program, but the variables must be constrained to be integer.
4619:"Production Sets with Indivisibilities, Part I: Generalities"
4363:"Designing telecommunication networks by integer programming"
57:
and the constraints (other than the integer constraints) are
5607:
4252:"Mixed-Integer Linear Programming (MILP): Model Formulation"
3650:
Other heuristic methods that can be applied to ILPs include
1621:{\displaystyle \max \mathbf {c} ^{\mathrm {T} }\mathbf {x} }
881:
be an undirected graph. Define a linear program as follows:
3423:{\displaystyle (\log n)^{O(n)}\cdot (m\cdot \log V)^{O(1)}}
1931:. By definition of a basis, there is some square submatrix
4950:. IJCAI'16. New York, New York, USA: AAAI Press: 102–108.
4451:
Omu, Akomeno; Choudhary, Ruchi; Boies, Adam (2013-10-01).
4218:. In R. E. Miller; J. W. Thatcher; J.D. Bohlinger (eds.).
526:
by eliminating inequalities, introducing slack variables (
27:
A mathematical optimization problem restricted to integers
4782:"Minkowski's Convex Body Theorem and Integer Programming"
1193:) involves problems in which only some of the variables,
5346:
Integer
Programming and Combinatorial Optimization, IPCO
3062:{\displaystyle 2^{O(n^{3})}\cdot (m\cdot \log V)^{O(1)}}
4671:"Integer Programming with a Fixed Number of Variables"
3920:
defined as the maximum absolute value of any entry of
3072:
Kannan presented an improved algorithm with run-time
4547:
Radmanesh, Mohammadreza; Kumar, Manish (2016-03-01).
4284:
Combinatorial optimization: algorithms and complexity
4159:
4139:
4119:
4099:
4054:
4034:
4014:
3994:
3974:
3946:
3926:
3906:
3882:
3862:
3838:
3814:
3794:
3771:
3751:
3731:
3697:
3683:
to optimal a solution returned by these methods are.
3609:
3564:
3521:
3444:
3348:
3254:
3248:
Dadush presented an improved algorithm with run-time
3157:
3078:
2992:
2953:
2931:
2893:
2873:
2848:
2823:
2792:
2730:
2710:
2704:
be the maximum absolute value of the coefficients in
2670:
2648:
2618:
2590:
2546:
2518:
2384:
2364:
2344:
2305:
2212:
2162:
2142:
2104:
2080:
2060:
2040:
2020:
1977:
1957:
1937:
1915:
1814:
1781:
1759:
1737:
1709:
1687:
1667:
1634:
1595:
1320:
1272:
1240:
1199:
1157:
1131:
1105:
1078:
1050:
890:
849:
802:
770:
738:
573:
532:
487:
427:
261:
126:
101:
5316:
Linear and Integer Optimization: Theory and Practice
3141:{\displaystyle n^{O(n)}\cdot (m\cdot \log V)^{O(1)}}
5971:
5932:
5898:
5887:
5845:
5780:
5752:
5738:
5708:
5657:
5636:
5581:
5529:
5492:
5469:
5460:
5422:
3717:. In particular, this occurs when the matrix has a
2199:{\displaystyle \mathbf {x} _{0}=B^{-1}\mathbf {b} }
1577:is integer, solve the corresponding LP (called the
564:The plot on the right shows the following problem.
5297:Applied Integer Programming: Modeling and Solution
5268:Michael JĂĽnger; Thomas M. Liebling; Denis Naddef;
4165:
4145:
4125:
4105:
4085:
4040:
4020:
4000:
3980:
3952:
3932:
3912:
3888:
3868:
3844:
3820:
3800:
3777:
3757:
3737:
3703:
3622:
3595:
3550:
3503:
3422:
3329:
3235:
3140:
3061:
2966:
2939:
2899:
2879:
2854:
2829:
2805:
2738:
2716:
2689:
2656:
2626:
2596:
2552:
2524:
2504:
2370:
2350:
2326:
2291:
2198:
2148:
2128:
2086:
2066:
2046:
2026:
2003:
1963:
1943:
1923:
1901:
1800:
1767:
1745:
1715:
1695:
1673:
1653:
1620:
1447:
1303:
1258:
1212:
1170:
1143:
1117:
1091:
1063:
1033:
873:
820:
788:
756:
720:
540:
514:
473:
410:
241:
109:
5295:Der-San Chen; Robert G. Batson; Yu Dang (2010).
2580:Exact algorithms for a small number of variables
2567:Another class of algorithms are variants of the
2250:
2105:
1753:be an arbitrary basic feasible solution . Since
1596:
895:
5351:The Aussois Combinatorial Optimization Workshop
2986:The original algorithm of Lenstra had run-time
2156:is nonsingular, it is invertible and therefore
5211:Dimitris Bertsimas; Robert Weismantel (2005).
4173:of variables is a variable part of the input.
2690:{\displaystyle A\mathbf {x} \leq \mathbf {b} }
2004:{\displaystyle B\mathbf {x} _{0}=\mathbf {b} }
1474:) and so should only take on the value 0 or 1.
5371:
5028:Reis, Victor; Rothvoss, Thomas (2023-03-26).
4153:of variables is a parameter, here the number
2074:is nonsingular, and therefore by assumption,
1178:we have also found the minimum vertex cover.
515:{\displaystyle A\in \mathbb {R} ^{m\times n}}
8:
4048:, integer programming can be solved in time
1971:with linearly independent columns such that
1431:
1412:
1402:
1383:
1304:{\displaystyle \lfloor \log _{2}U\rfloor +1}
1292:
1273:
252:and an ILP in standard form is expressed as
5051:Theoretical Computer Science Stack Exchange
4213:"Reducibility among Combinatorial Problems"
3504:{\displaystyle 2^{O(n^{3})}\cdot poly(d,L)}
6013:
5929:
5895:
5842:
5829:
5749:
5705:
5692:
5633:
5620:
5466:
5419:
5406:
5378:
5364:
5356:
2495:Every basic feasible solution is integral.
1801:{\displaystyle A\mathbf {x} =\mathbf {b} }
1654:{\displaystyle A\mathbf {x} =\mathbf {b} }
1234:. For example, given an integer variable,
836:The following is a reduction from minimum
5128:
5118:
5047:"FPT algorithm for mixed integer program"
4891:Frank, András; Tardos, Éva (1987-03-01).
4859:
4849:
4738:
4729:; Omar, Mohamed; Wright, Matthew (eds.).
4686:
4601:
4572:
4427:
4158:
4138:
4118:
4098:
4077:
4053:
4033:
4013:
3993:
3973:
3945:
3925:
3905:
3881:
3861:
3837:
3813:
3793:
3770:
3750:
3745:has vertices corresponding to columns of
3730:
3696:
3614:
3608:
3569:
3563:
3537:
3526:
3520:
3460:
3449:
3443:
3405:
3365:
3347:
3312:
3272:
3259:
3253:
3218:
3178:
3162:
3156:
3123:
3083:
3077:
3044:
3008:
2997:
2991:
2958:
2952:
2932:
2930:
2892:
2872:
2847:
2822:
2797:
2791:
2770:. The general case was solved in 1983 by
2731:
2729:
2709:
2682:
2674:
2669:
2649:
2647:
2619:
2617:
2589:
2545:
2517:
2493:
2478:
2466:
2453:
2448:
2432:
2419:
2418:
2399:
2385:
2383:
2363:
2343:
2311:
2310:
2304:
2276:
2275:
2236:
2235:
2229:
2217:
2211:
2191:
2182:
2169:
2164:
2161:
2141:
2103:
2079:
2059:
2039:
2019:
1996:
1987:
1982:
1976:
1956:
1936:
1916:
1914:
1888:
1883:
1862:
1857:
1842:
1837:
1821:
1816:
1813:
1793:
1785:
1780:
1760:
1758:
1738:
1736:
1708:
1688:
1686:
1666:
1646:
1638:
1633:
1613:
1606:
1605:
1600:
1594:
1419:
1411:
1390:
1382:
1363:
1347:
1331:
1319:
1280:
1271:
1239:
1204:
1198:
1162:
1156:
1130:
1104:
1083:
1077:
1055:
1049:
1006:
1005:
1002:
1000:
987:
945:
932:
918:
902:
891:
889:
848:
801:
769:
737:
614:
597:
596:
578:
574:
572:
533:
531:
500:
496:
495:
486:
465:
461:
460:
451:
442:
438:
437:
428:
426:
396:
388:
373:
365:
350:
342:
334:
323:
313:
306:
305:
300:
287:
283:
282:
273:
267:
262:
260:
230:
222:
207:
199:
188:
178:
171:
170:
165:
152:
148:
147:
138:
132:
127:
125:
102:
100:
5612:Optimization computes maxima and minima.
5232:Integer programming: theory and practice
5175:Theory of linear and integer programming
4008:. That is, for some computable function
555:
4200:
5153:Integer and combinatorial optimization
3434:These algorithms can also be used for
1266:, the variable can be expressed using
46:. In many settings the term refers to
5808:Principal pivoting algorithm of Lemke
5040:
5038:
4664:
4662:
4660:
4222:. New York: Plenum. pp. 85–103.
3691:It is often the case that the matrix
7:
5314:Gerard Sierksma; Yori Zwols (2015).
4938:Bliem, Bernhard; Bredereck, Robert;
3711:that defines the integer program is
3638:Since integer linear programming is
83:Canonical and standard form for ILPs
4220:Complexity of Computer Computations
87:In integer linear programming, the
5452:Successive parabolic interpolation
4786:Mathematics of Operations Research
4675:Mathematics of Operations Research
3765:, and two columns form an edge if
2426:
2423:
2420:
2327:{\displaystyle B^{\mathrm {adj} }}
2318:
2315:
2312:
2283:
2280:
2277:
2243:
2240:
2237:
1607:
1526:The task of frequency planning in
1015:
964:
307:
172:
25:
5772:Projective algorithm of Karmarkar
5340:A Tutorial on Integer Programming
5045:Hildebrand, Robert (2016-10-07).
4830:; Rothvoss, Thomas (2020-11-07).
3856:of the graph of the transpose of
1902:{\displaystyle \mathbf {x} _{0}=}
1044:Given that the constraints limit
5767:Ellipsoid algorithm of Khachiyan
5670:Sequential quadratic programming
5507:Broyden–Fletcher–Goldfarb–Shanno
4553:Aerospace Science and Technology
2933:
2732:
2683:
2675:
2650:
2620:
2449:
2192:
2165:
1997:
1983:
1917:
1817:
1794:
1786:
1761:
1739:
1689:
1647:
1639:
1614:
1601:
1187:Mixed-integer linear programming
534:
452:
429:
397:
389:
374:
366:
351:
343:
335:
314:
301:
274:
231:
223:
208:
200:
179:
166:
139:
117:vector which is to be decided):
103:
5073:(1989). "Tabu search-Part II".
4309:"Integer Programming Reduction"
2758:. This is trivial for the case
619:
604:
5725:Reduced gradient (Frank–Wolfe)
4508:2005 IEEE Aerospace Conference
4070:
4058:
3596:{\displaystyle 2^{O(n\log n)}}
3588:
3573:
3543:
3530:
3498:
3486:
3466:
3453:
3415:
3409:
3402:
3383:
3375:
3369:
3362:
3349:
3322:
3316:
3309:
3290:
3282:
3276:
3228:
3222:
3215:
3196:
3188:
3182:
3133:
3127:
3120:
3101:
3093:
3087:
3054:
3048:
3041:
3022:
3014:
3001:
2490:
2444:
2392:
2259:
2253:
2114:
2108:
1896:
1830:
868:
856:
815:
803:
783:
771:
751:
739:
560:IP polytope with LP relaxation
70:Karp's 21 NP-complete problems
1:
6055:Spiral optimization algorithm
5675:Successive linear programming
5251:Logic and Integer Programming
5151:; Laurence A. Wolsey (1988).
5015:Dadush, Daniel (2012-06-14).
4669:Lenstra, H. W. (1983-11-01).
4334:Logic and integer programming
3436:mixed integer linear programs
2129:{\displaystyle \det(B)=\pm 1}
2034:are linearly independent and
1703:have all integer entries and
1259:{\displaystyle 0\leq x\leq U}
5793:Simplex algorithm of Dantzig
5665:Augmented Lagrangian methods
5130:10.4230/LIPICS.ICALP.2018.85
4420:10.1016/j.renene.2009.02.031
3664:Reactive search optimization
3551:{\displaystyle 2^{O(n^{3})}}
2947:is obvious, or the value of
2940:{\displaystyle \mathbf {x} }
2739:{\displaystyle \mathbf {b} }
2657:{\displaystyle \mathbf {x} }
2627:{\displaystyle \mathbf {b} }
1924:{\displaystyle \mathbf {x} }
1768:{\displaystyle \mathbf {x} }
1746:{\displaystyle \mathbf {x} }
1696:{\displaystyle \mathbf {b} }
541:{\displaystyle \mathbf {s} }
110:{\displaystyle \mathbf {x} }
5192:Laurence A. Wolsey (1998).
4780:Kannan, Ravi (1987-08-01).
4477:10.1016/j.enpol.2013.05.009
4228:10.1007/978-1-4684-2001-2_9
4086:{\displaystyle f(a,d)n^{k}}
1513:Telecommunications networks
1224:Zero–one linear programming
1144:{\displaystyle v\not \in C}
6119:
6098:Combinatorial optimization
5213:Optimization over integers
4617:Scarf, Herbert E. (1981).
3687:Sparse integer programming
2571:method. For example, the
1775:is feasible, we know that
1228:binary integer programming
524:converted to standard form
18:Integer linear programming
6072:
6025:
6012:
5996:Push–relabel maximum flow
5841:
5828:
5798:Revised simplex algorithm
5704:
5691:
5632:
5619:
5605:
5418:
5405:
5249:H. Paul Williams (2009).
5075:ORSA Journal on Computing
4574:10.1016/j.ast.2015.12.021
4516:10.1109/AERO.2005.1559600
4183:Constrained least squares
3966:fixed-parameter tractable
2839:fixed-parameter tractable
2766:=2 was solved in 1981 by
2378:is integral. Therefore,
1585:Using total unimodularity
821:{\displaystyle (1.8,2.8)}
77:mixed-integer programming
36:mathematical optimization
5521:Symmetric rank-one (SR1)
5502:Berndt–Hall–Hall–Hausman
3673:Hopfield neural networks
2887:, with no dependence on
2358:and is integral because
1504:Territorial partitioning
1099:can be set to 1 for any
6045:Parallel metaheuristics
5853:Approximation algorithm
5564:Powell's dog leg method
5516:Davidon–Fletcher–Powell
5412:Unconstrained nonlinear
5299:. John Wiley and Sons.
5230:John K. Karlof (2006).
5177:. John Wiley and Sons.
4985:10.1145/3328526.3329649
4379:Sharma, Deepak (2010).
4332:Williams, H.P. (2009).
4113:and objective function
3668:Ant colony optimization
874:{\displaystyle G=(V,E)}
64:Integer programming is
6030:Evolutionary algorithm
5613:
5274:William R. Pulleyblank
4727:Harrington, Heather A.
4286:. Mineola, NY: Dover.
4167:
4147:
4127:
4107:
4087:
4042:
4022:
4002:
3982:
3968:time parameterized by
3954:
3934:
3914:
3890:
3870:
3846:
3828:is the minimum of the
3822:
3802:
3779:
3759:
3739:
3705:
3624:
3597:
3552:
3505:
3424:
3331:
3237:
3142:
3063:
2968:
2941:
2901:
2881:
2856:
2831:
2807:
2740:
2718:
2691:
2658:
2628:
2598:
2554:
2526:
2506:
2372:
2352:
2328:
2293:
2200:
2150:
2130:
2088:
2068:
2048:
2028:
2005:
1965:
1945:
1925:
1903:
1802:
1769:
1747:
1717:
1697:
1675:
1655:
1622:
1449:
1305:
1260:
1214:
1172:
1145:
1119:
1118:{\displaystyle v\in C}
1093:
1065:
1035:
875:
822:
790:
758:
722:
561:
542:
516:
475:
412:
243:
111:
5803:Criss-cross algorithm
5626:Constrained nonlinear
5611:
5432:Golden-section search
4798:10.1287/moor.12.3.415
4307:Erickson, J. (2015).
4168:
4148:
4128:
4108:
4088:
4043:
4023:
4003:
3983:
3955:
3935:
3915:
3891:
3871:
3847:
3823:
3803:
3780:
3760:
3740:
3706:
3625:
3623:{\displaystyle n^{n}}
3598:
3553:
3506:
3425:
3332:
3238:
3143:
3064:
2969:
2967:{\displaystyle x_{n}}
2942:
2902:
2882:
2857:
2832:
2808:
2806:{\displaystyle 2^{n}}
2774:, combining ideas by
2741:
2719:
2692:
2659:
2629:
2599:
2562:cutting plane methods
2555:
2527:
2507:
2373:
2353:
2329:
2294:
2201:
2151:
2131:
2089:
2069:
2049:
2029:
2014:Since the columns of
2006:
1966:
1946:
1926:
1904:
1803:
1770:
1748:
1718:
1698:
1676:
1656:
1623:
1450:
1306:
1261:
1215:
1213:{\displaystyle x_{i}}
1173:
1171:{\displaystyle y_{v}}
1146:
1120:
1094:
1092:{\displaystyle y_{v}}
1066:
1064:{\displaystyle y_{v}}
1036:
876:
823:
791:
789:{\displaystyle (2,2)}
759:
757:{\displaystyle (1,2)}
723:
559:
543:
517:
476:
413:
244:
112:
91:is distinct from the
6103:NP-complete problems
5720:Cutting-plane method
4697:10.1287/moor.8.4.538
4381:"Frequency Planning"
4276:Papadimitriou, C. H.
4188:Diophantine equation
4157:
4137:
4117:
4097:
4052:
4032:
4012:
3992:
3972:
3944:
3924:
3904:
3880:
3860:
3836:
3812:
3792:
3769:
3749:
3729:
3695:
3607:
3562:
3519:
3442:
3346:
3252:
3155:
3076:
2990:
2951:
2929:
2891:
2871:
2846:
2821:
2790:
2728:
2708:
2668:
2646:
2616:
2588:
2544:
2516:
2512:Thus, if the matrix
2382:
2362:
2342:
2303:
2210:
2160:
2140:
2102:
2078:
2058:
2038:
2018:
1975:
1955:
1935:
1913:
1812:
1779:
1757:
1735:
1707:
1685:
1665:
1632:
1593:
1318:
1270:
1238:
1197:
1155:
1129:
1103:
1076:
1048:
888:
847:
832:Proof of NP-hardness
800:
768:
736:
571:
530:
485:
425:
259:
124:
99:
53:(ILP), in which the
6050:Simulated annealing
5868:Integer programming
5858:Dynamic programming
5698:Convex optimization
5559:Levenberg–Marquardt
5194:Integer programming
5171:Alexander Schrijver
5149:George L. Nemhauser
4565:2016AeST...50..149R
4469:2013EnPol..61..249O
4412:2010REne...35..151M
3962:strongly polynomial
3660:Simulated annealing
3558:can be improved to
2923:Geometry of numbers
2780:Peter van Emde Boas
2612:integer matrix and
1488:production planning
1482:Production planning
32:integer programming
5730:Subgradient method
5614:
5539:Conjugate gradient
5447:Nelder–Mead method
5087:10.1287/ijoc.2.1.4
4909:10.1007/BF02579200
4837:Journal of the ACM
4828:Goemans, Michel X.
4723:De Loera, JesĂşs A.
4163:
4143:
4123:
4103:
4083:
4038:
4028:and some constant
4018:
3998:
3978:
3950:
3930:
3910:
3886:
3866:
3842:
3818:
3798:
3775:
3755:
3735:
3701:
3620:
3593:
3548:
3501:
3420:
3327:
3233:
3138:
3059:
2964:
2937:
2897:
2877:
2865:doubly exponential
2852:
2827:
2803:
2736:
2714:
2687:
2654:
2624:
2594:
2550:
2522:
2502:
2500:
2480: is integral.
2434: is integral.
2368:
2348:
2324:
2289:
2196:
2146:
2126:
2084:
2064:
2044:
2024:
2001:
1961:
1941:
1921:
1899:
1798:
1765:
1743:
1725:totally unimodular
1713:
1693:
1671:
1651:
1618:
1541:Cash flow matching
1535:Other applications
1445:
1311:binary variables:
1301:
1256:
1210:
1168:
1141:
1115:
1089:
1061:
1031:
1029:
913:
871:
818:
786:
754:
718:
716:
602:
562:
538:
512:
471:
408:
406:
294:
239:
237:
159:
107:
55:objective function
50:linear programming
6085:
6084:
6068:
6067:
6008:
6007:
6004:
6003:
5967:
5966:
5928:
5927:
5824:
5823:
5820:
5819:
5816:
5815:
5687:
5686:
5683:
5682:
5603:
5602:
5599:
5598:
5577:
5576:
5325:978-1-498-71016-9
5306:978-0-470-37306-4
5287:978-3-540-68274-5
5260:978-0-387-92279-9
5241:978-0-8493-1914-3
5222:978-0-9759146-2-5
5215:. Dynamic Ideas.
5203:978-0-471-28366-9
5184:978-0-471-98232-6
5162:978-0-471-82819-8
4994:978-1-4503-6792-9
4957:978-1-57735-770-4
4940:Niedermeier, Rolf
4844:(6): 38:1–38:21.
4510:. pp. 1–13.
4343:978-0-387-92280-5
4237:978-1-4684-2003-6
4166:{\displaystyle n}
4146:{\displaystyle n}
4126:{\displaystyle c}
4106:{\displaystyle b}
4041:{\displaystyle k}
4021:{\displaystyle f}
4001:{\displaystyle d}
3981:{\displaystyle a}
3953:{\displaystyle n}
3933:{\displaystyle A}
3913:{\displaystyle A}
3889:{\displaystyle a}
3869:{\displaystyle A}
3845:{\displaystyle A}
3821:{\displaystyle A}
3801:{\displaystyle d}
3778:{\displaystyle A}
3758:{\displaystyle A}
3738:{\displaystyle A}
3704:{\displaystyle A}
3634:Heuristic methods
2900:{\displaystyle V}
2880:{\displaystyle n}
2855:{\displaystyle n}
2830:{\displaystyle m}
2784:Doignon's theorem
2717:{\displaystyle A}
2597:{\displaystyle A}
2553:{\displaystyle A}
2525:{\displaystyle A}
2496:
2481:
2435:
2371:{\displaystyle B}
2351:{\displaystyle B}
2263:
2206:. By definition,
2149:{\displaystyle B}
2087:{\displaystyle B}
2067:{\displaystyle B}
2047:{\displaystyle B}
2027:{\displaystyle B}
1964:{\displaystyle A}
1944:{\displaystyle B}
1729:simplex algorithm
1716:{\displaystyle A}
1674:{\displaystyle A}
1522:Cellular networks
1125:and to 0 for any
898:
617:
582:
579:
326:
271:
268:
191:
136:
133:
16:(Redirected from
6110:
6014:
5930:
5896:
5873:Branch and bound
5863:Greedy algorithm
5843:
5830:
5750:
5706:
5693:
5634:
5621:
5569:Truncated Newton
5484:Wolfe conditions
5467:
5420:
5407:
5380:
5373:
5366:
5357:
5329:
5310:
5291:
5270:George Nemhauser
5264:
5245:
5226:
5207:
5188:
5166:
5135:
5134:
5132:
5122:
5105:
5099:
5098:
5067:
5061:
5060:
5058:
5057:
5042:
5033:
5026:
5020:
5013:
5007:
5006:
4968:
4962:
4961:
4935:
4929:
4928:
4888:
4882:
4881:
4863:
4853:
4824:
4818:
4817:
4777:
4771:
4770:
4749:10.1090/conm/685
4742:
4715:
4709:
4708:
4690:
4666:
4655:
4654:
4614:
4608:
4607:
4605:
4593:
4587:
4586:
4576:
4544:
4538:
4537:
4503:
4497:
4496:
4448:
4442:
4441:
4431:
4400:Renewable Energy
4391:
4385:
4384:
4376:
4370:
4369:
4367:
4357:Borndörfer, R.;
4354:
4348:
4347:
4329:
4323:
4322:
4320:
4314:. Archived from
4313:
4304:
4298:
4297:
4272:
4266:
4265:
4263:
4261:
4256:
4248:
4242:
4241:
4217:
4209:Karp, Richard M.
4205:
4172:
4170:
4169:
4164:
4152:
4150:
4149:
4144:
4132:
4130:
4129:
4124:
4112:
4110:
4109:
4104:
4092:
4090:
4089:
4084:
4082:
4081:
4047:
4045:
4044:
4039:
4027:
4025:
4024:
4019:
4007:
4005:
4004:
3999:
3987:
3985:
3984:
3979:
3959:
3957:
3956:
3951:
3939:
3937:
3936:
3931:
3919:
3917:
3916:
3911:
3895:
3893:
3892:
3887:
3875:
3873:
3872:
3867:
3851:
3849:
3848:
3843:
3832:of the graph of
3827:
3825:
3824:
3819:
3807:
3805:
3804:
3799:
3787:sparsity measure
3784:
3782:
3781:
3776:
3764:
3762:
3761:
3756:
3744:
3742:
3741:
3736:
3710:
3708:
3707:
3702:
3629:
3627:
3626:
3621:
3619:
3618:
3602:
3600:
3599:
3594:
3592:
3591:
3557:
3555:
3554:
3549:
3547:
3546:
3542:
3541:
3510:
3508:
3507:
3502:
3470:
3469:
3465:
3464:
3429:
3427:
3426:
3421:
3419:
3418:
3379:
3378:
3336:
3334:
3333:
3328:
3326:
3325:
3286:
3285:
3264:
3263:
3242:
3240:
3239:
3234:
3232:
3231:
3192:
3191:
3170:
3169:
3147:
3145:
3144:
3139:
3137:
3136:
3097:
3096:
3068:
3066:
3065:
3060:
3058:
3057:
3018:
3017:
3013:
3012:
2973:
2971:
2970:
2965:
2963:
2962:
2946:
2944:
2943:
2938:
2936:
2906:
2904:
2903:
2898:
2886:
2884:
2883:
2878:
2861:
2859:
2858:
2853:
2836:
2834:
2833:
2828:
2815:LP-type problems
2812:
2810:
2809:
2804:
2802:
2801:
2745:
2743:
2742:
2737:
2735:
2723:
2721:
2720:
2715:
2696:
2694:
2693:
2688:
2686:
2678:
2663:
2661:
2660:
2655:
2653:
2633:
2631:
2630:
2625:
2623:
2603:
2601:
2600:
2595:
2569:branch and bound
2559:
2557:
2556:
2551:
2540:When the matrix
2536:Exact algorithms
2531:
2529:
2528:
2523:
2511:
2509:
2508:
2503:
2501:
2497:
2494:
2486:
2482:
2479:
2474:
2473:
2458:
2457:
2452:
2440:
2436:
2433:
2431:
2430:
2429:
2407:
2406:
2388:
2377:
2375:
2374:
2369:
2357:
2355:
2354:
2349:
2333:
2331:
2330:
2325:
2323:
2322:
2321:
2298:
2296:
2295:
2290:
2288:
2287:
2286:
2264:
2262:
2248:
2247:
2246:
2230:
2225:
2224:
2205:
2203:
2202:
2197:
2195:
2190:
2189:
2174:
2173:
2168:
2155:
2153:
2152:
2147:
2135:
2133:
2132:
2127:
2093:
2091:
2090:
2085:
2073:
2071:
2070:
2065:
2053:
2051:
2050:
2045:
2033:
2031:
2030:
2025:
2010:
2008:
2007:
2002:
2000:
1992:
1991:
1986:
1970:
1968:
1967:
1962:
1950:
1948:
1947:
1942:
1930:
1928:
1927:
1922:
1920:
1908:
1906:
1905:
1900:
1895:
1894:
1893:
1892:
1869:
1868:
1867:
1866:
1849:
1848:
1847:
1846:
1826:
1825:
1820:
1807:
1805:
1804:
1799:
1797:
1789:
1774:
1772:
1771:
1766:
1764:
1752:
1750:
1749:
1744:
1742:
1722:
1720:
1719:
1714:
1702:
1700:
1699:
1694:
1692:
1680:
1678:
1677:
1672:
1660:
1658:
1657:
1652:
1650:
1642:
1627:
1625:
1624:
1619:
1617:
1612:
1611:
1610:
1604:
1454:
1452:
1451:
1446:
1441:
1440:
1424:
1423:
1406:
1405:
1395:
1394:
1368:
1367:
1352:
1351:
1336:
1335:
1310:
1308:
1307:
1302:
1285:
1284:
1265:
1263:
1262:
1257:
1232:binary variables
1219:
1217:
1216:
1211:
1209:
1208:
1177:
1175:
1174:
1169:
1167:
1166:
1150:
1148:
1147:
1142:
1124:
1122:
1121:
1116:
1098:
1096:
1095:
1090:
1088:
1087:
1070:
1068:
1067:
1062:
1060:
1059:
1040:
1038:
1037:
1032:
1030:
1013:
1011:
1010:
1009:
992:
991:
962:
950:
949:
937:
936:
923:
922:
912:
880:
878:
877:
872:
827:
825:
824:
819:
795:
793:
792:
787:
763:
761:
760:
755:
727:
725:
724:
719:
717:
697:
671:
645:
618:
615:
603:
601:
600:
580:
547:
545:
544:
539:
537:
521:
519:
518:
513:
511:
510:
499:
481:are vectors and
480:
478:
477:
472:
470:
469:
464:
455:
447:
446:
441:
432:
417:
415:
414:
409:
407:
400:
392:
386:
385:
384:
377:
369:
363:
362:
361:
354:
346:
338:
329:
327:
324:
321:
317:
312:
311:
310:
304:
297:
295:
293:
292:
291:
286:
277:
269:
265:
248:
246:
245:
240:
238:
234:
226:
220:
219:
218:
211:
203:
194:
192:
189:
186:
182:
177:
176:
175:
169:
162:
160:
158:
157:
156:
151:
142:
134:
130:
116:
114:
113:
108:
106:
21:
6118:
6117:
6113:
6112:
6111:
6109:
6108:
6107:
6088:
6087:
6086:
6081:
6064:
6021:
6000:
5963:
5924:
5901:
5890:
5883:
5837:
5812:
5776:
5743:
5734:
5711:
5700:
5679:
5653:
5649:Penalty methods
5644:Barrier methods
5628:
5615:
5595:
5591:Newton's method
5573:
5525:
5488:
5456:
5437:Powell's method
5414:
5401:
5384:
5336:
5326:
5313:
5307:
5294:
5288:
5267:
5261:
5248:
5242:
5229:
5223:
5210:
5204:
5191:
5185:
5169:
5163:
5147:
5144:
5142:Further reading
5139:
5138:
5107:
5106:
5102:
5069:
5068:
5064:
5055:
5053:
5044:
5043:
5036:
5027:
5023:
5014:
5010:
4995:
4970:
4969:
4965:
4958:
4937:
4936:
4932:
4890:
4889:
4885:
4851:10.1145/3421750
4826:
4825:
4821:
4779:
4778:
4774:
4759:
4717:
4716:
4712:
4688:10.1.1.431.5444
4668:
4667:
4658:
4635:10.2307/1911124
4616:
4615:
4611:
4595:
4594:
4590:
4546:
4545:
4541:
4526:
4505:
4504:
4500:
4450:
4449:
4445:
4393:
4392:
4388:
4378:
4377:
4373:
4365:
4356:
4355:
4351:
4344:
4331:
4330:
4326:
4321:on 18 May 2015.
4318:
4311:
4306:
4305:
4301:
4294:
4274:
4273:
4269:
4259:
4257:
4254:
4250:
4249:
4245:
4238:
4215:
4207:
4206:
4202:
4197:
4179:
4155:
4154:
4135:
4134:
4115:
4114:
4095:
4094:
4073:
4050:
4049:
4030:
4029:
4010:
4009:
3990:
3989:
3970:
3969:
3942:
3941:
3922:
3921:
3902:
3901:
3898:numeric measure
3878:
3877:
3858:
3857:
3834:
3833:
3810:
3809:
3790:
3789:
3767:
3766:
3747:
3746:
3727:
3726:
3719:block structure
3693:
3692:
3689:
3680:k-opt heuristic
3636:
3610:
3605:
3604:
3565:
3560:
3559:
3533:
3522:
3517:
3516:
3456:
3445:
3440:
3439:
3401:
3361:
3344:
3343:
3308:
3268:
3255:
3250:
3249:
3214:
3174:
3158:
3153:
3152:
3119:
3079:
3074:
3073:
3040:
3004:
2993:
2988:
2987:
2954:
2949:
2948:
2927:
2926:
2889:
2888:
2869:
2868:
2863:, but possibly
2844:
2843:
2819:
2818:
2793:
2788:
2787:
2772:Hendrik Lenstra
2726:
2725:
2706:
2705:
2666:
2665:
2644:
2643:
2614:
2613:
2586:
2585:
2582:
2542:
2541:
2538:
2514:
2513:
2499:
2498:
2484:
2483:
2462:
2447:
2438:
2437:
2414:
2395:
2380:
2379:
2360:
2359:
2340:
2339:
2306:
2301:
2300:
2271:
2249:
2231:
2213:
2208:
2207:
2178:
2163:
2158:
2157:
2138:
2137:
2100:
2099:
2076:
2075:
2056:
2055:
2036:
2035:
2016:
2015:
1981:
1973:
1972:
1953:
1952:
1933:
1932:
1911:
1910:
1884:
1879:
1858:
1853:
1838:
1833:
1815:
1810:
1809:
1777:
1776:
1755:
1754:
1733:
1732:
1705:
1704:
1683:
1682:
1663:
1662:
1630:
1629:
1599:
1591:
1590:
1587:
1571:
1537:
1524:
1515:
1506:
1497:
1484:
1461:
1415:
1407:
1386:
1378:
1359:
1343:
1327:
1316:
1315:
1276:
1268:
1267:
1236:
1235:
1200:
1195:
1194:
1184:
1158:
1153:
1152:
1127:
1126:
1101:
1100:
1079:
1074:
1073:
1051:
1046:
1045:
1028:
1027:
1012:
1001:
993:
983:
980:
979:
961:
951:
941:
928:
925:
924:
914:
886:
885:
845:
844:
834:
798:
797:
766:
765:
734:
733:
715:
714:
695:
694:
669:
668:
643:
642:
620:
611:
610:
605:
583:
569:
568:
554:
528:
527:
494:
483:
482:
459:
436:
423:
422:
405:
404:
382:
381:
359:
358:
328:
319:
318:
299:
296:
281:
272:
257:
256:
236:
235:
216:
215:
193:
184:
183:
164:
161:
146:
137:
122:
121:
97:
96:
85:
28:
23:
22:
15:
12:
11:
5:
6116:
6114:
6106:
6105:
6100:
6090:
6089:
6083:
6082:
6080:
6079:
6073:
6070:
6069:
6066:
6065:
6063:
6062:
6057:
6052:
6047:
6042:
6037:
6032:
6026:
6023:
6022:
6019:Metaheuristics
6017:
6010:
6009:
6006:
6005:
6002:
6001:
5999:
5998:
5993:
5991:Ford–Fulkerson
5988:
5983:
5977:
5975:
5969:
5968:
5965:
5964:
5962:
5961:
5959:Floyd–Warshall
5956:
5951:
5950:
5949:
5938:
5936:
5926:
5925:
5923:
5922:
5917:
5912:
5906:
5904:
5893:
5885:
5884:
5882:
5881:
5880:
5879:
5865:
5860:
5855:
5849:
5847:
5839:
5838:
5833:
5826:
5825:
5822:
5821:
5818:
5817:
5814:
5813:
5811:
5810:
5805:
5800:
5795:
5789:
5787:
5778:
5777:
5775:
5774:
5769:
5764:
5762:Affine scaling
5758:
5756:
5754:Interior point
5747:
5736:
5735:
5733:
5732:
5727:
5722:
5716:
5714:
5702:
5701:
5696:
5689:
5688:
5685:
5684:
5681:
5680:
5678:
5677:
5672:
5667:
5661:
5659:
5658:Differentiable
5655:
5654:
5652:
5651:
5646:
5640:
5638:
5630:
5629:
5624:
5617:
5616:
5606:
5604:
5601:
5600:
5597:
5596:
5594:
5593:
5587:
5585:
5579:
5578:
5575:
5574:
5572:
5571:
5566:
5561:
5556:
5551:
5546:
5541:
5535:
5533:
5527:
5526:
5524:
5523:
5518:
5513:
5504:
5498:
5496:
5490:
5489:
5487:
5486:
5481:
5475:
5473:
5464:
5458:
5457:
5455:
5454:
5449:
5444:
5439:
5434:
5428:
5426:
5416:
5415:
5410:
5403:
5402:
5385:
5383:
5382:
5375:
5368:
5360:
5354:
5353:
5348:
5342:
5335:
5334:External links
5332:
5331:
5330:
5324:
5311:
5305:
5292:
5286:
5265:
5259:
5246:
5240:
5227:
5221:
5208:
5202:
5189:
5183:
5167:
5161:
5143:
5140:
5137:
5136:
5100:
5062:
5034:
5021:
5008:
4993:
4963:
4956:
4942:(2016-07-09).
4930:
4883:
4819:
4792:(3): 415–440.
4772:
4757:
4710:
4681:(4): 538–548.
4656:
4609:
4588:
4539:
4524:
4498:
4443:
4406:(1): 151–156.
4386:
4371:
4349:
4342:
4324:
4299:
4292:
4267:
4243:
4236:
4199:
4198:
4196:
4193:
4192:
4191:
4185:
4178:
4175:
4162:
4142:
4122:
4102:
4080:
4076:
4072:
4069:
4066:
4063:
4060:
4057:
4037:
4017:
3997:
3977:
3949:
3929:
3909:
3885:
3865:
3841:
3817:
3797:
3774:
3754:
3734:
3700:
3688:
3685:
3676:
3675:
3670:
3665:
3662:
3657:
3635:
3632:
3617:
3613:
3590:
3587:
3584:
3581:
3578:
3575:
3572:
3568:
3545:
3540:
3536:
3532:
3529:
3525:
3500:
3497:
3494:
3491:
3488:
3485:
3482:
3479:
3476:
3473:
3468:
3463:
3459:
3455:
3452:
3448:
3432:
3431:
3417:
3414:
3411:
3408:
3404:
3400:
3397:
3394:
3391:
3388:
3385:
3382:
3377:
3374:
3371:
3368:
3364:
3360:
3357:
3354:
3351:
3339:
3338:
3324:
3321:
3318:
3315:
3311:
3307:
3304:
3301:
3298:
3295:
3292:
3289:
3284:
3281:
3278:
3275:
3271:
3267:
3262:
3258:
3245:
3244:
3230:
3227:
3224:
3221:
3217:
3213:
3210:
3207:
3204:
3201:
3198:
3195:
3190:
3187:
3184:
3181:
3177:
3173:
3168:
3165:
3161:
3149:
3135:
3132:
3129:
3126:
3122:
3118:
3115:
3112:
3109:
3106:
3103:
3100:
3095:
3092:
3089:
3086:
3082:
3070:
3056:
3053:
3050:
3047:
3043:
3039:
3036:
3033:
3030:
3027:
3024:
3021:
3016:
3011:
3007:
3003:
3000:
2996:
2961:
2957:
2935:
2896:
2876:
2851:
2826:
2800:
2796:
2734:
2713:
2685:
2681:
2677:
2673:
2652:
2622:
2593:
2581:
2578:
2573:branch and cut
2549:
2537:
2534:
2521:
2492:
2489:
2487:
2485:
2477:
2472:
2469:
2465:
2461:
2456:
2451:
2446:
2443:
2441:
2439:
2428:
2425:
2422:
2417:
2413:
2410:
2405:
2402:
2398:
2394:
2391:
2389:
2387:
2367:
2347:
2320:
2317:
2314:
2309:
2285:
2282:
2279:
2274:
2270:
2267:
2261:
2258:
2255:
2252:
2245:
2242:
2239:
2234:
2228:
2223:
2220:
2216:
2194:
2188:
2185:
2181:
2177:
2172:
2167:
2145:
2136:. Also, since
2125:
2122:
2119:
2116:
2113:
2110:
2107:
2083:
2063:
2043:
2023:
1999:
1995:
1990:
1985:
1980:
1960:
1940:
1919:
1898:
1891:
1887:
1882:
1878:
1875:
1872:
1865:
1861:
1856:
1852:
1845:
1841:
1836:
1832:
1829:
1824:
1819:
1796:
1792:
1788:
1784:
1763:
1741:
1712:
1691:
1670:
1649:
1645:
1641:
1637:
1616:
1609:
1603:
1598:
1586:
1583:
1570:
1567:
1566:
1565:
1557:
1549:
1543:
1536:
1533:
1523:
1520:
1514:
1511:
1505:
1502:
1496:
1493:
1483:
1480:
1476:
1475:
1468:
1460:
1457:
1456:
1455:
1444:
1439:
1436:
1433:
1430:
1427:
1422:
1418:
1414:
1410:
1404:
1401:
1398:
1393:
1389:
1385:
1381:
1377:
1374:
1371:
1366:
1362:
1358:
1355:
1350:
1346:
1342:
1339:
1334:
1330:
1326:
1323:
1300:
1297:
1294:
1291:
1288:
1283:
1279:
1275:
1255:
1252:
1249:
1246:
1243:
1207:
1203:
1183:
1180:
1165:
1161:
1140:
1137:
1134:
1114:
1111:
1108:
1086:
1082:
1058:
1054:
1042:
1041:
1026:
1023:
1020:
1017:
1014:
1008:
1004:
999:
996:
994:
990:
986:
982:
981:
978:
975:
972:
969:
966:
963:
960:
957:
954:
952:
948:
944:
940:
935:
931:
927:
926:
921:
917:
911:
908:
905:
901:
897:
894:
893:
870:
867:
864:
861:
858:
855:
852:
833:
830:
817:
814:
811:
808:
805:
785:
782:
779:
776:
773:
753:
750:
747:
744:
741:
729:
728:
713:
710:
707:
704:
701:
698:
696:
693:
690:
687:
684:
681:
678:
675:
672:
670:
667:
664:
661:
658:
655:
652:
649:
646:
644:
641:
638:
635:
632:
629:
626:
623:
621:
613:
612:
609:
606:
599:
595:
592:
589:
586:
577:
576:
553:
550:
536:
509:
506:
503:
498:
493:
490:
468:
463:
458:
454:
450:
445:
440:
435:
431:
419:
418:
403:
399:
395:
391:
387:
383:
380:
376:
372:
368:
364:
360:
357:
353:
349:
345:
341:
337:
333:
330:
322:
320:
316:
309:
303:
298:
290:
285:
280:
276:
266:
264:
250:
249:
233:
229:
225:
221:
217:
214:
210:
206:
202:
198:
195:
187:
185:
181:
174:
168:
163:
155:
150:
145:
141:
131:
129:
105:
89:canonical form
84:
81:
26:
24:
14:
13:
10:
9:
6:
4:
3:
2:
6115:
6104:
6101:
6099:
6096:
6095:
6093:
6078:
6075:
6074:
6071:
6061:
6058:
6056:
6053:
6051:
6048:
6046:
6043:
6041:
6038:
6036:
6035:Hill climbing
6033:
6031:
6028:
6027:
6024:
6020:
6015:
6011:
5997:
5994:
5992:
5989:
5987:
5984:
5982:
5979:
5978:
5976:
5974:
5973:Network flows
5970:
5960:
5957:
5955:
5952:
5948:
5945:
5944:
5943:
5940:
5939:
5937:
5935:
5934:Shortest path
5931:
5921:
5918:
5916:
5913:
5911:
5908:
5907:
5905:
5903:
5902:spanning tree
5897:
5894:
5892:
5886:
5878:
5874:
5871:
5870:
5869:
5866:
5864:
5861:
5859:
5856:
5854:
5851:
5850:
5848:
5844:
5840:
5836:
5835:Combinatorial
5831:
5827:
5809:
5806:
5804:
5801:
5799:
5796:
5794:
5791:
5790:
5788:
5786:
5783:
5779:
5773:
5770:
5768:
5765:
5763:
5760:
5759:
5757:
5755:
5751:
5748:
5746:
5741:
5737:
5731:
5728:
5726:
5723:
5721:
5718:
5717:
5715:
5713:
5707:
5703:
5699:
5694:
5690:
5676:
5673:
5671:
5668:
5666:
5663:
5662:
5660:
5656:
5650:
5647:
5645:
5642:
5641:
5639:
5635:
5631:
5627:
5622:
5618:
5610:
5592:
5589:
5588:
5586:
5584:
5580:
5570:
5567:
5565:
5562:
5560:
5557:
5555:
5552:
5550:
5547:
5545:
5542:
5540:
5537:
5536:
5534:
5532:
5531:Other methods
5528:
5522:
5519:
5517:
5514:
5512:
5508:
5505:
5503:
5500:
5499:
5497:
5495:
5491:
5485:
5482:
5480:
5477:
5476:
5474:
5472:
5468:
5465:
5463:
5459:
5453:
5450:
5448:
5445:
5443:
5440:
5438:
5435:
5433:
5430:
5429:
5427:
5425:
5421:
5417:
5413:
5408:
5404:
5400:
5396:
5392:
5388:
5381:
5376:
5374:
5369:
5367:
5362:
5361:
5358:
5352:
5349:
5347:
5343:
5341:
5338:
5337:
5333:
5327:
5321:
5318:. CRC Press.
5317:
5312:
5308:
5302:
5298:
5293:
5289:
5283:
5279:
5275:
5271:
5266:
5262:
5256:
5252:
5247:
5243:
5237:
5234:. CRC Press.
5233:
5228:
5224:
5218:
5214:
5209:
5205:
5199:
5195:
5190:
5186:
5180:
5176:
5172:
5168:
5164:
5158:
5154:
5150:
5146:
5145:
5141:
5131:
5126:
5121:
5116:
5112:
5104:
5101:
5096:
5092:
5088:
5084:
5080:
5076:
5072:
5066:
5063:
5052:
5048:
5041:
5039:
5035:
5031:
5025:
5022:
5018:
5012:
5009:
5004:
5000:
4996:
4990:
4986:
4982:
4978:
4974:
4967:
4964:
4959:
4953:
4949:
4945:
4941:
4934:
4931:
4926:
4922:
4918:
4914:
4910:
4906:
4902:
4898:
4897:Combinatorica
4894:
4887:
4884:
4879:
4875:
4871:
4867:
4862:
4857:
4852:
4847:
4843:
4839:
4838:
4833:
4829:
4823:
4820:
4815:
4811:
4807:
4803:
4799:
4795:
4791:
4787:
4783:
4776:
4773:
4768:
4764:
4760:
4758:9781470423216
4754:
4750:
4746:
4741:
4736:
4732:
4728:
4724:
4720:
4714:
4711:
4706:
4702:
4698:
4694:
4689:
4684:
4680:
4676:
4672:
4665:
4663:
4661:
4657:
4652:
4648:
4644:
4640:
4636:
4632:
4628:
4624:
4620:
4613:
4610:
4604:
4599:
4592:
4589:
4584:
4580:
4575:
4570:
4566:
4562:
4558:
4554:
4550:
4543:
4540:
4535:
4531:
4527:
4525:0-7803-8870-4
4521:
4517:
4513:
4509:
4502:
4499:
4494:
4490:
4486:
4482:
4478:
4474:
4470:
4466:
4462:
4458:
4457:Energy Policy
4454:
4447:
4444:
4439:
4435:
4430:
4429:10400.22/1585
4425:
4421:
4417:
4413:
4409:
4405:
4401:
4397:
4390:
4387:
4382:
4375:
4372:
4364:
4360:
4359:Grötschel, M.
4353:
4350:
4345:
4339:
4335:
4328:
4325:
4317:
4310:
4303:
4300:
4295:
4289:
4285:
4281:
4280:Steiglitz, K.
4277:
4271:
4268:
4253:
4247:
4244:
4239:
4233:
4229:
4225:
4221:
4214:
4210:
4204:
4201:
4194:
4189:
4186:
4184:
4181:
4180:
4176:
4174:
4160:
4140:
4120:
4100:
4078:
4074:
4067:
4064:
4061:
4055:
4035:
4015:
3995:
3975:
3967:
3963:
3947:
3927:
3907:
3899:
3883:
3863:
3855:
3839:
3831:
3815:
3795:
3788:
3772:
3752:
3732:
3724:
3720:
3716:
3715:
3698:
3686:
3684:
3681:
3674:
3671:
3669:
3666:
3663:
3661:
3658:
3656:
3655:Hill climbing
3653:
3652:
3651:
3648:
3645:
3641:
3633:
3631:
3615:
3611:
3585:
3582:
3579:
3576:
3570:
3566:
3538:
3534:
3527:
3523:
3514:
3495:
3492:
3489:
3483:
3480:
3477:
3474:
3471:
3461:
3457:
3450:
3446:
3437:
3412:
3406:
3398:
3395:
3392:
3389:
3386:
3380:
3372:
3366:
3358:
3355:
3352:
3341:
3340:
3319:
3313:
3305:
3302:
3299:
3296:
3293:
3287:
3279:
3273:
3269:
3265:
3260:
3256:
3247:
3246:
3225:
3219:
3211:
3208:
3205:
3202:
3199:
3193:
3185:
3179:
3175:
3171:
3166:
3163:
3159:
3150:
3130:
3124:
3116:
3113:
3110:
3107:
3104:
3098:
3090:
3084:
3080:
3071:
3051:
3045:
3037:
3034:
3031:
3028:
3025:
3019:
3009:
3005:
2998:
2994:
2985:
2984:
2983:
2981:
2977:
2959:
2955:
2924:
2920:
2916:
2912:
2908:
2894:
2874:
2866:
2862:
2849:
2840:
2824:
2816:
2798:
2794:
2785:
2781:
2777:
2776:László Lovász
2773:
2769:
2768:Herbert Scarf
2765:
2762:=1. The case
2761:
2757:
2753:
2749:
2711:
2703:
2698:
2679:
2671:
2642:-by-1 vector
2641:
2637:
2611:
2607:
2591:
2579:
2577:
2574:
2570:
2565:
2563:
2547:
2535:
2533:
2519:
2488:
2475:
2470:
2467:
2463:
2459:
2454:
2442:
2415:
2411:
2408:
2403:
2400:
2396:
2390:
2365:
2345:
2337:
2307:
2272:
2268:
2265:
2256:
2232:
2226:
2221:
2218:
2214:
2186:
2183:
2179:
2175:
2170:
2143:
2123:
2120:
2117:
2111:
2097:
2081:
2061:
2041:
2021:
2012:
1993:
1988:
1978:
1958:
1938:
1889:
1885:
1880:
1876:
1873:
1870:
1863:
1859:
1854:
1850:
1843:
1839:
1834:
1827:
1822:
1790:
1782:
1730:
1726:
1710:
1668:
1643:
1635:
1584:
1582:
1580:
1579:LP relaxation
1576:
1568:
1564:
1561:
1558:
1556:
1553:
1550:
1547:
1546:Energy system
1544:
1542:
1539:
1538:
1534:
1532:
1529:
1521:
1519:
1512:
1510:
1503:
1501:
1494:
1492:
1489:
1481:
1479:
1473:
1469:
1466:
1465:
1464:
1458:
1442:
1437:
1434:
1428:
1425:
1420:
1416:
1408:
1399:
1396:
1391:
1387:
1379:
1375:
1372:
1369:
1364:
1360:
1356:
1353:
1348:
1344:
1340:
1337:
1332:
1328:
1324:
1321:
1314:
1313:
1312:
1298:
1295:
1289:
1286:
1281:
1277:
1253:
1250:
1247:
1244:
1241:
1233:
1229:
1225:
1221:
1205:
1201:
1192:
1188:
1181:
1179:
1163:
1159:
1138:
1135:
1132:
1112:
1109:
1106:
1084:
1080:
1056:
1052:
1024:
1021:
1018:
997:
995:
988:
984:
976:
973:
970:
967:
958:
955:
953:
946:
942:
938:
933:
929:
919:
915:
909:
906:
903:
899:
884:
883:
882:
865:
862:
859:
853:
850:
841:
839:
831:
829:
812:
809:
806:
780:
777:
774:
748:
745:
742:
711:
708:
705:
702:
699:
691:
688:
685:
682:
679:
676:
673:
665:
662:
659:
656:
653:
650:
647:
639:
636:
633:
630:
627:
624:
622:
607:
593:
590:
587:
584:
567:
566:
565:
558:
551:
549:
525:
507:
504:
501:
491:
488:
466:
456:
448:
443:
433:
401:
393:
378:
370:
355:
347:
339:
331:
288:
278:
255:
254:
253:
227:
212:
204:
196:
153:
143:
120:
119:
118:
94:
93:standard form
90:
82:
80:
78:
73:
71:
67:
62:
60:
56:
52:
51:
45:
41:
37:
34:problem is a
33:
19:
6040:Local search
5986:Edmonds–Karp
5942:Bellman–Ford
5867:
5712:minimization
5544:Gauss–Newton
5494:Quasi–Newton
5479:Trust region
5387:Optimization
5315:
5296:
5280:. Springer.
5277:
5253:. Springer.
5250:
5231:
5212:
5193:
5174:
5152:
5110:
5103:
5078:
5074:
5065:
5054:. Retrieved
5050:
5024:
5011:
4976:
4966:
4947:
4933:
4903:(1): 49–65.
4900:
4896:
4886:
4861:1721.1/92865
4841:
4835:
4822:
4789:
4785:
4775:
4730:
4719:Amenta, Nina
4713:
4678:
4674:
4626:
4623:Econometrica
4622:
4612:
4591:
4556:
4552:
4542:
4507:
4501:
4460:
4456:
4446:
4403:
4399:
4389:
4374:
4352:
4333:
4327:
4316:the original
4302:
4283:
4270:
4258:. Retrieved
4246:
4219:
4203:
3897:
3786:
3722:
3712:
3690:
3677:
3649:
3637:
3512:
3435:
3433:
2979:
2975:
2918:
2914:
2911:
2909:
2842:
2763:
2759:
2755:
2751:
2747:
2701:
2699:
2639:
2635:
2609:
2605:
2583:
2566:
2539:
2334:denotes the
2013:
1588:
1574:
1572:
1548:optimization
1525:
1516:
1507:
1498:
1485:
1477:
1462:
1459:Applications
1227:
1223:
1222:
1190:
1186:
1185:
1043:
842:
838:vertex cover
835:
730:
563:
420:
251:
92:
88:
86:
76:
74:
63:
47:
31:
29:
6060:Tabu search
5471:Convergence
5442:Line search
5344:Conference
5081:(3): 4–32.
4629:(1): 1–32.
4559:: 149–160.
4463:: 249–266.
3644:tabu search
2664:satisfying
2054:is square,
1560:Transit map
66:NP-complete
40:feasibility
6092:Categories
5891:algorithms
5399:heuristics
5391:Algorithms
5120:1802.05859
5071:Glover, F.
5056:2024-05-21
4740:1508.07606
4603:1710.02226
4293:0486402584
4195:References
3854:tree-depth
3830:tree-depth
2096:unimodular
1628:such that
1569:Algorithms
1495:Scheduling
616:subject to
325:subject to
190:subject to
5846:Paradigms
5745:quadratic
5462:Gradients
5424:Functions
5196:. Wiley.
5155:. Wiley.
5095:207225435
5003:195298520
4917:1439-6912
4878:227154747
4870:0004-5411
4806:0364-765X
4705:0364-765X
4683:CiteSeerX
4643:0012-9682
4583:1270-9638
4485:0301-4215
4438:0960-1481
3583:
3472:⋅
3396:
3390:⋅
3381:⋅
3356:
3303:
3297:⋅
3288:⋅
3266:⋅
3209:
3203:⋅
3194:⋅
3172:⋅
3114:
3108:⋅
3099:⋅
3035:
3029:⋅
3020:⋅
2841:(FPT) in
2680:≤
2491:⇒
2468:−
2445:⇒
2412:±
2401:−
2393:⇒
2269:±
2219:−
2184:−
2121:±
1874:⋯
1563:layouting
1531:antenna.
1432:⌋
1426:
1413:⌊
1403:⌋
1397:
1384:⌊
1373:⋯
1293:⌋
1287:
1274:⌊
1251:≤
1245:≤
1110:∈
1022:∈
1016:∀
998:∈
974:∈
965:∀
956:≥
907:∈
900:∑
709:≥
689:≤
663:≤
637:≤
625:−
594:∈
505:×
492:∈
457:∈
434:∈
394:≥
371:≥
279:∈
228:≥
205:≤
144:∈
79:problem.
6077:Software
5954:Dijkstra
5785:exchange
5583:Hessians
5549:Gradient
5173:(1998).
4925:45585308
4534:13447718
4493:29369795
4361:(2012).
4282:(1998).
4260:16 April
4211:(1972).
4177:See also
3852:and the
2754:and log
2584:Suppose
2336:adjugate
1555:guidance
1182:Variants
1136:∉
581:maximize
270:maximize
135:maximize
48:integer
44:integers
5920:Kruskal
5910:BorĹŻvka
5900:Minimum
5637:General
5395:methods
4767:3625571
4651:1911124
4561:Bibcode
4465:Bibcode
4408:Bibcode
3896:be the
3640:NP-hard
2299:. Here
2098:and so
552:Example
5782:Basis-
5740:Linear
5710:Convex
5554:Mirror
5511:L-BFGS
5397:, and
5322:
5303:
5284:
5257:
5238:
5219:
5200:
5181:
5159:
5093:
5001:
4991:
4954:
4923:
4915:
4876:
4868:
4814:495512
4812:
4804:
4765:
4755:
4703:
4685:
4649:
4641:
4581:
4532:
4522:
4491:
4483:
4436:
4340:
4290:
4234:
3940:. Let
3876:. Let
3714:sparse
3603:or to
2917:, log
2634:is an
2604:is an
1808:. Let
1661:where
421:where
59:linear
5981:Dinic
5889:Graph
5115:arXiv
5091:S2CID
4999:S2CID
4921:S2CID
4874:S2CID
4810:S2CID
4735:arXiv
4647:JSTOR
4598:arXiv
4530:S2CID
4489:S2CID
4366:(PDF)
4319:(PDF)
4312:(PDF)
4255:(PDF)
4216:(PDF)
3723:graph
2974:(the
2746:. If
1472:graph
5947:SPFA
5915:Prim
5509:and
5320:ISBN
5301:ISBN
5282:ISBN
5255:ISBN
5236:ISBN
5217:ISBN
5198:ISBN
5179:ISBN
5157:ISBN
4989:ISBN
4952:ISBN
4913:ISSN
4866:ISSN
4802:ISSN
4753:ISBN
4701:ISSN
4639:ISSN
4579:ISSN
4520:ISBN
4481:ISSN
4434:ISSN
4338:ISBN
4288:ISBN
4262:2018
4232:ISBN
3988:and
3964:and
2837:and
2778:and
2724:and
2700:Let
2608:-by-
1681:and
1226:(or
1191:MILP
843:Let
764:and
5877:cut
5742:and
5125:doi
5083:doi
4981:doi
4905:doi
4856:hdl
4846:doi
4794:doi
4745:doi
4693:doi
4631:doi
4569:doi
4512:doi
4473:doi
4424:hdl
4416:doi
4224:doi
3900:of
3808:of
3725:of
3580:log
3393:log
3353:log
3300:log
3206:log
3164:2.5
3111:log
3032:log
2867:in
2338:of
2251:det
2106:det
2094:is
1951:of
1723:is
1597:max
1552:UAV
1528:GSM
1417:log
1388:log
1278:log
896:min
813:2.8
807:1.8
38:or
30:An
6094::
5393:,
5389::
5272:;
5123:.
5089:.
5077:.
5049:.
5037:^
5032:.
4997:.
4987:.
4975:.
4946:.
4919:.
4911:.
4899:.
4895:.
4872:.
4864:.
4854:.
4842:67
4840:.
4834:.
4808:.
4800:.
4790:12
4788:.
4784:.
4763:MR
4761:.
4751:.
4743:.
4721:;
4699:.
4691:.
4677:.
4673:.
4659:^
4645:.
4637:.
4627:49
4625:.
4621:.
4577:.
4567:.
4557:50
4555:.
4551:.
4528:.
4518:.
4487:.
4479:.
4471:.
4461:61
4459:.
4455:.
4432:.
4422:.
4414:.
4404:35
4402:.
4398:.
4278:;
4230:.
3630:.
2907:.
2782:.
2697:.
2011:.
692:12
666:12
72:.
61:.
5875:/
5379:e
5372:t
5365:v
5328:.
5309:.
5290:.
5263:.
5244:.
5225:.
5206:.
5187:.
5165:.
5133:.
5127::
5117::
5097:.
5085::
5079:1
5059:.
5019:.
5005:.
4983::
4960:.
4927:.
4907::
4901:7
4880:.
4858::
4848::
4816:.
4796::
4769:.
4747::
4737::
4707:.
4695::
4679:8
4653:.
4633::
4606:.
4600::
4585:.
4571::
4563::
4536:.
4514::
4495:.
4475::
4467::
4440:.
4426::
4418::
4410::
4383:.
4368:.
4346:.
4296:.
4264:.
4240:.
4226::
4161:n
4141:n
4121:c
4101:b
4079:k
4075:n
4071:)
4068:d
4065:,
4062:a
4059:(
4056:f
4036:k
4016:f
3996:d
3976:a
3948:n
3928:A
3908:A
3884:a
3864:A
3840:A
3816:A
3796:d
3773:A
3753:A
3733:A
3699:A
3616:n
3612:n
3589:)
3586:n
3577:n
3574:(
3571:O
3567:2
3544:)
3539:3
3535:n
3531:(
3528:O
3524:2
3513:L
3499:)
3496:L
3493:,
3490:d
3487:(
3484:y
3481:l
3478:o
3475:p
3467:)
3462:3
3458:n
3454:(
3451:O
3447:2
3430:.
3416:)
3413:1
3410:(
3407:O
3403:)
3399:V
3387:m
3384:(
3376:)
3373:n
3370:(
3367:O
3363:)
3359:n
3350:(
3337:.
3323:)
3320:1
3317:(
3314:O
3310:)
3306:V
3294:m
3291:(
3283:)
3280:n
3277:(
3274:O
3270:2
3261:n
3257:n
3243:.
3229:)
3226:1
3223:(
3220:O
3216:)
3212:V
3200:m
3197:(
3189:)
3186:n
3183:(
3180:O
3176:2
3167:n
3160:n
3148:.
3134:)
3131:1
3128:(
3125:O
3121:)
3117:V
3105:m
3102:(
3094:)
3091:n
3088:(
3085:O
3081:n
3069:.
3055:)
3052:1
3049:(
3046:O
3042:)
3038:V
3026:m
3023:(
3015:)
3010:3
3006:n
3002:(
2999:O
2995:2
2980:n
2976:n
2960:n
2956:x
2934:x
2919:V
2915:m
2895:V
2875:n
2850:n
2825:m
2799:n
2795:2
2764:n
2760:n
2756:V
2752:m
2748:n
2733:b
2712:A
2702:V
2684:b
2676:x
2672:A
2651:x
2640:n
2636:m
2621:b
2610:n
2606:m
2592:A
2548:A
2520:A
2476:b
2471:1
2464:B
2460:=
2455:0
2450:x
2427:j
2424:d
2421:a
2416:B
2409:=
2404:1
2397:B
2366:B
2346:B
2319:j
2316:d
2313:a
2308:B
2284:j
2281:d
2278:a
2273:B
2266:=
2260:)
2257:B
2254:(
2244:j
2241:d
2238:a
2233:B
2227:=
2222:1
2215:B
2193:b
2187:1
2180:B
2176:=
2171:0
2166:x
2144:B
2124:1
2118:=
2115:)
2112:B
2109:(
2082:B
2062:B
2042:B
2022:B
1998:b
1994:=
1989:0
1984:x
1979:B
1959:A
1939:B
1918:x
1897:]
1890:j
1886:n
1881:x
1877:,
1871:,
1864:2
1860:n
1855:x
1851:,
1844:1
1840:n
1835:x
1831:[
1828:=
1823:0
1818:x
1795:b
1791:=
1787:x
1783:A
1762:x
1740:x
1711:A
1690:b
1669:A
1648:b
1644:=
1640:x
1636:A
1615:x
1608:T
1602:c
1575:x
1443:.
1438:1
1435:+
1429:U
1421:2
1409:x
1400:U
1392:2
1380:2
1376:+
1370:+
1365:3
1361:x
1357:4
1354:+
1349:2
1345:x
1341:2
1338:+
1333:1
1329:x
1325:=
1322:x
1299:1
1296:+
1290:U
1282:2
1254:U
1248:x
1242:0
1206:i
1202:x
1189:(
1164:v
1160:y
1139:C
1133:v
1113:C
1107:v
1085:v
1081:y
1057:v
1053:y
1025:V
1019:v
1007:+
1003:Z
989:v
985:y
977:E
971:v
968:u
959:1
947:u
943:y
939:+
934:v
930:y
920:v
916:y
910:V
904:v
869:)
866:E
863:,
860:V
857:(
854:=
851:G
816:)
810:,
804:(
784:)
781:2
778:,
775:2
772:(
752:)
749:2
746:,
743:1
740:(
712:0
706:y
703:,
700:x
686:y
683:3
680:+
677:x
674:2
660:y
657:2
654:+
651:x
648:3
640:1
634:y
631:+
628:x
608:y
598:Z
591:y
588:,
585:x
535:s
508:n
502:m
497:R
489:A
467:m
462:R
453:b
449:,
444:n
439:R
430:c
402:,
398:0
390:x
379:,
375:0
367:s
356:,
352:b
348:=
344:s
340:+
336:x
332:A
315:x
308:T
302:c
289:n
284:Z
275:x
232:0
224:x
213:,
209:b
201:x
197:A
180:x
173:T
167:c
154:n
149:Z
140:x
104:x
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
