4305:
additional auxiliary rates used for the design of the scheme. Commonly, one aims to describe the fundamental limits of communication in terms of the problem's parameters only. This gives rise to the need of eliminating the aforementioned auxiliary rates, which is executed via
Fourier–Motzkin elimination. However, the elimination process results in a new system that possibly contains more inequalities than the original. Yet, often some of the inequalities in the reduced system are redundant. Redundancy may be implied by other inequalities or by
25:
5178:
2845:
1208:
1531:
2619:
1812:
2957:(or any sufficiently large negative number) would satisfy the reduced system, therefore there exist corresponding x and z for the larger systems as well, and there are infinitely many such solutions. E.g. setting y = -1000000, x = 0, z = -2222222 satisfies the original system as well as the reduced ones.
4304:
achievability proofs result in conditions under which the existence of a well-performing coding scheme is guaranteed. These conditions are often described by linear system of inequalities. The variables of the system include both the transmission rates (that are part of the problem's formulation) and
2432:
Since all the inequalities are in the same form (all less-than or all greater-than), we can examine the coefficient signs for each variable. Eliminating x would yield 2*2 = 4 inequalities on the remaining variables, and so would eliminating y. Eliminating z would yield only 3*1 = 3 inequalities so we
2956:
This system uses only 2 variables instead of 3. Examining the coefficient signs for each variable yields all-positive for y, so we can immediately say that the system is unbounded in y: since all y coefficients are positive and all inequalities are less-than-or-equal, setting y to negative infinity
4639:
is the number of random variables appearing in the involved information measures. Consequently, any STI can be proven via linear programming by checking if it is implied by the basic identities and non-negativity constraints. The described algorithm first performs
Fourier–Motzkin elimination to
185:
If all variables are eliminated from a system of linear inequalities, then one obtains a system of constant inequalities. It is then trivial to decide whether the resulting system is true or false. It is true if and only if the original system has solutions. As a consequence, elimination of all
2427:
2630:
4337:-th inequality is satisfied for any solution of all other inequalities, then it is redundant. Similarly, STIs refers to inequalities that are implied by the non-negativity of information theoretic measures and basic identities they satisfy. For instance, the STI
920:
1256:
2439:
2951:
3112:
Two "acceleration" theorems due to Imbert permit the elimination of redundant inequalities based solely on syntactic properties of the formula derivation tree, thus curtailing the need to solve linear programs or compute matrix ranks.
1543:
4163:
65:, is a useful starting point for translations, but translators must revise errors as necessary and confirm that the translation is accurate, rather than simply copy-pasting machine-translated text into the English Knowledge.
3397:
1974:
4313:
performs the elimination, while identifying and removing redundant inequalities. Consequently, the software's outputs a simplified system (without redundancies) that involves the communication rates only.
703:
452:
2262:
4514:
2840:{\displaystyle {\begin{cases}{\frac {7-x+5y}{2}}\leqslant {\frac {10-2x+5y}{4}}\\{\frac {7-x+5y}{2}}\leqslant {\frac {9-3x+6y}{3}}\\{\frac {7-x+5y}{2}}\leqslant {\frac {12+3x-2y}{6}}\\\end{cases}}}
784:
533:
3584:
1203:{\displaystyle \max(A_{1}(x_{1},\dots ,x_{r-1}),\dots ,A_{n_{A}}(x_{1},\dots ,x_{r-1}))\leq x_{r}\leq \min(B_{1}(x_{1},\dots ,x_{r-1}),\dots ,B_{n_{B}}(x_{1},\dots ,x_{r-1}))\wedge \phi }
4406:
4293:
This theorem provides a quick detection criterion and is used in practice to avoid more costly checks, such as those based on matrix ranks. See the reference for implementation details.
2157:
3688:
3098:
that the number of non-redundant constraints grows as a single exponential. A single exponential implementation of
Fourier-Motzkin elimination and complexity estimates are given in.
4617:
3504:
4751:. In: Boulier, F., England, M., Sadykov, T.M., Vorozhtsov, E.V. (eds) Computer Algebra in Scientific Computing. CASC 2020. Lecture Notes in Computer Science, vol 12291. Springer,]
4571:
1526:{\displaystyle \max(A_{1}(x_{1},\dots ,x_{r-1}),\dots ,A_{n_{A}}(x_{1},\dots ,x_{r-1}))\leq \min(B_{1}(x_{1},\dots ,x_{r-1}),\dots ,B_{n_{B}}(x_{1},\dots ,x_{r-1}))\wedge \phi }
330:
the variable to be eliminated. The linear inequalities in the system can be grouped into three classes depending on the sign (positive, negative or null) of the coefficient for
4261:
2052:
2013:
2614:{\displaystyle {\begin{cases}z\leqslant {\frac {10-2x+5y}{4}}\\z\leqslant {\frac {9-3x+6y}{3}}\\{\frac {7-x+5y}{2}}\leqslant z\\z\leqslant {\frac {12+3x-2y}{6}}\\\end{cases}}}
2211:
1248:
3089:
3243:
1852:
75:
3018:
2856:
2246:
3269:
1807:{\displaystyle \max(A_{1}(x_{1},\dots ,x_{r-1}),\dots ,A_{n_{A}}(x_{1},\dots ,x_{r-1}))\leq \min(B_{1}(x_{1},\dots ,x_{r-1}),\dots ,B_{n_{B}}(x_{1},\dots ,x_{r-1}))}
4288:
4007:
3966:
3938:
3891:
3856:
3827:
3780:
3753:
3718:
3635:
3451:
3424:
3144:
2082:
908:
888:
858:
831:
607:
580:
355:
328:
301:
274:
4640:
remove the auxiliary rates. Then, it imposes the information theoretic non-negativity constraints on the reduced output system and removes redundant inequalities.
4637:
4335:
4195:
4032:
4027:
3911:
3800:
3608:
3204:
3184:
3164:
3038:
2983:
804:
553:
247:
227:
207:
5075:
4946:
85:
Do not translate text that appears unreliable or low-quality. If possible, verify the text with references provided in the foreign-language article.
3274:
4168:
An inequality that does not satisfy these bounds is necessarily redundant, and can be removed from the system without changing its solution set.
1857:
4792:
Gattegno, Ido B.; Goldfeld, Ziv; Permuter, Haim H. (2015-09-25). "Fourier-Motzkin
Elimination Software for Information Theoretic Inequalities".
178:, from a system of relations (here linear inequalities) refers to the creation of another system of the same sort, but without the variables in
5070:
5666:
3091:, a double exponential complexity. This is due to the algorithm producing many redundant constraints implied by other constraints.
2422:{\displaystyle {\begin{cases}2x-5y+4z\leqslant 10\\3x-6y+3z\leqslant 9\\-x+5y-2z\leqslant -7\\-3x+2y+6z\leqslant 12\\\end{cases}}}
615:
364:
5564:
5084:
4939:
4828:
4777:
4702:
4411:
708:
457:
115:
5645:
5107:
4317:
Redundant constraint can be identified by solving a linear program as follows. Given a linear constraints system, if the
70:
3104:
is well-known to give solutions to inequality systems in polynomial time, favoring it over
Fourier-Motzkin elimination.
5159:
5020:
4306:
3512:
93:
5127:
4714:
4899:
106:
Content in this edit is translated from the existing German
Knowledge article at ]; see its history for attribution.
5671:
5238:
4932:
5177:
4340:
2087:
5515:
3640:
37:
5623:
5243:
148:
4580:
5559:
5527:
3456:
4519:
5608:
5233:
5554:
5510:
5403:
5132:
5112:
4200:
2018:
1979:
5322:
5293:
4955:
2162:
1217:
5478:
4924:
3043:
2865:
2639:
2448:
2271:
5340:
101:
4848:
5522:
5421:
5137:
4746:
3209:
2946:{\displaystyle {\begin{cases}5y\leqslant -4\\x+y\leqslant -1\\-6x+17y\leqslant -9\\\end{cases}}}
1820:
5613:
5598:
5488:
5366:
5015:
4992:
4959:
4843:
3866:
by accident. A variable is implicitly eliminated when it appears in at least one inequality of
5502:
5468:
5371:
5313:
5194:
5000:
4980:
2988:
2216:
122:
3248:
5549:
5376:
5288:
4266:
3985:
3944:
3916:
3869:
3834:
3805:
3758:
3731:
3696:
3613:
3429:
3402:
3122:
2060:
893:
866:
836:
809:
585:
558:
333:
306:
279:
252:
4858:
4158:{\displaystyle 1+|E_{i}|\ \leq \ |H_{i}|\ \leq 1+\left|E_{i}\cup (I_{i}\cap O_{k})\right|}
8:
5618:
5483:
5436:
5426:
5278:
5266:
5079:
5062:
4967:
4816:
4658:– the cylindrical algebraic decomposition algorithm performs quantifier elimination over
3095:
5353:
5308:
5298:
5089:
5005:
4881:
4793:
4622:
4320:
4301:
4180:
4012:
3896:
3785:
3593:
3189:
3169:
3149:
3101:
3023:
2968:
789:
538:
232:
212:
192:
186:
variables can be used to detect whether a system of inequalities has solutions or not.
5361:
5039:
4903:
4824:
4710:
4655:
97:
16:
Mathematical algorithm for eliminating variables from a system of linear inequalities
5441:
5431:
5335:
5212:
5117:
5099:
5052:
4963:
4912:, open-source code in MATLAB by Ido B. Gattegno, Ziv Goldfeld and Haim H. Permuter.
4873:
4649:
163:
4683:
5457:
5445:
5330:
5217:
5151:
5122:
4918:, open-source code in Python implementing the two Imbert acceleration theorems.
4731:
4679:
182:, such that both systems have the same solutions over the remaining variables.
159:
5660:
5603:
5587:
3392:{\displaystyle k:A_{i}(x_{1},\dots ,x_{r-1})\leq B_{j}(x_{1},\dots ,x_{r-1})}
2057:
We have therefore transformed the original system into another system where
5541:
5047:
1969:{\displaystyle A_{i}(x_{1},\dots ,x_{r-1})\leq B_{j}(x_{1},\dots ,x_{r-1})}
4915:
5628:
5010:
4574:
152:
4885:
4764:, Artificial Intelligence IV: Methodology, Systems, Applications, 1990.
104:
to the source of your translation. A model attribution edit summary is
4954:
4838:
Keßler, Christoph W. (1996). "Parallel
Fourier–Motzkin Elimination".
4309:(a.k.a. Shannon type inequalities). A recently developed open-source
144:
4877:
5030:
4798:
4909:
4310:
5350:
3972:
A non-redundant inequality has the property that its history is
3755:
is in the set as soon as at least one inequality in the history
62:
4171:
The second acceleration theorem detects minimal history sets:
3166:
as the set of indexes of inequalities from the initial system
4762:
About
Redundant Inequalities Generated by Fourier's Algorithm
698:{\displaystyle x_{r}\leq b_{i}-\sum _{k=1}^{r-1}a_{ik}x_{k}}
447:{\displaystyle x_{r}\geq b_{i}-\sum _{k=1}^{r-1}a_{ik}x_{k}}
4688:
Mémoires de l'Académie des sciences de l'Institut de France
2939:
2833:
2607:
2415:
74:
to this template: there are already 1,879 articles in the
1214:
Elimination consists in producing a system equivalent to
4791:
4509:{\displaystyle I(X_{1};X_{2})=H(X_{1})-H(X_{1}|X_{2})}
4859:"Fourier's Method of Linear Programming and its Dual"
4625:
4583:
4522:
4516:
and the non-negativity of conditional entropy, i.e.,
4414:
4343:
4323:
4296:
4269:
4203:
4183:
4035:
4015:
3988:
3947:
3919:
3899:
3872:
3837:
3808:
3788:
3761:
3734:
3699:
3643:
3616:
3596:
3515:
3459:
3432:
3405:
3277:
3251:
3212:
3192:
3172:
3152:
3125:
3046:
3026:
2991:
2971:
2859:
2633:
2442:
2265:
2219:
2165:
2090:
2063:
2021:
1982:
1860:
1823:
1546:
1259:
1220:
923:
896:
869:
839:
812:
792:
779:{\displaystyle x_{r}\leq B_{i}(x_{1},\dots ,x_{r-1})}
711:
618:
588:
561:
541:
528:{\displaystyle x_{r}\geq A_{i}(x_{1},\dots ,x_{r-1})}
460:
367:
336:
309:
282:
255:
235:
215:
195:
5467:
4749:
Complexity
Estimates for Fourier-Motzkin Elimination
4684:"Histoire de l'Académie, partie mathématique (1824)"
3271:
of the initial system. When adding a new inequality
58:
4631:
4611:
4565:
4508:
4400:
4329:
4282:
4255:
4189:
4157:
4021:
4001:
3960:
3932:
3905:
3885:
3850:
3821:
3794:
3774:
3747:
3712:
3682:
3629:
3602:
3578:
3498:
3445:
3418:
3391:
3263:
3237:
3198:
3178:
3158:
3138:
3083:
3032:
3012:
2977:
2945:
2839:
2613:
2421:
2240:
2205:
2151:
2076:
2046:
2007:
1968:
1846:
1806:
1525:
1242:
1202:
902:
882:
852:
825:
798:
778:
697:
601:
574:
547:
527:
446:
349:
322:
295:
268:
241:
221:
201:
3579:{\displaystyle O_{k}=\{x_{r},\ldots ,x_{r-k+1}\}}
3107:
3020:inequalities in the output, thus naively running
890:plays no role, grouped into a single conjunction
5658:
4733:Quantifier elimination by lazy model enumeration
1677:
1547:
1390:
1260:
1067:
924:
4700:
4175:Theorem (Imbert's second acceleration theorem).
2256:Consider the following system of inequalities:
2084:is eliminated. Note that the output system has
3980:Theorem (Imbert's first acceleration theorem).
100:accompanying your translation by providing an
49:Click for important translation instructions.
36:expand this article with text translated from
4940:
4745:RJ. Jing, M. Moreno-Maza, and D. Talaashrafi
112:{{Translated|de|Fourier-Motzkin-Elimination}}
5501:
3573:
3529:
3232:
3226:
2213:, then the number of output inequalities is
1250:. Obviously, this formula is equivalent to
4979:
4823:. John Wiley & sons. pp. 155–156.
4401:{\displaystyle I(X_{1};X_{2})\leq H(X_{1})}
174:The elimination of a set of variables, say
4947:
4933:
4707:Understanding and Using Linear Programming
2152:{\displaystyle (n-n_{A}-n_{B})+n_{A}n_{B}}
914:The original system is thus equivalent to
5193:
4847:
4815:
4797:
4772:
4770:
4736:, Computer aided verification (CAV) 2010.
4586:
3683:{\displaystyle E_{i}\cup I_{i}\cup R_{i}}
5181:Optimization computes maxima and minima.
4856:
4821:Theory of Linear and Integer Programming
612:those inequalities that are of the form
361:those inequalities that are of the form
5265:
4678:
3040:successive steps can result in at most
5659:
4837:
4767:
4612:{\displaystyle \mathbb {R} ^{2^{n}-1}}
5585:
5401:
5377:Principal pivoting algorithm of Lemke
5264:
5192:
4978:
4928:
4779:Fourier Elimination: Which to Choose?
4652:– can be proved using FM elimination.
4573:. Shannon-type inequalities define a
3499:{\displaystyle H_{k}=H_{i}\cup H_{j}}
4916:Symbolic Fourier-Motzkin elimination
4900:Chapter 1 of Undergraduate Convexity
4566:{\displaystyle H(X_{1}|X_{2})\geq 0}
3893:, but appears neither in inequality
162:who proposed the method in 1826 and
18:
5667:Optimization algorithms and methods
4910:FME software for Information theory
4694:
2985:inequalities can result in at most
860:is the number of such inequalities;
609:is the number of such inequalities;
13:
5586:
5176:
5021:Successive parabolic interpolation
4809:
4307:inequalities in information theory
4297:Applications in information theory
1221:
14:
5683:
5402:
5341:Projective algorithm of Karmarkar
4902:, textbook by Niels Lauritzen at
4893:
4408:is a consequence of the identity
4256:{\displaystyle 1+|E_{i}|=|H_{i}|}
2965:Running an elimination step over
2047:{\displaystyle 1\leq j\leq n_{B}}
2008:{\displaystyle 1\leq i\leq n_{A}}
147:for eliminating variables from a
5336:Ellipsoid algorithm of Khachiyan
5239:Sequential quadratic programming
5076:Broyden–Fletcher–Goldfarb–Shanno
4690:. Vol. 7. Gauthier-Villars.
3802:results from the elimination of
2624:which gives the 3 inequalities:
2159:inequalities. In particular, if
23:
2206:{\displaystyle n_{A}=n_{B}=n/2}
1243:{\displaystyle \exists x_{r}~S}
5294:Reduced gradient (Frank–Wolfe)
4785:
4754:
4739:
4724:
4672:
4662:inequalities, not just linear.
4554:
4540:
4526:
4503:
4489:
4475:
4466:
4453:
4444:
4418:
4395:
4382:
4373:
4347:
4249:
4234:
4226:
4211:
4147:
4121:
4087:
4072:
4058:
4043:
3386:
3348:
3332:
3294:
3108:Imbert's acceleration theorems
3084:{\displaystyle 4(n/4)^{2^{d}}}
3065:
3050:
2123:
2091:
1963:
1925:
1909:
1871:
1801:
1798:
1760:
1731:
1693:
1680:
1671:
1668:
1630:
1601:
1563:
1550:
1514:
1511:
1473:
1444:
1406:
1393:
1384:
1381:
1343:
1314:
1276:
1263:
1191:
1188:
1150:
1121:
1083:
1070:
1048:
1045:
1007:
978:
940:
927:
773:
735:
522:
484:
169:
166:who re-discovered it in 1936.
110:You may also add the template
1:
5624:Spiral optimization algorithm
5244:Successive linear programming
4866:American Mathematical Monthly
4666:
2960:
158:The algorithm is named after
149:system of linear inequalities
5362:Simplex algorithm of Dantzig
5234:Augmented Lagrangian methods
3590:eliminated. Each inequality
863:those inequalities in which
7:
4643:
3968:, all remaining variables.
3509:Suppose that the variables
3238:{\displaystyle H_{i}=\{i\}}
137:Fourier–Motzkin elimination
82:will aid in categorization.
10:
5688:
2251:
1847:{\displaystyle n_{A}n_{B}}
57:Machine translation, like
5641:
5594:
5581:
5565:Push–relabel maximum flow
5540:
5456:
5414:
5410:
5397:
5367:Revised simplex algorithm
5349:
5321:
5307:
5277:
5273:
5260:
5226:
5205:
5201:
5188:
5174:
5150:
5098:
5061:
5038:
5029:
4991:
4987:
4974:
38:the corresponding article
5090:Symmetric rank-one (SR1)
5071:Berndt–Hall–Hall–Hausman
4857:Williams, H. P. (1986).
5672:Real algebraic geometry
5614:Parallel metaheuristics
5422:Approximation algorithm
5133:Powell's dog leg method
5085:Davidon–Fletcher–Powell
4981:Unconstrained nonlinear
3728:on purpose. A variable
3013:{\displaystyle n^{2}/4}
2241:{\displaystyle n^{2}/4}
121:For more guidance, see
5599:Evolutionary algorithm
5182:
4633:
4613:
4567:
4510:
4402:
4331:
4284:
4257:
4191:
4159:
4023:
4003:
3962:
3934:
3907:
3887:
3852:
3823:
3796:
3776:
3749:
3722:effectively eliminated
3714:
3684:
3631:
3604:
3580:
3500:
3447:
3420:
3393:
3265:
3264:{\displaystyle i\in S}
3239:
3200:
3180:
3160:
3140:
3085:
3034:
3014:
2979:
2947:
2841:
2615:
2423:
2242:
2207:
2153:
2078:
2048:
2009:
1970:
1848:
1808:
1527:
1244:
1204:
904:
884:
854:
827:
800:
780:
699:
671:
603:
576:
549:
529:
448:
420:
351:
324:
297:
270:
243:
223:
203:
5372:Criss-cross algorithm
5195:Constrained nonlinear
5180:
5001:Golden-section search
4634:
4614:
4568:
4511:
4403:
4332:
4302:Information-theoretic
4285:
4283:{\displaystyle H_{i}}
4258:
4192:
4160:
4024:
4004:
4002:{\displaystyle H_{i}}
3963:
3961:{\displaystyle R_{i}}
3935:
3933:{\displaystyle E_{i}}
3908:
3888:
3886:{\displaystyle H_{i}}
3860:implicitly eliminated
3853:
3851:{\displaystyle I_{i}}
3824:
3822:{\displaystyle x_{j}}
3797:
3777:
3775:{\displaystyle H_{i}}
3750:
3748:{\displaystyle x_{j}}
3715:
3713:{\displaystyle E_{i}}
3685:
3632:
3630:{\displaystyle O_{k}}
3605:
3581:
3501:
3448:
3446:{\displaystyle H_{k}}
3421:
3419:{\displaystyle x_{r}}
3394:
3266:
3240:
3201:
3181:
3161:
3141:
3139:{\displaystyle H_{i}}
3086:
3035:
3015:
2980:
2948:
2842:
2616:
2424:
2243:
2208:
2154:
2079:
2077:{\displaystyle x_{r}}
2049:
2010:
1971:
1849:
1809:
1528:
1245:
1205:
905:
903:{\displaystyle \phi }
885:
883:{\displaystyle x_{r}}
855:
853:{\displaystyle n_{B}}
828:
826:{\displaystyle n_{B}}
801:
781:
700:
645:
604:
602:{\displaystyle n_{A}}
577:
575:{\displaystyle n_{A}}
550:
530:
449:
394:
352:
350:{\displaystyle x_{r}}
325:
323:{\displaystyle x_{r}}
298:
296:{\displaystyle x_{r}}
271:
269:{\displaystyle x_{1}}
244:
224:
204:
123:Knowledge:Translation
94:copyright attribution
5289:Cutting-plane method
4817:Schrijver, Alexander
4709:. Berlin: Springer.
4623:
4581:
4520:
4412:
4341:
4321:
4267:
4201:
4181:
4033:
4013:
3986:
3945:
3917:
3897:
3870:
3835:
3806:
3786:
3759:
3732:
3697:
3641:
3614:
3594:
3513:
3457:
3430:
3403:
3275:
3249:
3210:
3190:
3170:
3150:
3123:
3044:
3024:
2989:
2969:
2857:
2631:
2440:
2263:
2217:
2163:
2088:
2061:
2019:
1980:
1858:
1821:
1544:
1257:
1218:
921:
894:
867:
837:
810:
790:
709:
616:
586:
559:
539:
458:
365:
334:
307:
280:
253:
233:
213:
193:
143:, is a mathematical
139:, also known as the
5619:Simulated annealing
5437:Integer programming
5427:Dynamic programming
5267:Convex optimization
5128:Levenberg–Marquardt
4776:Jean-Louis Imbert,
4760:Jean-Louis Imbert,
4311:software for MATLAB
3610:partitions the set
3426:), the new history
3096:upper bound theorem
5299:Subgradient method
5183:
5108:Conjugate gradient
5016:Nelder–Mead method
4629:
4609:
4563:
4506:
4398:
4327:
4280:
4253:
4187:
4177:If the inequality
4155:
4019:
3999:
3958:
3930:
3903:
3883:
3848:
3819:
3792:
3772:
3745:
3710:
3680:
3627:
3600:
3576:
3496:
3453:is constructed as
3443:
3416:
3389:
3261:
3235:
3196:
3176:
3156:
3136:
3102:Linear programming
3081:
3030:
3010:
2975:
2943:
2938:
2837:
2832:
2611:
2606:
2433:use that instead.
2419:
2414:
2238:
2203:
2149:
2074:
2044:
2005:
1966:
1844:
1804:
1523:
1240:
1200:
900:
880:
850:
823:
806:ranging from 1 to
796:
776:
705:; denote these by
695:
599:
572:
555:ranging from 1 to
545:
525:
454:; denote these by
444:
347:
320:
293:
266:
239:
229:inequalities with
219:
199:
189:Consider a system
102:interlanguage link
5654:
5653:
5637:
5636:
5577:
5576:
5573:
5572:
5536:
5535:
5497:
5496:
5393:
5392:
5389:
5388:
5385:
5384:
5256:
5255:
5252:
5251:
5172:
5171:
5168:
5167:
5146:
5145:
4904:Aarhus University
4840:Universität Trier
4830:978-0-471-98232-6
4656:Real closed field
4632:{\displaystyle n}
4330:{\displaystyle i}
4190:{\displaystyle i}
4093:
4070:
4064:
4029:is minimal, then
4022:{\displaystyle i}
4009:of an inequality
3906:{\displaystyle i}
3795:{\displaystyle i}
3603:{\displaystyle i}
3245:for inequalities
3199:{\displaystyle i}
3179:{\displaystyle S}
3159:{\displaystyle i}
3146:of an inequality
3033:{\displaystyle d}
2978:{\displaystyle n}
2828:
2795:
2764:
2731:
2700:
2667:
2602:
2556:
2525:
2485:
1817:is equivalent to
1236:
799:{\displaystyle i}
548:{\displaystyle i}
242:{\displaystyle r}
222:{\displaystyle n}
202:{\displaystyle S}
134:
133:
50:
46:
5679:
5583:
5582:
5499:
5498:
5465:
5464:
5442:Branch and bound
5432:Greedy algorithm
5412:
5411:
5399:
5398:
5319:
5318:
5275:
5274:
5262:
5261:
5203:
5202:
5190:
5189:
5138:Truncated Newton
5053:Wolfe conditions
5036:
5035:
4989:
4988:
4976:
4975:
4949:
4942:
4935:
4926:
4925:
4889:
4863:
4853:
4851:
4834:
4804:
4803:
4801:
4789:
4783:
4774:
4765:
4758:
4752:
4743:
4737:
4730:David Monniaux,
4728:
4722:
4720:
4701:Gärtner, Bernd;
4698:
4692:
4691:
4676:
4638:
4636:
4635:
4630:
4618:
4616:
4615:
4610:
4608:
4607:
4600:
4599:
4589:
4572:
4570:
4569:
4564:
4553:
4552:
4543:
4538:
4537:
4515:
4513:
4512:
4507:
4502:
4501:
4492:
4487:
4486:
4465:
4464:
4443:
4442:
4430:
4429:
4407:
4405:
4404:
4399:
4394:
4393:
4372:
4371:
4359:
4358:
4336:
4334:
4333:
4328:
4289:
4287:
4286:
4281:
4279:
4278:
4262:
4260:
4259:
4254:
4252:
4247:
4246:
4237:
4229:
4224:
4223:
4214:
4196:
4194:
4193:
4188:
4164:
4162:
4161:
4156:
4154:
4150:
4146:
4145:
4133:
4132:
4117:
4116:
4091:
4090:
4085:
4084:
4075:
4068:
4062:
4061:
4056:
4055:
4046:
4028:
4026:
4025:
4020:
4008:
4006:
4005:
4000:
3998:
3997:
3967:
3965:
3964:
3959:
3957:
3956:
3939:
3937:
3936:
3931:
3929:
3928:
3912:
3910:
3909:
3904:
3892:
3890:
3889:
3884:
3882:
3881:
3857:
3855:
3854:
3849:
3847:
3846:
3828:
3826:
3825:
3820:
3818:
3817:
3801:
3799:
3798:
3793:
3781:
3779:
3778:
3773:
3771:
3770:
3754:
3752:
3751:
3746:
3744:
3743:
3719:
3717:
3716:
3711:
3709:
3708:
3689:
3687:
3686:
3681:
3679:
3678:
3666:
3665:
3653:
3652:
3636:
3634:
3633:
3628:
3626:
3625:
3609:
3607:
3606:
3601:
3585:
3583:
3582:
3577:
3572:
3571:
3541:
3540:
3525:
3524:
3505:
3503:
3502:
3497:
3495:
3494:
3482:
3481:
3469:
3468:
3452:
3450:
3449:
3444:
3442:
3441:
3425:
3423:
3422:
3417:
3415:
3414:
3399:(by eliminating
3398:
3396:
3395:
3390:
3385:
3384:
3360:
3359:
3347:
3346:
3331:
3330:
3306:
3305:
3293:
3292:
3270:
3268:
3267:
3262:
3244:
3242:
3241:
3236:
3222:
3221:
3205:
3203:
3202:
3197:
3186:used to produce
3185:
3183:
3182:
3177:
3165:
3163:
3162:
3157:
3145:
3143:
3142:
3137:
3135:
3134:
3090:
3088:
3087:
3082:
3080:
3079:
3078:
3077:
3060:
3039:
3037:
3036:
3031:
3019:
3017:
3016:
3011:
3006:
3001:
3000:
2984:
2982:
2981:
2976:
2952:
2950:
2949:
2944:
2942:
2941:
2846:
2844:
2843:
2838:
2836:
2835:
2829:
2824:
2801:
2796:
2791:
2771:
2765:
2760:
2737:
2732:
2727:
2707:
2701:
2696:
2673:
2668:
2663:
2643:
2620:
2618:
2617:
2612:
2610:
2609:
2603:
2598:
2575:
2557:
2552:
2532:
2526:
2521:
2498:
2486:
2481:
2458:
2428:
2426:
2425:
2420:
2418:
2417:
2247:
2245:
2244:
2239:
2234:
2229:
2228:
2212:
2210:
2209:
2204:
2199:
2188:
2187:
2175:
2174:
2158:
2156:
2155:
2150:
2148:
2147:
2138:
2137:
2122:
2121:
2109:
2108:
2083:
2081:
2080:
2075:
2073:
2072:
2053:
2051:
2050:
2045:
2043:
2042:
2014:
2012:
2011:
2006:
2004:
2003:
1975:
1973:
1972:
1967:
1962:
1961:
1937:
1936:
1924:
1923:
1908:
1907:
1883:
1882:
1870:
1869:
1853:
1851:
1850:
1845:
1843:
1842:
1833:
1832:
1813:
1811:
1810:
1805:
1797:
1796:
1772:
1771:
1759:
1758:
1757:
1756:
1730:
1729:
1705:
1704:
1692:
1691:
1667:
1666:
1642:
1641:
1629:
1628:
1627:
1626:
1600:
1599:
1575:
1574:
1562:
1561:
1537:The inequality
1532:
1530:
1529:
1524:
1510:
1509:
1485:
1484:
1472:
1471:
1470:
1469:
1443:
1442:
1418:
1417:
1405:
1404:
1380:
1379:
1355:
1354:
1342:
1341:
1340:
1339:
1313:
1312:
1288:
1287:
1275:
1274:
1249:
1247:
1246:
1241:
1234:
1233:
1232:
1209:
1207:
1206:
1201:
1187:
1186:
1162:
1161:
1149:
1148:
1147:
1146:
1120:
1119:
1095:
1094:
1082:
1081:
1063:
1062:
1044:
1043:
1019:
1018:
1006:
1005:
1004:
1003:
977:
976:
952:
951:
939:
938:
909:
907:
906:
901:
889:
887:
886:
881:
879:
878:
859:
857:
856:
851:
849:
848:
832:
830:
829:
824:
822:
821:
805:
803:
802:
797:
785:
783:
782:
777:
772:
771:
747:
746:
734:
733:
721:
720:
704:
702:
701:
696:
694:
693:
684:
683:
670:
659:
641:
640:
628:
627:
608:
606:
605:
600:
598:
597:
581:
579:
578:
573:
571:
570:
554:
552:
551:
546:
534:
532:
531:
526:
521:
520:
496:
495:
483:
482:
470:
469:
453:
451:
450:
445:
443:
442:
433:
432:
419:
408:
390:
389:
377:
376:
356:
354:
353:
348:
346:
345:
329:
327:
326:
321:
319:
318:
302:
300:
299:
294:
292:
291:
275:
273:
272:
267:
265:
264:
248:
246:
245:
240:
228:
226:
225:
220:
208:
206:
205:
200:
164:Theodore Motzkin
151:. It can output
113:
107:
81:
80:|topic=
78:, and specifying
63:Google Translate
48:
45:(September 2013)
44:
27:
26:
19:
5687:
5686:
5682:
5681:
5680:
5678:
5677:
5676:
5657:
5656:
5655:
5650:
5633:
5590:
5569:
5532:
5493:
5470:
5459:
5452:
5406:
5381:
5345:
5312:
5303:
5280:
5269:
5248:
5222:
5218:Penalty methods
5213:Barrier methods
5197:
5184:
5164:
5160:Newton's method
5142:
5094:
5057:
5025:
5006:Powell's method
4983:
4970:
4953:
4922:
4896:
4878:10.2307/2322281
4861:
4831:
4812:
4810:Further reading
4807:
4790:
4786:
4775:
4768:
4759:
4755:
4744:
4740:
4729:
4725:
4717:
4699:
4695:
4680:Fourier, Joseph
4677:
4673:
4669:
4646:
4624:
4621:
4620:
4595:
4591:
4590:
4585:
4584:
4582:
4579:
4578:
4548:
4544:
4539:
4533:
4529:
4521:
4518:
4517:
4497:
4493:
4488:
4482:
4478:
4460:
4456:
4438:
4434:
4425:
4421:
4413:
4410:
4409:
4389:
4385:
4367:
4363:
4354:
4350:
4342:
4339:
4338:
4322:
4319:
4318:
4299:
4274:
4270:
4268:
4265:
4264:
4248:
4242:
4238:
4233:
4225:
4219:
4215:
4210:
4202:
4199:
4198:
4182:
4179:
4178:
4141:
4137:
4128:
4124:
4112:
4108:
4107:
4103:
4086:
4080:
4076:
4071:
4057:
4051:
4047:
4042:
4034:
4031:
4030:
4014:
4011:
4010:
3993:
3989:
3987:
3984:
3983:
3982:If the history
3952:
3948:
3946:
3943:
3942:
3924:
3920:
3918:
3915:
3914:
3898:
3895:
3894:
3877:
3873:
3871:
3868:
3867:
3842:
3838:
3836:
3833:
3832:
3813:
3809:
3807:
3804:
3803:
3787:
3784:
3783:
3766:
3762:
3760:
3757:
3756:
3739:
3735:
3733:
3730:
3729:
3704:
3700:
3698:
3695:
3694:
3674:
3670:
3661:
3657:
3648:
3644:
3642:
3639:
3638:
3621:
3617:
3615:
3612:
3611:
3595:
3592:
3591:
3555:
3551:
3536:
3532:
3520:
3516:
3514:
3511:
3510:
3490:
3486:
3477:
3473:
3464:
3460:
3458:
3455:
3454:
3437:
3433:
3431:
3428:
3427:
3410:
3406:
3404:
3401:
3400:
3374:
3370:
3355:
3351:
3342:
3338:
3320:
3316:
3301:
3297:
3288:
3284:
3276:
3273:
3272:
3250:
3247:
3246:
3217:
3213:
3211:
3208:
3207:
3191:
3188:
3187:
3171:
3168:
3167:
3151:
3148:
3147:
3130:
3126:
3124:
3121:
3120:
3110:
3073:
3069:
3068:
3064:
3056:
3045:
3042:
3041:
3025:
3022:
3021:
3002:
2996:
2992:
2990:
2987:
2986:
2970:
2967:
2966:
2963:
2937:
2936:
2906:
2905:
2884:
2883:
2861:
2860:
2858:
2855:
2854:
2831:
2830:
2802:
2800:
2772:
2770:
2767:
2766:
2738:
2736:
2708:
2706:
2703:
2702:
2674:
2672:
2644:
2642:
2635:
2634:
2632:
2629:
2628:
2605:
2604:
2576:
2574:
2565:
2564:
2533:
2531:
2528:
2527:
2499:
2497:
2488:
2487:
2459:
2457:
2444:
2443:
2441:
2438:
2437:
2413:
2412:
2376:
2375:
2339:
2338:
2305:
2304:
2267:
2266:
2264:
2261:
2260:
2254:
2230:
2224:
2220:
2218:
2215:
2214:
2195:
2183:
2179:
2170:
2166:
2164:
2161:
2160:
2143:
2139:
2133:
2129:
2117:
2113:
2104:
2100:
2089:
2086:
2085:
2068:
2064:
2062:
2059:
2058:
2038:
2034:
2020:
2017:
2016:
1999:
1995:
1981:
1978:
1977:
1951:
1947:
1932:
1928:
1919:
1915:
1897:
1893:
1878:
1874:
1865:
1861:
1859:
1856:
1855:
1838:
1834:
1828:
1824:
1822:
1819:
1818:
1786:
1782:
1767:
1763:
1752:
1748:
1747:
1743:
1719:
1715:
1700:
1696:
1687:
1683:
1656:
1652:
1637:
1633:
1622:
1618:
1617:
1613:
1589:
1585:
1570:
1566:
1557:
1553:
1545:
1542:
1541:
1499:
1495:
1480:
1476:
1465:
1461:
1460:
1456:
1432:
1428:
1413:
1409:
1400:
1396:
1369:
1365:
1350:
1346:
1335:
1331:
1330:
1326:
1302:
1298:
1283:
1279:
1270:
1266:
1258:
1255:
1254:
1228:
1224:
1219:
1216:
1215:
1176:
1172:
1157:
1153:
1142:
1138:
1137:
1133:
1109:
1105:
1090:
1086:
1077:
1073:
1058:
1054:
1033:
1029:
1014:
1010:
999:
995:
994:
990:
966:
962:
947:
943:
934:
930:
922:
919:
918:
895:
892:
891:
874:
870:
868:
865:
864:
844:
840:
838:
835:
834:
817:
813:
811:
808:
807:
791:
788:
787:
761:
757:
742:
738:
729:
725:
716:
712:
710:
707:
706:
689:
685:
676:
672:
660:
649:
636:
632:
623:
619:
617:
614:
613:
593:
589:
587:
584:
583:
566:
562:
560:
557:
556:
540:
537:
536:
510:
506:
491:
487:
478:
474:
465:
461:
459:
456:
455:
438:
434:
425:
421:
409:
398:
385:
381:
372:
368:
366:
363:
362:
341:
337:
335:
332:
331:
314:
310:
308:
305:
304:
287:
283:
281:
278:
277:
260:
256:
254:
251:
250:
234:
231:
230:
214:
211:
210:
194:
191:
190:
172:
130:
129:
128:
111:
105:
79:
51:
28:
24:
17:
12:
11:
5:
5685:
5675:
5674:
5669:
5652:
5651:
5649:
5648:
5642:
5639:
5638:
5635:
5634:
5632:
5631:
5626:
5621:
5616:
5611:
5606:
5601:
5595:
5592:
5591:
5588:Metaheuristics
5579:
5578:
5575:
5574:
5571:
5570:
5568:
5567:
5562:
5560:Ford–Fulkerson
5557:
5552:
5546:
5544:
5538:
5537:
5534:
5533:
5531:
5530:
5528:Floyd–Warshall
5525:
5520:
5519:
5518:
5507:
5505:
5495:
5494:
5492:
5491:
5486:
5481:
5475:
5473:
5462:
5454:
5453:
5451:
5450:
5449:
5448:
5434:
5429:
5424:
5418:
5416:
5408:
5407:
5395:
5394:
5391:
5390:
5387:
5386:
5383:
5382:
5380:
5379:
5374:
5369:
5364:
5358:
5356:
5347:
5346:
5344:
5343:
5338:
5333:
5331:Affine scaling
5327:
5325:
5323:Interior point
5316:
5305:
5304:
5302:
5301:
5296:
5291:
5285:
5283:
5271:
5270:
5258:
5257:
5254:
5253:
5250:
5249:
5247:
5246:
5241:
5236:
5230:
5228:
5227:Differentiable
5224:
5223:
5221:
5220:
5215:
5209:
5207:
5199:
5198:
5186:
5185:
5175:
5173:
5170:
5169:
5166:
5165:
5163:
5162:
5156:
5154:
5148:
5147:
5144:
5143:
5141:
5140:
5135:
5130:
5125:
5120:
5115:
5110:
5104:
5102:
5096:
5095:
5093:
5092:
5087:
5082:
5073:
5067:
5065:
5059:
5058:
5056:
5055:
5050:
5044:
5042:
5033:
5027:
5026:
5024:
5023:
5018:
5013:
5008:
5003:
4997:
4995:
4985:
4984:
4972:
4971:
4952:
4951:
4944:
4937:
4929:
4920:
4919:
4913:
4907:
4895:
4894:External links
4892:
4891:
4890:
4872:(9): 681–695.
4854:
4835:
4829:
4811:
4808:
4806:
4805:
4784:
4766:
4753:
4738:
4723:
4715:
4703:Matoušek, Jiří
4693:
4670:
4668:
4665:
4664:
4663:
4653:
4645:
4642:
4628:
4606:
4603:
4598:
4594:
4588:
4562:
4559:
4556:
4551:
4547:
4542:
4536:
4532:
4528:
4525:
4505:
4500:
4496:
4491:
4485:
4481:
4477:
4474:
4471:
4468:
4463:
4459:
4455:
4452:
4449:
4446:
4441:
4437:
4433:
4428:
4424:
4420:
4417:
4397:
4392:
4388:
4384:
4381:
4378:
4375:
4370:
4366:
4362:
4357:
4353:
4349:
4346:
4326:
4298:
4295:
4277:
4273:
4251:
4245:
4241:
4236:
4232:
4228:
4222:
4218:
4213:
4209:
4206:
4186:
4153:
4149:
4144:
4140:
4136:
4131:
4127:
4123:
4120:
4115:
4111:
4106:
4102:
4099:
4096:
4089:
4083:
4079:
4074:
4067:
4060:
4054:
4050:
4045:
4041:
4038:
4018:
3996:
3992:
3970:
3969:
3955:
3951:
3940:
3927:
3923:
3902:
3880:
3876:
3845:
3841:
3830:
3816:
3812:
3791:
3769:
3765:
3742:
3738:
3707:
3703:
3677:
3673:
3669:
3664:
3660:
3656:
3651:
3647:
3624:
3620:
3599:
3575:
3570:
3567:
3564:
3561:
3558:
3554:
3550:
3547:
3544:
3539:
3535:
3531:
3528:
3523:
3519:
3493:
3489:
3485:
3480:
3476:
3472:
3467:
3463:
3440:
3436:
3413:
3409:
3388:
3383:
3380:
3377:
3373:
3369:
3366:
3363:
3358:
3354:
3350:
3345:
3341:
3337:
3334:
3329:
3326:
3323:
3319:
3315:
3312:
3309:
3304:
3300:
3296:
3291:
3287:
3283:
3280:
3260:
3257:
3254:
3234:
3231:
3228:
3225:
3220:
3216:
3195:
3175:
3155:
3133:
3129:
3109:
3106:
3076:
3072:
3067:
3063:
3059:
3055:
3052:
3049:
3029:
3009:
3005:
2999:
2995:
2974:
2962:
2959:
2954:
2953:
2940:
2935:
2932:
2929:
2926:
2923:
2920:
2917:
2914:
2911:
2908:
2907:
2904:
2901:
2898:
2895:
2892:
2889:
2886:
2885:
2882:
2879:
2876:
2873:
2870:
2867:
2866:
2864:
2848:
2847:
2834:
2827:
2823:
2820:
2817:
2814:
2811:
2808:
2805:
2799:
2794:
2790:
2787:
2784:
2781:
2778:
2775:
2769:
2768:
2763:
2759:
2756:
2753:
2750:
2747:
2744:
2741:
2735:
2730:
2726:
2723:
2720:
2717:
2714:
2711:
2705:
2704:
2699:
2695:
2692:
2689:
2686:
2683:
2680:
2677:
2671:
2666:
2662:
2659:
2656:
2653:
2650:
2647:
2641:
2640:
2638:
2622:
2621:
2608:
2601:
2597:
2594:
2591:
2588:
2585:
2582:
2579:
2573:
2570:
2567:
2566:
2563:
2560:
2555:
2551:
2548:
2545:
2542:
2539:
2536:
2530:
2529:
2524:
2520:
2517:
2514:
2511:
2508:
2505:
2502:
2496:
2493:
2490:
2489:
2484:
2480:
2477:
2474:
2471:
2468:
2465:
2462:
2456:
2453:
2450:
2449:
2447:
2430:
2429:
2416:
2411:
2408:
2405:
2402:
2399:
2396:
2393:
2390:
2387:
2384:
2381:
2378:
2377:
2374:
2371:
2368:
2365:
2362:
2359:
2356:
2353:
2350:
2347:
2344:
2341:
2340:
2337:
2334:
2331:
2328:
2325:
2322:
2319:
2316:
2313:
2310:
2307:
2306:
2303:
2300:
2297:
2294:
2291:
2288:
2285:
2282:
2279:
2276:
2273:
2272:
2270:
2253:
2250:
2237:
2233:
2227:
2223:
2202:
2198:
2194:
2191:
2186:
2182:
2178:
2173:
2169:
2146:
2142:
2136:
2132:
2128:
2125:
2120:
2116:
2112:
2107:
2103:
2099:
2096:
2093:
2071:
2067:
2041:
2037:
2033:
2030:
2027:
2024:
2002:
1998:
1994:
1991:
1988:
1985:
1965:
1960:
1957:
1954:
1950:
1946:
1943:
1940:
1935:
1931:
1927:
1922:
1918:
1914:
1911:
1906:
1903:
1900:
1896:
1892:
1889:
1886:
1881:
1877:
1873:
1868:
1864:
1841:
1837:
1831:
1827:
1815:
1814:
1803:
1800:
1795:
1792:
1789:
1785:
1781:
1778:
1775:
1770:
1766:
1762:
1755:
1751:
1746:
1742:
1739:
1736:
1733:
1728:
1725:
1722:
1718:
1714:
1711:
1708:
1703:
1699:
1695:
1690:
1686:
1682:
1679:
1676:
1673:
1670:
1665:
1662:
1659:
1655:
1651:
1648:
1645:
1640:
1636:
1632:
1625:
1621:
1616:
1612:
1609:
1606:
1603:
1598:
1595:
1592:
1588:
1584:
1581:
1578:
1573:
1569:
1565:
1560:
1556:
1552:
1549:
1535:
1534:
1522:
1519:
1516:
1513:
1508:
1505:
1502:
1498:
1494:
1491:
1488:
1483:
1479:
1475:
1468:
1464:
1459:
1455:
1452:
1449:
1446:
1441:
1438:
1435:
1431:
1427:
1424:
1421:
1416:
1412:
1408:
1403:
1399:
1395:
1392:
1389:
1386:
1383:
1378:
1375:
1372:
1368:
1364:
1361:
1358:
1353:
1349:
1345:
1338:
1334:
1329:
1325:
1322:
1319:
1316:
1311:
1308:
1305:
1301:
1297:
1294:
1291:
1286:
1282:
1278:
1273:
1269:
1265:
1262:
1239:
1231:
1227:
1223:
1212:
1211:
1199:
1196:
1193:
1190:
1185:
1182:
1179:
1175:
1171:
1168:
1165:
1160:
1156:
1152:
1145:
1141:
1136:
1132:
1129:
1126:
1123:
1118:
1115:
1112:
1108:
1104:
1101:
1098:
1093:
1089:
1085:
1080:
1076:
1072:
1069:
1066:
1061:
1057:
1053:
1050:
1047:
1042:
1039:
1036:
1032:
1028:
1025:
1022:
1017:
1013:
1009:
1002:
998:
993:
989:
986:
983:
980:
975:
972:
969:
965:
961:
958:
955:
950:
946:
942:
937:
933:
929:
926:
912:
911:
899:
877:
873:
861:
847:
843:
820:
816:
795:
775:
770:
767:
764:
760:
756:
753:
750:
745:
741:
737:
732:
728:
724:
719:
715:
692:
688:
682:
679:
675:
669:
666:
663:
658:
655:
652:
648:
644:
639:
635:
631:
626:
622:
610:
596:
592:
569:
565:
544:
524:
519:
516:
513:
509:
505:
502:
499:
494:
490:
486:
481:
477:
473:
468:
464:
441:
437:
431:
428:
424:
418:
415:
412:
407:
404:
401:
397:
393:
388:
384:
380:
375:
371:
344:
340:
317:
313:
290:
286:
263:
259:
238:
218:
198:
171:
168:
160:Joseph Fourier
132:
131:
127:
126:
119:
108:
86:
83:
71:adding a topic
66:
55:
52:
33:
32:
31:
29:
22:
15:
9:
6:
4:
3:
2:
5684:
5673:
5670:
5668:
5665:
5664:
5662:
5647:
5644:
5643:
5640:
5630:
5627:
5625:
5622:
5620:
5617:
5615:
5612:
5610:
5607:
5605:
5604:Hill climbing
5602:
5600:
5597:
5596:
5593:
5589:
5584:
5580:
5566:
5563:
5561:
5558:
5556:
5553:
5551:
5548:
5547:
5545:
5543:
5542:Network flows
5539:
5529:
5526:
5524:
5521:
5517:
5514:
5513:
5512:
5509:
5508:
5506:
5504:
5503:Shortest path
5500:
5490:
5487:
5485:
5482:
5480:
5477:
5476:
5474:
5472:
5471:spanning tree
5466:
5463:
5461:
5455:
5447:
5443:
5440:
5439:
5438:
5435:
5433:
5430:
5428:
5425:
5423:
5420:
5419:
5417:
5413:
5409:
5405:
5404:Combinatorial
5400:
5396:
5378:
5375:
5373:
5370:
5368:
5365:
5363:
5360:
5359:
5357:
5355:
5352:
5348:
5342:
5339:
5337:
5334:
5332:
5329:
5328:
5326:
5324:
5320:
5317:
5315:
5310:
5306:
5300:
5297:
5295:
5292:
5290:
5287:
5286:
5284:
5282:
5276:
5272:
5268:
5263:
5259:
5245:
5242:
5240:
5237:
5235:
5232:
5231:
5229:
5225:
5219:
5216:
5214:
5211:
5210:
5208:
5204:
5200:
5196:
5191:
5187:
5179:
5161:
5158:
5157:
5155:
5153:
5149:
5139:
5136:
5134:
5131:
5129:
5126:
5124:
5121:
5119:
5116:
5114:
5111:
5109:
5106:
5105:
5103:
5101:
5100:Other methods
5097:
5091:
5088:
5086:
5083:
5081:
5077:
5074:
5072:
5069:
5068:
5066:
5064:
5060:
5054:
5051:
5049:
5046:
5045:
5043:
5041:
5037:
5034:
5032:
5028:
5022:
5019:
5017:
5014:
5012:
5009:
5007:
5004:
5002:
4999:
4998:
4996:
4994:
4990:
4986:
4982:
4977:
4973:
4969:
4965:
4961:
4957:
4950:
4945:
4943:
4938:
4936:
4931:
4930:
4927:
4923:
4917:
4914:
4911:
4908:
4905:
4901:
4898:
4897:
4887:
4883:
4879:
4875:
4871:
4867:
4860:
4855:
4850:
4849:10.1.1.54.657
4845:
4841:
4836:
4832:
4826:
4822:
4818:
4814:
4813:
4800:
4795:
4788:
4781:
4780:
4773:
4771:
4763:
4757:
4750:
4747:
4742:
4735:
4734:
4727:
4721:Pages 81–104.
4718:
4716:3-540-30697-8
4712:
4708:
4704:
4697:
4689:
4685:
4681:
4675:
4671:
4661:
4657:
4654:
4651:
4650:Farkas' lemma
4648:
4647:
4641:
4626:
4604:
4601:
4596:
4592:
4576:
4560:
4557:
4549:
4545:
4534:
4530:
4523:
4498:
4494:
4483:
4479:
4472:
4469:
4461:
4457:
4450:
4447:
4439:
4435:
4431:
4426:
4422:
4415:
4390:
4386:
4379:
4376:
4368:
4364:
4360:
4355:
4351:
4344:
4324:
4315:
4312:
4308:
4303:
4294:
4291:
4275:
4271:
4243:
4239:
4230:
4220:
4216:
4207:
4204:
4197:is such that
4184:
4176:
4172:
4169:
4166:
4151:
4142:
4138:
4134:
4129:
4125:
4118:
4113:
4109:
4104:
4100:
4097:
4094:
4081:
4077:
4065:
4052:
4048:
4039:
4036:
4016:
3994:
3990:
3981:
3977:
3975:
3953:
3949:
3941:
3925:
3921:
3900:
3878:
3874:
3865:
3861:
3858:, the set of
3843:
3839:
3831:
3814:
3810:
3789:
3767:
3763:
3740:
3736:
3727:
3723:
3720:, the set of
3705:
3701:
3693:
3692:
3691:
3675:
3671:
3667:
3662:
3658:
3654:
3649:
3645:
3622:
3618:
3597:
3589:
3568:
3565:
3562:
3559:
3556:
3552:
3548:
3545:
3542:
3537:
3533:
3526:
3521:
3517:
3507:
3491:
3487:
3483:
3478:
3474:
3470:
3465:
3461:
3438:
3434:
3411:
3407:
3381:
3378:
3375:
3371:
3367:
3364:
3361:
3356:
3352:
3343:
3339:
3335:
3327:
3324:
3321:
3317:
3313:
3310:
3307:
3302:
3298:
3289:
3285:
3281:
3278:
3258:
3255:
3252:
3229:
3223:
3218:
3214:
3193:
3173:
3153:
3131:
3127:
3119:
3114:
3105:
3103:
3099:
3097:
3092:
3074:
3070:
3061:
3057:
3053:
3047:
3027:
3007:
3003:
2997:
2993:
2972:
2958:
2933:
2930:
2927:
2924:
2921:
2918:
2915:
2912:
2909:
2902:
2899:
2896:
2893:
2890:
2887:
2880:
2877:
2874:
2871:
2868:
2862:
2853:
2852:
2851:
2850:Simplifying:
2825:
2821:
2818:
2815:
2812:
2809:
2806:
2803:
2797:
2792:
2788:
2785:
2782:
2779:
2776:
2773:
2761:
2757:
2754:
2751:
2748:
2745:
2742:
2739:
2733:
2728:
2724:
2721:
2718:
2715:
2712:
2709:
2697:
2693:
2690:
2687:
2684:
2681:
2678:
2675:
2669:
2664:
2660:
2657:
2654:
2651:
2648:
2645:
2636:
2627:
2626:
2625:
2599:
2595:
2592:
2589:
2586:
2583:
2580:
2577:
2571:
2568:
2561:
2558:
2553:
2549:
2546:
2543:
2540:
2537:
2534:
2522:
2518:
2515:
2512:
2509:
2506:
2503:
2500:
2494:
2491:
2482:
2478:
2475:
2472:
2469:
2466:
2463:
2460:
2454:
2451:
2445:
2436:
2435:
2434:
2409:
2406:
2403:
2400:
2397:
2394:
2391:
2388:
2385:
2382:
2379:
2372:
2369:
2366:
2363:
2360:
2357:
2354:
2351:
2348:
2345:
2342:
2335:
2332:
2329:
2326:
2323:
2320:
2317:
2314:
2311:
2308:
2301:
2298:
2295:
2292:
2289:
2286:
2283:
2280:
2277:
2274:
2268:
2259:
2258:
2257:
2249:
2235:
2231:
2225:
2221:
2200:
2196:
2192:
2189:
2184:
2180:
2176:
2171:
2167:
2144:
2140:
2134:
2130:
2126:
2118:
2114:
2110:
2105:
2101:
2097:
2094:
2069:
2065:
2055:
2039:
2035:
2031:
2028:
2025:
2022:
2000:
1996:
1992:
1989:
1986:
1983:
1958:
1955:
1952:
1948:
1944:
1941:
1938:
1933:
1929:
1920:
1916:
1912:
1904:
1901:
1898:
1894:
1890:
1887:
1884:
1879:
1875:
1866:
1862:
1854:inequalities
1839:
1835:
1829:
1825:
1793:
1790:
1787:
1783:
1779:
1776:
1773:
1768:
1764:
1753:
1749:
1744:
1740:
1737:
1734:
1726:
1723:
1720:
1716:
1712:
1709:
1706:
1701:
1697:
1688:
1684:
1674:
1663:
1660:
1657:
1653:
1649:
1646:
1643:
1638:
1634:
1623:
1619:
1614:
1610:
1607:
1604:
1596:
1593:
1590:
1586:
1582:
1579:
1576:
1571:
1567:
1558:
1554:
1540:
1539:
1538:
1520:
1517:
1506:
1503:
1500:
1496:
1492:
1489:
1486:
1481:
1477:
1466:
1462:
1457:
1453:
1450:
1447:
1439:
1436:
1433:
1429:
1425:
1422:
1419:
1414:
1410:
1401:
1397:
1387:
1376:
1373:
1370:
1366:
1362:
1359:
1356:
1351:
1347:
1336:
1332:
1327:
1323:
1320:
1317:
1309:
1306:
1303:
1299:
1295:
1292:
1289:
1284:
1280:
1271:
1267:
1253:
1252:
1251:
1237:
1229:
1225:
1197:
1194:
1183:
1180:
1177:
1173:
1169:
1166:
1163:
1158:
1154:
1143:
1139:
1134:
1130:
1127:
1124:
1116:
1113:
1110:
1106:
1102:
1099:
1096:
1091:
1087:
1078:
1074:
1064:
1059:
1055:
1051:
1040:
1037:
1034:
1030:
1026:
1023:
1020:
1015:
1011:
1000:
996:
991:
987:
984:
981:
973:
970:
967:
963:
959:
956:
953:
948:
944:
935:
931:
917:
916:
915:
897:
875:
871:
862:
845:
841:
818:
814:
793:
768:
765:
762:
758:
754:
751:
748:
743:
739:
730:
726:
722:
717:
713:
690:
686:
680:
677:
673:
667:
664:
661:
656:
653:
650:
646:
642:
637:
633:
629:
624:
620:
611:
594:
590:
567:
563:
542:
517:
514:
511:
507:
503:
500:
497:
492:
488:
479:
475:
471:
466:
462:
439:
435:
429:
426:
422:
416:
413:
410:
405:
402:
399:
395:
391:
386:
382:
378:
373:
369:
360:
359:
358:
342:
338:
315:
311:
288:
284:
261:
257:
236:
216:
196:
187:
183:
181:
177:
167:
165:
161:
156:
154:
150:
146:
142:
138:
124:
120:
117:
109:
103:
99:
95:
91:
87:
84:
77:
76:main category
73:
72:
67:
64:
60:
56:
54:
53:
47:
41:
39:
34:You can help
30:
21:
20:
5609:Local search
5555:Edmonds–Karp
5511:Bellman–Ford
5281:minimization
5113:Gauss–Newton
5063:Quasi–Newton
5048:Trust region
4956:Optimization
4921:
4869:
4865:
4839:
4820:
4787:
4778:
4761:
4756:
4748:
4741:
4732:
4726:
4706:
4696:
4687:
4674:
4659:
4316:
4300:
4292:
4290:is minimal.
4174:
4173:
4170:
4167:
3979:
3978:
3973:
3971:
3863:
3859:
3725:
3721:
3587:
3508:
3117:
3115:
3111:
3100:
3093:
2964:
2955:
2849:
2623:
2431:
2255:
2056:
1816:
1536:
1213:
913:
188:
184:
179:
175:
173:
157:
140:
136:
135:
98:edit summary
89:
69:
43:
35:
5629:Tabu search
5040:Convergence
5011:Line search
3862:variables,
3724:variables,
3116:Define the
3094:McMullen's
170:Elimination
155:solutions.
5661:Categories
5460:algorithms
4968:heuristics
4960:Algorithms
4799:1610.03990
4667:References
4660:polynomial
3588:officially
3586:have been
2961:Complexity
249:variables
141:FME method
5415:Paradigms
5314:quadratic
5031:Gradients
4993:Functions
4844:CiteSeerX
4842:: 66–71.
4602:−
4558:≥
4470:−
4377:≤
4135:∩
4119:∪
4095:≤
4066:≤
3668:∪
3655:∪
3560:−
3546:…
3484:∪
3379:−
3365:…
3336:≤
3325:−
3311:…
3256:∈
2931:−
2928:⩽
2910:−
2900:−
2897:⩽
2878:−
2875:⩽
2816:−
2798:⩽
2777:−
2743:−
2734:⩽
2713:−
2679:−
2670:⩽
2649:−
2590:−
2572:⩽
2559:⩽
2538:−
2504:−
2495:⩽
2464:−
2455:⩽
2407:⩽
2380:−
2370:−
2367:⩽
2358:−
2343:−
2333:⩽
2315:−
2299:⩽
2281:−
2111:−
2098:−
2032:≤
2026:≤
1993:≤
1987:≤
1956:−
1942:…
1913:≤
1902:−
1888:…
1791:−
1777:…
1738:…
1724:−
1710:…
1675:≤
1661:−
1647:…
1608:…
1594:−
1580:…
1521:ϕ
1518:∧
1504:−
1490:…
1451:…
1437:−
1423:…
1388:≤
1374:−
1360:…
1321:…
1307:−
1293:…
1222:∃
1198:ϕ
1195:∧
1181:−
1167:…
1128:…
1114:−
1100:…
1065:≤
1052:≤
1038:−
1024:…
985:…
971:−
957:…
898:ϕ
766:−
752:…
723:≤
665:−
647:∑
643:−
630:≤
515:−
501:…
472:≥
414:−
396:∑
392:−
379:≥
145:algorithm
116:talk page
68:Consider
40:in German
5646:Software
5523:Dijkstra
5354:exchange
5152:Hessians
5118:Gradient
4819:(1998).
4705:(2006).
4682:(1827).
4644:See also
4619:, where
3206:. Thus,
92:provide
5489:Kruskal
5479:Borůvka
5469:Minimum
5206:General
4964:methods
4886:2322281
4263:, then
3974:minimal
3913:nor in
3118:history
2252:Example
303:, with
114:to the
96:in the
42:.
5351:Basis-
5309:Linear
5279:Convex
5123:Mirror
5080:L-BFGS
4966:, and
4884:
4846:
4827:
4713:
4092:
4069:
4063:
1976:, for
1235:
833:where
786:, for
582:where
535:, for
5550:Dinic
5458:Graph
4882:JSTOR
4862:(PDF)
4794:arXiv
3637:into
59:DeepL
5516:SPFA
5484:Prim
5078:and
4825:ISBN
4711:ISBN
4575:cone
3864:i.e.
3726:i.e.
2015:and
153:real
90:must
88:You
5446:cut
5311:and
4874:doi
4577:in
3782:of
1678:min
1548:max
1391:min
1261:max
1068:min
925:max
276:to
209:of
61:or
5663::
4962:,
4958::
4880:.
4870:93
4868:.
4864:.
4769:^
4686:.
4165:.
3976:.
3690::
3506:.
2922:17
2804:12
2676:10
2578:12
2461:10
2410:12
2302:10
2248:.
2054:.
357:.
5444:/
4948:e
4941:t
4934:v
4906:.
4888:.
4876::
4852:.
4833:.
4802:.
4796::
4782:.
4719:.
4627:n
4605:1
4597:n
4593:2
4587:R
4561:0
4555:)
4550:2
4546:X
4541:|
4535:1
4531:X
4527:(
4524:H
4504:)
4499:2
4495:X
4490:|
4484:1
4480:X
4476:(
4473:H
4467:)
4462:1
4458:X
4454:(
4451:H
4448:=
4445:)
4440:2
4436:X
4432:;
4427:1
4423:X
4419:(
4416:I
4396:)
4391:1
4387:X
4383:(
4380:H
4374:)
4369:2
4365:X
4361:;
4356:1
4352:X
4348:(
4345:I
4325:i
4276:i
4272:H
4250:|
4244:i
4240:H
4235:|
4231:=
4227:|
4221:i
4217:E
4212:|
4208:+
4205:1
4185:i
4152:|
4148:)
4143:k
4139:O
4130:i
4126:I
4122:(
4114:i
4110:E
4105:|
4101:+
4098:1
4088:|
4082:i
4078:H
4073:|
4059:|
4053:i
4049:E
4044:|
4040:+
4037:1
4017:i
3995:i
3991:H
3954:i
3950:R
3926:i
3922:E
3901:i
3879:i
3875:H
3844:i
3840:I
3829:.
3815:j
3811:x
3790:i
3768:i
3764:H
3741:j
3737:x
3706:i
3702:E
3676:i
3672:R
3663:i
3659:I
3650:i
3646:E
3623:k
3619:O
3598:i
3574:}
3569:1
3566:+
3563:k
3557:r
3553:x
3549:,
3543:,
3538:r
3534:x
3530:{
3527:=
3522:k
3518:O
3492:j
3488:H
3479:i
3475:H
3471:=
3466:k
3462:H
3439:k
3435:H
3412:r
3408:x
3387:)
3382:1
3376:r
3372:x
3368:,
3362:,
3357:1
3353:x
3349:(
3344:j
3340:B
3333:)
3328:1
3322:r
3318:x
3314:,
3308:,
3303:1
3299:x
3295:(
3290:i
3286:A
3282::
3279:k
3259:S
3253:i
3233:}
3230:i
3227:{
3224:=
3219:i
3215:H
3194:i
3174:S
3154:i
3132:i
3128:H
3075:d
3071:2
3066:)
3062:4
3058:/
3054:n
3051:(
3048:4
3028:d
3008:4
3004:/
2998:2
2994:n
2973:n
2934:9
2925:y
2919:+
2916:x
2913:6
2903:1
2894:y
2891:+
2888:x
2881:4
2872:y
2869:5
2863:{
2826:6
2822:y
2819:2
2813:x
2810:3
2807:+
2793:2
2789:y
2786:5
2783:+
2780:x
2774:7
2762:3
2758:y
2755:6
2752:+
2749:x
2746:3
2740:9
2729:2
2725:y
2722:5
2719:+
2716:x
2710:7
2698:4
2694:y
2691:5
2688:+
2685:x
2682:2
2665:2
2661:y
2658:5
2655:+
2652:x
2646:7
2637:{
2600:6
2596:y
2593:2
2587:x
2584:3
2581:+
2569:z
2562:z
2554:2
2550:y
2547:5
2544:+
2541:x
2535:7
2523:3
2519:y
2516:6
2513:+
2510:x
2507:3
2501:9
2492:z
2483:4
2479:y
2476:5
2473:+
2470:x
2467:2
2452:z
2446:{
2404:z
2401:6
2398:+
2395:y
2392:2
2389:+
2386:x
2383:3
2373:7
2364:z
2361:2
2355:y
2352:5
2349:+
2346:x
2336:9
2330:z
2327:3
2324:+
2321:y
2318:6
2312:x
2309:3
2296:z
2293:4
2290:+
2287:y
2284:5
2278:x
2275:2
2269:{
2236:4
2232:/
2226:2
2222:n
2201:2
2197:/
2193:n
2190:=
2185:B
2181:n
2177:=
2172:A
2168:n
2145:B
2141:n
2135:A
2131:n
2127:+
2124:)
2119:B
2115:n
2106:A
2102:n
2095:n
2092:(
2070:r
2066:x
2040:B
2036:n
2029:j
2023:1
2001:A
1997:n
1990:i
1984:1
1964:)
1959:1
1953:r
1949:x
1945:,
1939:,
1934:1
1930:x
1926:(
1921:j
1917:B
1910:)
1905:1
1899:r
1895:x
1891:,
1885:,
1880:1
1876:x
1872:(
1867:i
1863:A
1840:B
1836:n
1830:A
1826:n
1802:)
1799:)
1794:1
1788:r
1784:x
1780:,
1774:,
1769:1
1765:x
1761:(
1754:B
1750:n
1745:B
1741:,
1735:,
1732:)
1727:1
1721:r
1717:x
1713:,
1707:,
1702:1
1698:x
1694:(
1689:1
1685:B
1681:(
1672:)
1669:)
1664:1
1658:r
1654:x
1650:,
1644:,
1639:1
1635:x
1631:(
1624:A
1620:n
1615:A
1611:,
1605:,
1602:)
1597:1
1591:r
1587:x
1583:,
1577:,
1572:1
1568:x
1564:(
1559:1
1555:A
1551:(
1533:.
1515:)
1512:)
1507:1
1501:r
1497:x
1493:,
1487:,
1482:1
1478:x
1474:(
1467:B
1463:n
1458:B
1454:,
1448:,
1445:)
1440:1
1434:r
1430:x
1426:,
1420:,
1415:1
1411:x
1407:(
1402:1
1398:B
1394:(
1385:)
1382:)
1377:1
1371:r
1367:x
1363:,
1357:,
1352:1
1348:x
1344:(
1337:A
1333:n
1328:A
1324:,
1318:,
1315:)
1310:1
1304:r
1300:x
1296:,
1290:,
1285:1
1281:x
1277:(
1272:1
1268:A
1264:(
1238:S
1230:r
1226:x
1210:.
1192:)
1189:)
1184:1
1178:r
1174:x
1170:,
1164:,
1159:1
1155:x
1151:(
1144:B
1140:n
1135:B
1131:,
1125:,
1122:)
1117:1
1111:r
1107:x
1103:,
1097:,
1092:1
1088:x
1084:(
1079:1
1075:B
1071:(
1060:r
1056:x
1049:)
1046:)
1041:1
1035:r
1031:x
1027:,
1021:,
1016:1
1012:x
1008:(
1001:A
997:n
992:A
988:,
982:,
979:)
974:1
968:r
964:x
960:,
954:,
949:1
945:x
941:(
936:1
932:A
928:(
910:.
876:r
872:x
846:B
842:n
819:B
815:n
794:i
774:)
769:1
763:r
759:x
755:,
749:,
744:1
740:x
736:(
731:i
727:B
718:r
714:x
691:k
687:x
681:k
678:i
674:a
668:1
662:r
657:1
654:=
651:k
638:i
634:b
625:r
621:x
595:A
591:n
568:A
564:n
543:i
523:)
518:1
512:r
508:x
504:,
498:,
493:1
489:x
485:(
480:i
476:A
467:r
463:x
440:k
436:x
430:k
427:i
423:a
417:1
411:r
406:1
403:=
400:k
387:i
383:b
374:r
370:x
343:r
339:x
316:r
312:x
289:r
285:x
262:1
258:x
237:r
217:n
197:S
180:V
176:V
125:.
118:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.