Linear programming

1265: 38: 4146: 4100:) since linear functions are both convex and concave. However, some problems have distinct optimal solutions; for example, the problem of finding a feasible solution to a system of linear inequalities is a linear programming problem in which the objective function is the zero function (i.e., the constant function taking the value zero everywhere). For this feasibility problem with the zero-function for its objective-function, if there are two distinct solutions, then every convex combination of the solutions is a solution. 3313: 8440: 557: 547: 2889: 290: 5425:

been studied since the 1970s. Essentially, these methods attempt to find the shortest pivot path on the arrangement polytope under the linear programming problem. In contrast to polytopal graphs, graphs of arrangement polytopes are known to have small diameter, allowing the possibility of strongly polynomial-time criss-cross pivot algorithm without resolving questions about the diameter of general polytopes.

2055: 58: 3308:{\displaystyle {\begin{bmatrix}1&-S_{1}&-S_{2}&0&0&0\\0&1&1&1&0&0\\0&F_{1}&F_{2}&0&1&0\\0&P_{1}&P_{2}&0&0&1\\\end{bmatrix}}{\begin{bmatrix}z\\x_{1}\\x_{2}\\x_{3}\\x_{4}\\x_{5}\end{bmatrix}}={\begin{bmatrix}0\\L\\F\\P\end{bmatrix}},\,{\begin{bmatrix}x_{1}\\x_{2}\\x_{3}\\x_{4}\\x_{5}\end{bmatrix}}\geq 0.} 2256: 166: 5421:. It has been proved that all polytopes have subexponential diameter. The recent disproof of the Hirsch conjecture is the first step to prove whether any polytope has superpolynomial diameter. If any such polytopes exist, then no edge-following variant can run in polynomial time. Questions about polytope diameter are of independent mathematical interest. 697:, are considered important enough to have much research on specialized algorithms. A number of algorithms for other types of optimization problems work by solving linear programming problems as sub-problems. Historically, ideas from linear programming have inspired many of the central concepts of optimization theory, such as 1815: 1053: 1247: 3499:

A linear program can also be unbounded or infeasible. Duality theory tells us that if the primal is unbounded then the dual is infeasible by the weak duality theorem. Likewise, if the dual is unbounded, then the primal must be infeasible. However, it is possible for both the dual and the primal to be

593:

Despite its initial obscurity, the wartime successes propelled linear programming into the spotlight. Post-WWII, the method gained widespread recognition and became a cornerstone in various fields, from operations research to economics. The overlooked contributions of Kantorovich and Leontief in the

5412:

The simplex algorithm and its variants fall in the family of edge-following algorithms, so named because they solve linear programming problems by moving from vertex to vertex along edges of a polytope. This means that their theoretical performance is limited by the maximum number of edges between

6345:

for multiple programming languages (C, C++, Fortran, Visual Basic, Java and C#) and packages (MATLAB, Excel, R, LabVIEW). The Optimization chapter of the NAG Library includes routines for linear programming problems with both sparse and non-sparse linear constraint matrices, together with routines

6168:

A general modeling language and interactive development environment. Its influence diagrams enable users to formulate problems as graphs with nodes for decision variables, objectives, and constraints. Analytica Optimizer Edition includes linear, mixed integer, and nonlinear solvers and selects the

4000:

This necessary condition for optimality conveys a fairly simple economic principle. In standard form (when maximizing), if there is slack in a constrained primal resource (i.e., there are "leftovers"), then additional quantities of that resource must have no value. Likewise, if there is slack in

5424:

Simplex pivot methods preserve primal (or dual) feasibility. On the other hand, criss-cross pivot methods do not preserve (primal or dual) feasibility – they may visit primal feasible, dual feasible or primal-and-dual infeasible bases in any order. Pivot methods of this type have

5326:

The current opinion is that the efficiencies of good implementations of simplex-based methods and interior point methods are similar for routine applications of linear programming. However, for specific types of LP problems, it may be that one type of solver is better than another (sometimes much

285:{\displaystyle {\begin{aligned}&{\text{Find a vector}}&&\mathbf {x} \\&{\text{that maximizes}}&&\mathbf {c} ^{\mathsf {T}}\mathbf {x} \\&{\text{subject to}}&&A\mathbf {x} \leq \mathbf {b} \\&{\text{and}}&&\mathbf {x} \geq \mathbf {0} .\end{aligned}}} 6268:

Solver with an API for large scale optimization of linear, integer, quadratic, conic and general nonlinear programs with stochastic programming extensions. It offers a global optimization procedure for finding guaranteed globally optimal solution to general nonlinear programs with continuous and

4204:

However, the simplex algorithm has poor worst-case behavior: Klee and Minty constructed a family of linear programming problems for which the simplex method takes a number of steps exponential in the problem size. In fact, for some time it was not known whether the linear programming problem was

3465:

There are two ideas fundamental to duality theory. One is the fact that (for the symmetric dual) the dual of a dual linear program is the original primal linear program. Additionally, every feasible solution for a linear program gives a bound on the optimal value of the objective function of its

2112: 589:

The turning point came during World War II when linear programming emerged as a vital tool. It found extensive use in addressing complex wartime challenges, including transportation logistics, scheduling, and resource allocation. Linear programming proved invaluable in optimizing these processes

4069:

is unbounded in the direction of the gradient of the objective function (where the gradient of the objective function is the vector of the coefficients of the objective function), then no optimal value is attained because it is always possible to do better than any finite value of the objective

1268:

Graphical solution to the farmer example – after shading regions violating the conditions, the vertex of the unshaded region with the dashed line farthest from the origin gives the optimal combination (its lying on the land and pesticide lines implies that revenue is limited by land and

6137:

A modeling language that allows to model linear, mixed integer, and nonlinear optimization models. It also offers a tool for constraint programming. Algorithm, in the forms of heuristics or exact methods, such as Branch-and-Cut or Column Generation, can also be implemented. The tool calls an

5741:

since they provide an alternate characterization of a problem. Specifically, for any problem, the convex hull of the solutions is an integral polyhedron; if this polyhedron has a nice/compact description, then we can efficiently find the optimal feasible solution under any linear objective.

5408:

These questions relate to the performance analysis and development of simplex-like methods. The immense efficiency of the simplex algorithm in practice despite its exponential-time theoretical performance hints that there may be variations of simplex that run in polynomial or even strongly

5390:, no algorithms have yet been found that allow strongly polynomial-time performance in the number of constraints and the number of variables. The development of such algorithms would be of great theoretical interest, and perhaps allow practical gains in solving large LPs as well. 4351:

Khachiyan's algorithm was of landmark importance for establishing the polynomial-time solvability of linear programs. The algorithm was not a computational break-through, as the simplex method is more efficient for all but specially constructed families of linear programs.

2050:{\displaystyle {\begin{bmatrix}1&1\\F_{1}&F_{2}\\P_{1}&P_{2}\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}\leq {\begin{bmatrix}L\\F\\P\end{bmatrix}},\,{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}\geq {\begin{bmatrix}0\\0\end{bmatrix}}.} 640:

was equivalent. Dantzig provided formal proof in an unpublished report "A Theorem on Linear Inequalities" on January 5, 1948. Dantzig's work was made available to public in 1951. In the post-war years, many industries applied it in their daily planning.

4402:). Karmarkar claimed that his algorithm was much faster in practical LP than the simplex method, a claim that created great interest in interior-point methods. Since Karmarkar's discovery, many interior-point methods have been proposed and analyzed. 6346:

for the optimization of quadratic, nonlinear, sums of squares of linear or nonlinear functions with nonlinear, bounded or no constraints. The NAG Library has routines for both local and global optimization, and for continuous or integer problems.

6257:

Collections of math and statistical algorithms available in C/C++, Fortran, Java and C#/.NET. Optimization routines in the IMSL Libraries include unconstrained, linearly and nonlinearly constrained minimizations, and linear programming algorithms.

1808: 851: 1149: 585:

independently delved into the practical applications of linear programming. Kantorovich focused on manufacturing schedules, while Leontief explored economic applications. Their groundbreaking work was largely overlooked for decades.

5351:

There are several open problems in the theory of linear programming, the solution of which would represent fundamental breakthroughs in mathematics and potentially major advances in our ability to solve large-scale linear programs.

644:

Dantzig's original example was to find the best assignment of 70 people to 70 jobs. The computing power required to test all the permutations to select the best assignment is vast; the number of possible configurations exceeds the

4225:

is a basis-exchange algorithm that pivots between bases. However, the criss-cross algorithm need not maintain feasibility, but can pivot rather from a feasible basis to an infeasible basis. The criss-cross algorithm does not have

4190:" occurs: many pivots are made with no increase in the objective function. In rare practical problems, the usual versions of the simplex algorithm may actually "cycle". To avoid cycles, researchers developed new pivoting rules. 5327:

better), and that the structure of the solutions generated by interior point methods versus simplex-based methods are significantly different with the support set of active variables being typically smaller for the latter one.

2251:{\displaystyle {\begin{bmatrix}1&-\mathbf {c} ^{\mathsf {T}}&0\\0&\mathbf {A} &\mathbf {I} \end{bmatrix}}{\begin{bmatrix}z\\\mathbf {x} \\\mathbf {s} \end{bmatrix}}={\begin{bmatrix}0\\\mathbf {b} \end{bmatrix}}} 431: 4915: 5453:(BIP) is the special case of integer programming where variables are required to be 0 or 1 (rather than arbitrary integers). This problem is also classified as NP-hard, and in fact the decision version was one of 1129: 5409:

polynomial time. It would be of great practical and theoretical significance to know whether any such variants exist, particularly as an approach to deciding if LP can be solved in strongly polynomial time.

6385:

Solver for large-scale linear programs, quadratic programs, general nonlinear and mixed-integer programs. Has API for several programming languages, also has a modelling language Mosel and works with AMPL,

4254:

In contrast to the simplex algorithm, which finds an optimal solution by traversing the edges between vertices on a polyhedral set, interior-point methods move through the interior of the feasible region.

712:, and it is currently utilized in company management, such as planning, production, transportation, and technology. Although the modern management issues are ever-changing, most companies would like to 2702: 2609: 4692: 1641: 1561: 4127:. Thereby we can study these vertices by means of looking at certain subsets of the set of all constraints (a discrete set), rather than the continuum of LP solutions. This principle underlies the 2299: 5441:(ILP) problem. In contrast to linear programming, which can be solved efficiently in the worst case, integer programming problems are in many practical situations (those with bounded variables) 2795: 832: 3470:

theorem states that the objective function value of the dual at any feasible solution is always greater than or equal to the objective function value of the primal at any feasible solution. The

171: 519:

for details). Industries that use linear programming models include transportation, energy, telecommunications, and manufacturing. It has proven useful in modeling diverse types of problems in

2448: 1424: 8006: 4186:

and then walking along a path on the edges of the polytope to vertices with non-decreasing values of the objective function until an optimum is reached for sure. In many practical problems, "

7203: 5378:

of the 21st century. In Smale's words, the third version of the problem "is the main unsolved problem of linear programming theory." While algorithms exist to solve linear programming in

468: 498: 7585: 5316: 5254: 5140: 1701: 5764:

described in this section, variables are not constrained to be integers but rather one has proven somehow that the continuous problem always has an integral optimal value (assuming

5732: 5633: 5579: 5042: 4201:

are taken. The simplex algorithm has been proved to solve "random" problems efficiently, i.e. in a cubic number of steps, which is similar to its behavior on practical problems.

2516: 6158:

A popular modeling language for large-scale linear, mixed integer and nonlinear optimisation with a free student limited version available (500 variables and 500 constraints).

2855: 1481: 4542: 7560:

Kantorovich, L. V. (1940). "Об одном эффективном методе решения некоторых классов экстремальных проблем" [A new method of solving some classes of extremal problems].

3811:

It is possible to obtain an optimal solution to the dual when only an optimal solution to the primal is known using the complementary slackness theorem. The theorem states:

1718: 4721: 2346: 2324: 359: 337: 315: 4799: 4400: 4488: 6220:

A nonlinear solver adjusted to spreadsheets in which function evaluations are based on the recalculating cells. Basic version available as a standard add-on for Excel.

5192: 5166: 5009: 4315: 6269:

discrete variables. It also has a statistical sampling API to integrate Monte-Carlo simulations into an optimization framework. It has an algebraic modeling language (

5078: 4444: 4078:

Otherwise, if a feasible solution exists and if the constraint set is bounded, then the optimum value is always attained on the boundary of the constraint set, by the

4983: 4959: 4935: 4760: 6678: 5660: 1048:{\displaystyle {\begin{matrix}a_{11}x_{1}+a_{12}x_{2}&\leq b_{1}\\a_{21}x_{1}+a_{22}x_{2}&\leq b_{2}\\a_{31}x_{1}+a_{32}x_{2}&\leq b_{3}\\\end{matrix}}} 3624: 1242:{\displaystyle \max\{\,\mathbf {c} ^{\mathsf {T}}\mathbf {x} \mid \mathbf {x} \in \mathbb {R} ^{n}\land A\mathbf {x} \leq \mathbf {b} \land \mathbf {x} \geq 0\,\}} 4053:

An optimal solution need not exist, for two reasons. First, if the constraints are inconsistent, then no feasible solution exists: For instance, the constraints

5680: 4602: 4582: 4562: 2882: 2366: 2105: 383: 8337: 7837:(carefully written account of primal and dual simplex algorithms and projective algorithms, with an introduction to integer linear programming – featuring the 41:

A pictorial representation of a simple linear program with two variables and six inequalities. The set of feasible solutions is depicted in yellow and forms a

6071:

and its own "lp" format, as well as custom formats through its "eXternal Language Interface" (XLI). Translating between model formats is also possible.

8940: 5467:

There are however some important subclasses of IP and MIP problems that are efficiently solvable, most notably problems where the constraint matrix is

2857:

are (non-negative) slack variables, representing in this example the unused area, the amount of unused fertilizer, and the amount of unused pesticide.

8208: 7539: 624:

independently developed general linear programming formulation to use for planning problems in the US Air Force. In 1947, Dantzig also invented the

7790: 594:

late 1930s eventually became foundational to the broader acceptance and utilization of linear programming in optimizing decision-making processes.

6274: 4001:

the dual (shadow) price non-negativity constraint requirement, i.e., the price is not zero, then there must be scarce supplies (no "leftovers").

392: 8332: 7714:

Fukuda, Komei; Terlaky, Tamás (1997). Thomas M. Liebling; Dominique de Werra (eds.). "Criss-cross methods: A fresh view on pivot algorithms".

7524: 4812: 5345: 3617: 4111:

denote the number of variables. Then the fundamental theorem of linear inequalities implies (for feasible problems) that for every vertex

1073: 7562: 5879: 5833: 5768:

is integral), and this optimal value may be found efficiently since all polynomial-size linear programs can be solved in polynomial time.

4140: 69:(not shown). The linear programming problem is to find a point on the polyhedron that is on the plane with the highest possible value. 606: 507:

Linear programming can be applied to various fields of study. It is widely used in mathematics and, to a lesser extent, in business,

5080:

time. In a followup work by Lee, Song and Zhang, they reproduce the same result via a different method. These two algorithms remain

3799:

is another example of a covering LP. In this case, there is one constraint for each vertex of the graph and one variable for each

8826: 8346: 3610: 628:

that, for the first time efficiently, tackled the linear programming problem in most cases. When Dantzig arranged a meeting with

8933: 7994:

Chapter 4: Linear Programming: pp. 63–94. Describes a randomized half-plane intersection algorithm for linear programming.

7769:. Oxford Lecture Series in Mathematics and its Applications. Vol. 4. New York: Oxford University Press. pp. 103–144. 6297:

A general-purpose and matrix-oriented programming-language for numerical computing. Linear programming in MATLAB requires the

2622: 2529: 6138:

appropriate solver such as CPLEX or similar, to solve the optimization problem at hand. Academic licenses are free of charge.

4615: 8201: 8110: 8091: 8016: 7987: 7913: 7802: 7704: 6839: 6701: 6581: 6553:

Kemeny, J. G.; Morgenstern, O.; Thompson, G. L. (1956). "A Generalization of the von Neumann Model of an Expanding Economy".

6371:

OPTMODEL; and a variety of vertical solutions aimed at specific problems/markets, all of which are fully integrated with the

5757:

described in the previous section, variables are forcibly constrained to be integers, and this problem is NP-hard in general,

5749:

Terminology is not consistent throughout the literature, so one should be careful to distinguish the following two concepts,

1574: 1494: 8028: 6818: 6367:

A suite of solvers for Linear, Integer, Nonlinear, Derivative-Free, Network, Combinatorial and Constraint Optimization; the

6201:

Popular solver with an API for several programming languages, and also has a modelling language and works with AIMMS, AMPL,

1252:

Other forms, such as minimization problems, problems with constraints on alternative forms, and problems involving negative

8978: 5928:

A general-purpose constraint integer programming solver with an emphasis on MIP. Compatible with Zimpl modelling language.

2262: 727:

is the usual and most intuitive form of describing a linear programming problem. It consists of the following three parts:

6431: 2715: 742: 653:. However, it takes only a moment to find the optimum solution by posing the problem as a linear program and applying the 8907: 8369: 6466: 8421: 8282: 6609: 2387: 1363: 646: 4187: 8988: 8926: 8389: 8075: 8040: 7235: 7118: 6387: 6234: 6202: 6191:

API to MATLAB and Python. Solve example Linear Programming (LP) problems through MATLAB, Python, or a web-interface.

5534:

if it has at least one optimal solution which is integral, i.e., made of only integer values. Likewise, a polyhedron

5454: 528: 520: 440: 8500: 8194: 5956: 5797: 473: 8439: 6817:

M. Grundmann; V. Kwatra; I. Essa (2011). "Auto-directed video stabilization with robust L1 optimal camera paths".

657:. The theory behind linear programming drastically reduces the number of possible solutions that must be checked. 7931: 7672: 6451: 5662:

with integer coordinates. As observed by Edmonds and Giles in 1977, one can equivalently say that the polyhedron

1428:(maximize the revenue (the total wheat sales plus the total barley sales) – revenue is the "objective function") 571: 6917:(1997). Thomas M. Liebling; Dominique de Werra (eds.). "Criss-cross methods: A fresh view on pivot algorithms". 6008:

An incremental constraint solving toolkit that efficiently solves systems of linear equalities and inequalities

8973: 8777: 7062: 6731: 5464:(MIP or MILP) problem. These are generally also NP-hard because they are even more general than ILP programs. 5259: 3800: 3572: 3337:, which provides an upper bound to the optimal value of the primal problem. In matrix form, we can express the 17: 5197: 5083: 2079:

to replace inequalities with equalities in the constraints. The problems can then be written in the following

9061: 8983: 8885: 8505: 5887: 5818: 5743: 3757: 1654: 5693: 5594: 1324:

be the selling price of barley, per hectare. If we denote the area of land planted with wheat and barley by

716:

and minimize costs with limited resources. Google also uses linear programming to stabilize YouTube videos.

9066: 9056: 8821: 8789: 7525:

http://www.in-ter-trans.eu/resources/Zesch_Hellingrath_2010_Integrated+Production-Distribution+Planning.pdf

6331:

A solver for large scale optimization with API for several languages (C++, java, .net, Matlab and python).

6270: 5918: 5418: 4363:

for linear programming. Karmarkar's algorithm improved on Khachiyan's worst-case polynomial bound (giving

3796: 691: 7014:

Roos, C. (1990). "An exponential example for Terlaky's pivoting rule for the criss-cross simplex method".

5537: 680:

Linear programming is a widely used field of optimization for several reasons. Many practical problems in

605:

formulated classical economic problems as linear programs. Kantorovich and Koopmans later shared the 1975

89: 49:. The optimum of the linear cost function is where the red line intersects the polygon. The red line is a 9051: 8870: 8495: 7536: 6368: 6110:

solver which uses branch and bound algorithm) has publicly available source code but is not open source.

6000: 5014: 4156:

of possible values for those variables. In the two-variable case this region is in the shape of a convex

2462: 613:

also formulated transportation problems as linear programs and gave a solution very similar to the later

8949: 8816: 8772: 8665: 8394: 8374: 7838: 6342: 6321:

A general-purpose programming-language for mathematics, including symbolic and numerical capabilities.

6026: 5738: 2807: 1803:{\displaystyle {\begin{bmatrix}S_{1}&S_{2}\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}} 1440: 130: 7646:. Stanford Business Books, Stanford University Press, Stanford, California, 2003. (Selected papers by 5471:

and the right-hand sides of the constraints are integers or – more general – where the system has the

4493: 684:

can be expressed as linear programming problems. Certain special cases of linear programming, such as

511:, and some engineering problems. There is a close connection between linear programs, eigenequations, 9020: 8555: 8217: 7849: 7676: 6446: 6311:

A WYSIWYG math editor. It has functions for solving both linear and nonlinear optimization problems.

6064: 5933: 5895: 5841: 5773: 5746:

is integral, then it is the desired description of the convex hull of feasible (integral) solutions.

5503: 100: 93: 8740: 8186: 7369: 6625: 1352:. This problem can be expressed with the following linear programming problem in the standard form: 1264: 8602: 7728: 6931: 6503: 6476: 6252: 5952: 5883: 5379: 5357: 4346: 4197:

is quite efficient and can be guaranteed to find the global optimum if certain precautions against

3761: 118: 7546:

OptimJ used in an Approximate Subgame-Perfect Equilibrium Computation Technique for Repeated Games

5913:

An open-source modeling language for large-scale linear, mixed integer and nonlinear optimization

4697: 2329: 2307: 342: 320: 298: 37: 8784: 8683: 8399: 7576: 4765: 4366: 4334: 3773: 3769: 3560: 708:

and its generalizations. Likewise, linear programming was heavily used in the early formation of

7782: 5460:

If only some of the unknown variables are required to be integers, then the problem is called a

4457: 8875: 8860: 8750: 8628: 8277: 8254: 8221: 7723: 7680: 7364: 6926: 6461: 6436: 5777: 5472: 5171: 5145: 4988: 4281: 3785: 1253: 610: 8176: 5366:

Does LP admit a polynomial-time algorithm in the real number (unit cost) model of computation?

5047: 4413: 4355:

However, Khachiyan's algorithm inspired new lines of research in linear programming. In 1984,

9025: 8968: 8764: 8730: 8633: 8575: 8456: 8262: 8242: 7218:

Vaidya, Pravin M. (1989). "Speeding-up linear programming using fast matrix multiplication".

6497: 6481: 6336: 5944: 5891: 5875: 5837: 5829: 5387: 5363:

Does LP admit a strongly polynomial-time algorithm to find a strictly complementary solution?

4968: 4962: 4944: 4938: 4920: 4264: 4243: 4222: 669: 134: 31: 7687:

Edmonds, Jack; Giles, Rick (1977). "A Min-Max Relation for Submodular Functions on Graphs".

6084:

A library for incrementally solving systems of linear equations with various goal functions

5413:

any two vertices on the LP polytope. As a result, we are interested in knowing the maximum

5397:

was recently disproved for higher dimensions, it still leaves the following questions open.

4730: 664:

in 1979, but a larger theoretical and practical breakthrough in the field came in 1984 when

9030: 8811: 8638: 8550: 7812: 7774: 7745: 7091: 7035: 6948: 6298: 6163: 6114: 5780:. Other specific well-known integral LPs include the matching polytope, lattice polyhedra, 5638: 5482: 5433:

If all of the unknown variables are required to be integers, then the problem is called an

3781: 3579: 1280:, to be planted with either wheat or barley or some combination of the two. The farmer has 1138: 686: 386: 8918: 8148: 7527:

OptimJ used in an optimization model for mixed-model assembly lines, University of Münster

6301:

in addition to the base MATLAB product; available routines include INTLINPROG and LINPROG

8: 8880: 8745: 8698: 8688: 8540: 8528: 8341: 8324: 8229: 7945: 6441: 6426: 6107: 5434: 5375: 4239: 3792: 3584: 3501: 3324: 713: 681: 650: 516: 617:. Hitchcock had died in 1957, and the Nobel Memorial Prize is not awarded posthumously. 9002: 8615: 8560: 8351: 8267: 7879: 7749: 7621: 7423: 7331: 7306: 7281: 7256: 7095: 7039: 6952: 6845: 6799: 6421: 6097:

A programming language and software environment for statistical computing and graphics

5665: 5511: 5468: 4587: 4567: 4547: 4356: 2867: 2351: 2090: 665: 578: 550: 532: 434: 368: 107: 85: 84:, is a method to achieve the best outcome (such as maximum profit or lowest cost) in a 53:

of the cost function, and the arrow indicates the direction in which we are optimizing.

7696: 7378: 9010: 8623: 8301: 8166: 8106: 8087: 8071: 8036: 8012: 7983: 7972: 7909: 7798: 7700: 7668: 7647: 7415: 7231: 7099: 7079: 6835: 6782:

Narendra Karmarkar (1984). "A New Polynomial-Time Algorithm for Linear Programming".

6737: 6727: 6697: 6674: 6605: 6577: 6574:

General Equilibrium and Structural Dynamics: Perspectives of New Structural Economics

6513: 5523: 5394: 4360: 4175: 4145: 4128: 4080: 4023: 3777: 3596: 3543: 3531: 2070: 654: 625: 602: 566:

The problem of solving a system of linear inequalities dates back at least as far as

115: 7222:. 30th Annual Symposium on Foundations of Computer Science. FOCS. pp. 332–337. 7043: 6849: 6038:

and numerous (15) third-party wrappers for other languages. Specialist support for

660:

The linear programming problem was first shown to be solvable in polynomial time by

8703: 8693: 8597: 8474: 8379: 8361: 8314: 8225: 8002: 7998: 7883: 7871: 7820: 7753: 7733: 7692: 7613: 7405: 7374: 7223: 7071: 7023: 6956: 6936: 6827: 6803: 6791: 6670: 6492: 6405: 6282: 6243: 5776:. There are other general methods including the integer decomposition property and 5497: 5487: 5383: 4326: 4322: 4318: 4182:

in 1947, solves LP problems by constructing a feasible solution at a vertex of the

4096: 4039: 3638: 3591: 3536: 661: 629: 582: 560: 512: 66: 7778: 7762: 7507: 7486: 6914: 6169:

solver to match the problem. It also accepts other engines as plug-ins, including

4230:

for linear programming. Both algorithms visit all 2 corners of a (perturbed)

92:. Linear programming is a special case of mathematical programming (also known as 8719: 8171: 8131: 8122: 7979: 7958: 7808: 7770: 7741: 7543: 7087: 7031: 6944: 6471: 6214: 5781: 4724: 4267: 4227: 4206: 4153: 4086: 4027: 4019: 4015: 3695: 632:

to discuss his simplex method, von Neumann immediately conjectured the theory of

501: 142: 126: 122: 111: 4321:

solved this long-standing complexity issue in 1979 with the introduction of the

4061: ≤ 1 cannot be satisfied jointly; in this case, we say that the LP is 590:

while considering critical constraints such as costs and resource availability.

570:, who in 1827 published a method for solving them, and after whom the method of 153:

where this function has the largest (or smallest) value if such a point exists.

9014: 8707: 8592: 8479: 8413: 8384: 7901: 7888:(Invited survey, from the International Symposium on Mathematical Programming.) 7057: 6655: 6486: 6456: 6356:

A Java-based modeling language for optimization with a free version available.

6174: 5938: 5923: 5854: 5737:

Integral linear programs are of central importance in the polyhedral aspect of

5492: 5414: 4210: 4179: 4157: 4047: 4035: 3471: 2075: 709: 621: 614: 567: 157: 137:, each of which is defined by a linear inequality. Its objective function is a 7962:, Universitext, Springer-Verlag, 2001. (Problems from Padberg with solutions.) 6831: 5772:

One common way of proving that a polyhedron is integral is to show that it is

5321: 9045: 8865: 8849: 7967: 7604:

Bland, Robert G. (1977). "New Finite Pivoting Rules for the Simplex Method".

7586:

Maximization of a linear function of variables subject to linear inequalities

7465: 7419: 7303:

Solving Empirical Risk Minimization in the Current Matrix Multiplication Time

7083: 7060:(1 June 1987). "Karmarkar's algorithm and its place in applied mathematics". 6401: 6287:

A general-purpose programming-language for symbolic and numerical computing.

5371: 4119:(or fewer) inequality constraints from the LP such that, when we treat those 4043: 4031: 7441: 7227: 6741: 5334: 4985:

is (roughly) defined to be the largest number such that one can multiply an

8803: 8309: 8023:

A6: MP1: INTEGER PROGRAMMING, pg.245. (computer science, complexity theory)

7862:

Todd, Michael J. (February 2002). "The many facets of linear programming".

6910: 6508: 6068: 6047: 6039: 5908: 4330: 4270:

algorithm ever found for linear programming. To solve a problem which has

4149:

In a linear programming problem, a series of linear constraints produces a

3567: 3467: 3334: 2080: 556: 362: 7875: 7410: 7393: 7352: 7253:

Efficient inverse maintenance and faster algorithms for linear programming

6760:

Leonid Khachiyan (1979). "A Polynomial Algorithm for Linear Programming".

1338:

respectively, then profit can be maximized by choosing optimal values for

546: 426:{\displaystyle \mathbf {x} \mapsto \mathbf {c} ^{\mathsf {T}}\mathbf {x} } 8890: 8272: 7617: 7577:

The distribution of a product from several sources to numerous localities

6380: 6316: 6013: 5869: 5823: 4612:

In 2015, Lee and Sidford showed that linear programming can be solved in

3765: 3548: 637: 138: 6148:

A commercial edition of the copyleft licensed library. C++, C#, Python.

4910:{\displaystyle {\tilde {O}}((n^{\omega }+n^{2.5-\alpha /2}+n^{2+1/6})L)} 8103:

Networks in Action; Text and Computer Exercises in Network Optimization

7737: 7625: 7075: 7027: 6940: 6795: 6372: 6361: 6341:

A collection of mathematical and statistical routines developed by the

4325:. The convergence analysis has (real-number) predecessors, notably the 4150: 3555: 62: 61:

A closed feasible region of a problem with three variables is a convex

8008:

Computers and Intractability: A Guide to the Theory of NP-Completeness

7537:

http://www.aaai.org/ocs/index.php/AAAI/AAAI10/paper/viewFile/1769/2076

7427: 7207:. 28th Annual IEEE Symposium on Foundations of Computer Science. FOCS. 5682:

is integral if for every bounded feasible integral objective function

8216: 7997: 7965: 6186: 6089: 5502:

if the problem has some extra structure, it may be possible to apply

5401:

Are there pivot rules which lead to polynomial-time simplex variants?

4231: 4194: 1256:

can always be rewritten into an equivalent problem in standard form.

515:'s general equilibrium model, and structural equilibrium models (see 508: 146: 50: 8047:(elementary introduction for mathematicians and computer scientists) 7326:

Jiang, Shunhua; Song, Zhao; Weinstein, Omri; Zhang, Hengjie (2020).

1124:{\displaystyle {\begin{matrix}x_{1}\geq 0\\x_{2}\geq 0\end{matrix}}} 8292: 8138: 7842: 7336: 7311: 7286: 7261: 6534:

von Neumann, J. (1945). "A Model of General Economic Equilibrium".

6055: 5966: 5342:

Does linear programming admit a strongly polynomial-time algorithm?

4183: 4066: 601:. About the same time as Kantorovich, the Dutch-American economist 150: 46: 8181: 4762:

represents the number of non-zero elements, and it remains taking

2376:

The example above is converted into the following augmented form:

65:. The surfaces giving a fixed value of the objective function are 8998: 8612: 7691:. Annals of Discrete Mathematics. Vol. 1. pp. 185–204. 7280:. 51st Annual ACM Symposium on the Theory of Computing. STOC'19. 7278:

Solving Linear Programs in the Current Matrix Multiplication Time

6576:(in Chinese). Beijing: Economic Science Press. pp. 122–125. 6306: 5478:

Advanced algorithms for solving integer linear programs include:

5442: 1277: 524: 42: 5791: 5784:

polyhedra, and the intersection of two generalized polymatroids/

7394:"A Monotonic Build-Up Simplex Algorithm for Linear Programming" 6395: 6351: 6292: 6225: 6206: 6170: 6143: 5987: 5874:

Open-source modeling language with solvers for large-scale LP,

4804: 1302:

kilograms of pesticide, while every hectare of barley requires

104: 6034:

GNU Linear Programming Kit, an LP/MILP solver with a native C

5194:. The result due to Jiang, Song, Weinstein and Zhang improved 7856:(Corrected republication with a new preface ed.). Dover. 7637:. Algorithms and Combinatorics. Vol. 1. Springer-Verlag. 6326: 6263: 6196: 6178: 6132: 6103: 5943:

An open-source suite of optimization algorithms to solve LP,

5903: 3760:

of a combinatorial problem and are important in the study of

8100: 6816: 6432:

Expected shortfall § Optimization of expected shortfall

3989:-th variable of the dual is equal to zero. Likewise, if the 3891:) denote the corresponding primal slack variables, and let ( 8948: 6153: 6076: 6043: 5948: 5864: 5849: 5404:

Do all polytopal graphs have polynomially bounded diameter?

5322:

Comparison of interior-point methods and simplex algorithms

4258: 4141:

List of numerical analysis topics § Linear programming

4073: 3474:

theorem states that if the primal has an optimal solution,

598: 30:

For the retronym referring to television broadcasting, see

7959:

Linear Optimization and Extensions: Problems and Solutions

7797:. New York: John Wiley & Sons, Inc. pp. xix+482. 7589:, 1947. Published pp. 339–347 in T.C. Koopmans (ed.): 6626:"Linear programming | Definition & Facts | Britannica" 4809:

In 2019, Cohen, Lee and Song improved the running time to

8081: 8054:, Second Edition, Springer-Verlag, 2006. (Graduate level) 6599: 6552: 6035: 3922:

are optimal for their respective problems if and only if

2697:{\displaystyle P_{1}\cdot x_{1}+P_{2}\cdot x_{2}+x_{5}=P} 2604:{\displaystyle F_{1}\cdot x_{1}+F_{2}\cdot x_{2}+x_{4}=F} 99:

More formally, linear programming is a technique for the

57: 7580:, Journal of Mathematics and Physics, 20, 1941, 224–230. 7220:

30th Annual Symposium on Foundations of Computer Science

4687:{\displaystyle {\tilde {O}}((nnz(A)+d^{2}){\sqrt {d}}L)} 4107:. The reason for this choice of name is as follows. Let 1288:

kilograms of pesticide. Every hectare of wheat requires

7508:"COR@L – Computational Optimization Research At Lehigh" 7325: 6656:"Reminiscences about the origins of linear programming" 5370:

This closely related set of problems has been cited by

3985:-th slack variable of the primal is not zero, then the 1636:{\displaystyle P_{1}\cdot x_{1}+P_{2}\cdot x_{2}\leq P} 1556:{\displaystyle F_{1}\cdot x_{1}+F_{2}\cdot x_{2}\leq F} 3914:) denote the corresponding dual slack variables. Then 3222: 3178: 3086: 2898: 2225: 2185: 2121: 2023: 1980: 1943: 1900: 1824: 1765: 1727: 1078: 856: 504:

over which the objective function is to be optimized.

156:

Linear programs are problems that can be expressed in

7854:

Combinatorial Optimization: Algorithms and Complexity

7671:

and interior-point algorithms, large-scale problems,

7121: 5696: 5668: 5641: 5597: 5540: 5510:

Such integer-programming algorithms are discussed by

5262: 5200: 5174: 5148: 5086: 5050: 5017: 4991: 4971: 4947: 4923: 4815: 4768: 4733: 4700: 4618: 4590: 4570: 4550: 4496: 4460: 4416: 4369: 4284: 3993:-th slack variable of the dual is not zero, then the 2892: 2870: 2810: 2718: 2625: 2532: 2465: 2390: 2354: 2332: 2310: 2294:{\displaystyle \mathbf {x} \geq 0,\mathbf {s} \geq 0} 2265: 2115: 2093: 2065:

Linear programming problems can be converted into an

1818: 1721: 1657: 1577: 1497: 1443: 1366: 1152: 1076: 854: 745: 636:

by realizing that the problem he had been working in

476: 443: 395: 371: 345: 323: 301: 169: 8729: 8084:

Linear and Integer Optimization: Theory and Practice

8060:

Combinatorial optimization: polyhedra and efficiency

7815:. (comprehensive reference to classical approaches). 7353:"Pivot versus interior point methods: Pros and cons" 7276:

Cohen, Michael B.; Lee, Yin-Tat; Song, Zhao (2018).

6602:

Linear and Integer Optimization: Theory and Practice

5336: 4454:

In 1989, Vaidya developed an algorithm that runs in

4340: 2790:{\displaystyle x_{1},x_{2},x_{3},x_{4},x_{5}\geq 0.} 1273:

Suppose that a farmer has a piece of farm land, say

827:{\displaystyle f(x_{1},x_{2})=c_{1}x_{1}+c_{2}x_{2}} 88:

whose requirements and objective are represented by

8057: 7115:An algorithm for linear programming which requires 6691: 6595: 6593: 5995:An LP solver from ALGLIB project (C++, C#, Python) 4410:In 1987, Vaidya proposed an algorithm that runs in 3329:Every linear programming problem, referred to as a 8050:Cornelis Roos, Tamás Terlaky, Jean-Philippe Vial, 7971: 7848: 7833:Linear Optimization and Extensions, Second Edition 7763:"3 A computational view of interior point methods" 7391: 7197: 7002: 6781: 5726: 5674: 5654: 5627: 5573: 5310: 5248: 5186: 5160: 5134: 5072: 5036: 5003: 4977: 4953: 4929: 4909: 4793: 4754: 4715: 4686: 4596: 4576: 4556: 4536: 4482: 4438: 4394: 4309: 4123:constraints as equalities, the unique solution is 3307: 2876: 2849: 2789: 2696: 2603: 2510: 2442: 2360: 2340: 2318: 2293: 2250: 2099: 2049: 1802: 1695: 1635: 1555: 1475: 1418: 1241: 1123: 1047: 826: 597:Kantorovich's work was initially neglected in the 492: 462: 425: 377: 353: 331: 309: 284: 7593:, New York-London 1951 (Wiley & Chapman-Hall) 6722:Dantzig, George B.; Thapa, Mukund Narain (1997). 6653: 5528:A linear program in real variables is said to be 4607: 4115:of the LP feasible region, there exists a set of 4014:Geometrically, the linear constraints define the 4009: 2443:{\displaystyle S_{1}\cdot x_{1}+S_{2}\cdot x_{2}} 1419:{\displaystyle S_{1}\cdot x_{1}+S_{2}\cdot x_{2}} 9043: 6905: 6903: 6901: 6759: 6590: 5828:Open-source library for solving large-scale LP, 5700: 5601: 5587:if for all bounded feasible objective functions 5330: 1153: 8026: 7635:The Simplex Algorithm: A Probabilistic Analysis 7600:. Oxford Science, 1996. (Collection of surveys) 7301:Lee, Yin-Tat; Song, Zhao; Zhang, Qiuyi (2019). 7198:{\displaystyle {O}(((m+n)n^{2}+(m+n)^{1.5}n)L)} 5859:Google's open-source linear programming solver 4544:arithmetic operations in the worst case, where 4169: 3520: 389:. The function whose value is to be maximized ( 145:defined on this polytope. A linear programming 8143:Interior Point Algorithms: Theory and Analysis 8052:Interior Point Methods for Linear Optimization 7894:Linear Programming: Foundations and Extensions 7760: 7591:Activity Analysis of Production and Allocation 6777: 6775: 3478:, then the dual also has an optimal solution, 2060: 463:{\displaystyle A\mathbf {x} \leq \mathbf {b} } 8934: 8202: 8155:, Springer-Verlag, New York, 1994. (Geometry) 7713: 7661:Dantzig, George B.; Thapa, Mukund N. (2003). 7653:George B. Dantzig and Mukund N. Thapa. 1997. 7392:Anstreicher, Kurt M.; Terlaky, Tamás (1994). 6909: 6898: 6755: 6753: 6751: 6649: 6647: 6645: 5792:Solvers and scripting (programming) languages 4490:time. Formally speaking, the algorithm takes 4103:The vertices of the polytope are also called 3997:-th variable of the primal is equal to zero. 3973: = 1, 2, ... , 3946: = 1, 2, ... , 3756:Covering and packing LPs commonly arise as a 3618: 3512: 493:{\displaystyle \mathbf {x} \geq \mathbf {0} } 8763: 7686: 7660: 7350: 7328:Faster Dynamic Matrix Inverse for Faster LPs 7300: 7275: 7255:. FOCS '15 Foundations of Computer Science. 6879: 6721: 6685: 6273:) and allows modeling within a spreadsheet ( 6205:, MPL, OpenOpt, OPL Development Studio, and 5721: 5697: 5622: 5598: 5568: 5547: 5346:(more unsolved problems in computer science) 4805:Current matrix multiplication time algorithm 4164: 1236: 1156: 8241: 7663:Linear Programming 2: Theory and Extensions 7559: 6772: 6696:. John Wiley & Sons. pp. 221–222. 6533: 5517: 4221:Like the simplex algorithm of Dantzig, the 3776:are packing LPs. The LP relaxations of the 733:linear (or affine) function to be maximized 8941: 8927: 8209: 8195: 8123:Model Building in Mathematical Programming 8033:Understanding and Using Linear Programming 7767:Advances in linear and integer programming 7598:Advances in Linear and Integer Programming 7305:. Conference on Learning Theory. COLT'19. 7250: 6889: 6887: 6748: 6642: 3806: 3625: 3611: 2326:are the newly introduced slack variables, 8455: 7891: 7783:at McMaster University website of Terlaky 7727: 7632: 7409: 7368: 7335: 7310: 7285: 7260: 6969: 6930: 5788:-polymatroids – e.g. see Schrijver 2003. 5311:{\displaystyle {\tilde {O}}(n^{2+1/18}L)} 3764:. For example, the LP relaxations of the 3216: 2069:in order to apply the common form of the 1974: 1235: 1192: 1159: 672:for solving linear-programming problems. 607:Nobel Memorial Prize in Economic Sciences 8443:Optimization computes maxima and minima. 8068:Theory of Linear and Integer Programming 7956:Dmitris Alevras and Manfred W. Padberg, 7900: 7357:European Journal of Operational Research 6862: 6694:Theory of Linear and Integer Programming 5249:{\displaystyle {\tilde {O}}(n^{2+1/6}L)} 5135:{\displaystyle {\tilde {O}}(n^{2+1/6}L)} 4449: 4405: 4259:Ellipsoid algorithm, following Khachiyan 4216: 4144: 4074:Optimal vertices (and rays) of polyhedra 1263: 577:In the late 1930s, Soviet mathematician 555: 545: 56: 36: 8950:Complementarity problems and algorithms 8527: 8101:Gerard Sierksma; Diptesh Ghosh (2010). 7830: 7761:Gondzio, Jacek; Terlaky, Tamás (1996). 6893: 6884: 6875: 6873: 6871: 6489:used to solve optimal stopping problems 3504:for details and several more examples. 1696:{\displaystyle x_{1}\geq 0,x_{2}\geq 0} 14: 9044: 7217: 7112: 7056: 7050: 6604:(3rd ed.). CRC Press. p. 1. 5727:{\displaystyle \{\max cx\mid x\in P\}} 5628:{\displaystyle \{\max cx\mid x\in P\}} 3405:An alternative primal formulation is: 2140: 1168: 412: 209: 8922: 8847: 8663: 8639:Principal pivoting algorithm of Lemke 8526: 8454: 8240: 8190: 7789: 7779:Postscript file at website of Gondzio 7673:decomposition following Dantzig–Wolfe 7639:(Average behavior on random problems) 7603: 7351:Illés, Tibor; Terlaky, Tamás (2002). 7251:Lee, Yin-Tat; Sidford, Aaron (2015). 6991: 6985: 6726:. New York: Springer. p. xxvii. 27:Method to solve optimization problems 8974:Linear complementarity problem (LCP) 8182:Benchmarks For Optimisation Software 8082:Gerard Sierksma; Yori Zwols (2015). 7861: 7825:Linear Programs and Related Problems 7442:"lp_solve reference guide (5.5.2.5)" 7013: 7007: 6980: 6974: 6868: 6717: 6715: 6713: 6600:Gerard Sierksma; Yori Zwols (2015). 5574:{\displaystyle P=\{x\mid Ax\geq 0\}} 5337:Unsolved problem in computer science 4038:; similarly, a linear function is a 2073:. This form introduces non-negative 1136:The problem is usually expressed in 317:are the variables to be determined, 8584: 8167:Guidance On Formulating LP Problems 6467:Linear-fractional programming (LFP) 6050:modelling language and translator. 5742:Conversely, if we can prove that a 5428: 5037:{\displaystyle n\times n^{\alpha }} 4337:by Arkadi Nemirovski and D. Yudin. 4278:input bits, this algorithm runs in 2511:{\displaystyle x_{1}+x_{2}+x_{3}=L} 1320:be the selling price of wheat and S 24: 8848: 8438: 8283:Successive parabolic interpolation 8145:, Wiley. (Advanced graduate-level) 8132:Primal-Dual Interior-Point Methods 7966:de Berg, Mark; van Kreveld, Marc; 7925: 7716:Mathematical Programming, Series B 7655:Linear programming 1: Introduction 7606:Mathematics of Operations Research 6996: 6919:Mathematical Programming, Series B 6681:from the original on May 20, 2015. 6571: 6500:, a superset of linear programming 5462:mixed integer (linear) programming 25: 9078: 8664: 8603:Projective algorithm of Karmarkar 8172:Mathematical Programming Glossary 8160: 8126:, Fifth Edition, 2013. (Modeling) 6710: 6067:solver featuring support for the 4341:Projective algorithm of Karmarkar 4249: 3641:is a linear program of the form: 3333:problem, can be converted into a 2850:{\displaystyle x_{3},x_{4},x_{5}} 2368:is the variable to be maximized. 1476:{\displaystyle x_{1}+x_{2}\leq L} 8598:Ellipsoid algorithm of Khachiyan 8501:Sequential quadratic programming 8338:Broyden–Fletcher–Goldfarb–Shanno 6654:George B. Dantzig (April 1982). 4584:is the number of variables, and 4537:{\displaystyle O((n+d)^{1.5}nL)} 4274:variables and can be encoded in 3698:, a linear program of the form: 2348:are the decision variables, and 2334: 2312: 2281: 2267: 2236: 2205: 2196: 2168: 2161: 2134: 1705:(cannot plant a negative area). 1225: 1217: 1209: 1183: 1175: 1162: 719: 486: 478: 456: 448: 419: 406: 397: 347: 325: 303: 271: 263: 245: 237: 216: 203: 184: 129:, which is a set defined as the 8070:. John Wiley & sons, 1998, 7970:; Schwarzkopf, Otfried (2000). 7530: 7518: 7500: 7479: 7458: 7434: 7385: 7344: 7319: 7294: 7269: 7244: 7211: 7106: 6963: 6856: 6810: 6452:Least-squares spectral analysis 3694:The dual of a covering LP is a 8556:Reduced gradient (Frank–Wolfe) 8117:(linear optimization modeling) 7827:, Academic Press. (elementary) 7689:Studies in Integer Programming 7667:(Comprehensive, covering e.g. 7633:Borgwardt, Karl-Heinz (1987). 7466:"External Language Interfaces" 7192: 7186: 7174: 7161: 7145: 7133: 7130: 7127: 7063:The Mathematical Intelligencer 6618: 6565: 6546: 6536:The Review of Economic Studies 6527: 5455:Karp's 21 NP-complete problems 5305: 5275: 5269: 5243: 5213: 5207: 5129: 5099: 5093: 5067: 5054: 4904: 4898: 4831: 4828: 4822: 4788: 4772: 4749: 4743: 4707: 4681: 4668: 4652: 4646: 4634: 4631: 4625: 4608:Input sparsity time algorithms 4564:is the number of constraints, 4531: 4516: 4503: 4500: 4477: 4464: 4433: 4420: 4389: 4373: 4304: 4288: 4010:Existence of optimal solutions 3841:) is primal feasible and that 3521:Covering/packing-problem pairs 775: 749: 401: 13: 1: 8886:Spiral optimization algorithm 8506:Successive linear programming 7892:Vanderbei, Robert J. (2001). 7697:10.1016/S0167-5060(08)70734-9 7552: 7379:10.1016/S0377-2217(02)00061-9 7003:Papadimitriou & Steiglitz 6106:(Mixed Integer Optimizer, an 5744:linear programming relaxation 5376:18 greatest unsolved problems 5331:Open problems and recent work 4134: 4131:for solving linear programs. 3758:linear programming relaxation 3507: 2860:In matrix form this becomes: 1711:In matrix form this becomes: 1316:kilograms of pesticide. Let S 8624:Simplex algorithm of Dantzig 8496:Augmented Lagrangian methods 8058:Alexander Schrijver (2003). 6692:Alexander Schrijver (1998). 6675:10.1016/0167-6377(82)90043-8 4716:{\displaystyle {\tilde {O}}} 4170:Simplex algorithm of Dantzig 2371: 2341:{\displaystyle \mathbf {x} } 2319:{\displaystyle \mathbf {s} } 1309:kilograms of fertilizer and 1295:kilograms of fertilizer and 1284:kilograms of fertilizer and 633: 433:in this case) is called the 354:{\displaystyle \mathbf {b} } 332:{\displaystyle \mathbf {c} } 310:{\displaystyle \mathbf {x} } 7: 7644:The Basic George B. Dantzig 6663:Operations Research Letters 6516:, used to solve LP problems 6414: 6404:language for simulation of 6369:Algebraic modeling language 6001:Cassowary constraint solver 4794:{\displaystyle O(n^{2.5}L)} 4395:{\displaystyle O(n^{3.5}L)} 4042:, which implies that every 4030:, which implies that every 3751: 2061:Augmented form (slack form) 572:Fourier–Motzkin elimination 10: 9083: 8969:Quadratic programming (QP) 8177:The Linear Programming FAQ 8151:, Chapters 1–3 and 6–7 in 7850:Papadimitriou, Christos H. 7839:traveling salesman problem 7765:. In J. E. Beasley (ed.). 7113:Vaidya, Pravin M. (1987). 6880:Dantzig & Thapa (2003) 6762:Doklady Akademii Nauk SSSR 6343:Numerical Algorithms Group 6021:An LP solver from COIN-OR 5739:combinatorial optimization 5521: 5451:binary integer programming 5439:integer linear programming 5415:graph-theoretical diameter 4483:{\displaystyle O(n^{2.5})} 4344: 4228:polynomial time-complexity 4138: 3513:Covering/packing dualities 3322: 3318: 1360: 1357: 1269:pesticide, not fertilizer) 1259: 541: 29: 8997: 8956: 8903: 8856: 8843: 8827:Push–relabel maximum flow 8802: 8718: 8676: 8672: 8659: 8629:Revised simplex algorithm 8611: 8583: 8569: 8539: 8535: 8522: 8488: 8467: 8463: 8450: 8436: 8412: 8360: 8323: 8300: 8291: 8253: 8249: 8236: 8129:Stephen J. Wright, 1997, 7946:Resources in your library 6832:10.1109/CVPR.2011.5995525 6447:Least absolute deviations 6390:. Free for academic use. 6209:. Free for academic use. 5504:delayed column generation 5388:interior-point techniques 5187:{\displaystyle \alpha =1} 5161:{\displaystyle \omega =2} 5004:{\displaystyle n\times n} 4310:{\displaystyle O(n^{6}L)} 4193:In practice, the simplex 4165:Basis exchange algorithms 4004: 3868:) is dual feasible. Let ( 2383: 94:mathematical optimization 8957:Complementarity Problems 8352:Symmetric rank-one (SR1) 8333:Berndt–Hall–Hall–Hausman 8135:, SIAM. (Graduate level) 7978:(2nd revised ed.). 7906:Approximation Algorithms 7864:Mathematical Programming 7016:Mathematical Programming 6521: 6504:Semidefinite programming 6477:Mathematical programming 6253:IMSL Numerical Libraries 5762:integral linear program, 5518:Integral linear programs 5073:{\displaystyle O(n^{2})} 4961:is the dual exponent of 4439:{\displaystyle O(n^{3})} 4335:approximation algorithms 4105:basic feasible solutions 3762:approximation algorithms 143:affine (linear) function 8964:Linear programming (LP) 8876:Parallel metaheuristics 8684:Approximation algorithm 8395:Powell's dog leg method 8347:Davidon–Fletcher–Powell 8243:Unconstrained nonlinear 7642:Richard W. Cottle, ed. 7596:J. E. Beasley, editor. 7228:10.1109/SFCS.1989.63499 5755:integer linear program, 5447:0–1 integer programming 4978:{\displaystyle \alpha } 4954:{\displaystyle \alpha } 4930:{\displaystyle \omega } 4604:is the number of bits. 4090:(alternatively, by the 3905:, ... , 3859:, ... , 3832:, ... , 3807:Complementary slackness 3788:are also covering LPs. 3770:independent set problem 3573:Maximum independent set 3430:with the corresponding 3370:with the corresponding 2706:(augmented constraint) 2613:(augmented constraint) 2520:(augmented constraint) 675: 581:and American economist 295:Here the components of 8861:Evolutionary algorithm 8444: 7974:Computational Geometry 7852:; Steiglitz, Kenneth. 7681:stochastic programming 7199: 6462:Linear production game 5778:total dual integrality 5728: 5690:of the linear program 5676: 5656: 5629: 5575: 5473:total dual integrality 5380:weakly polynomial time 5312: 5250: 5188: 5162: 5136: 5074: 5038: 5005: 4979: 4955: 4931: 4911: 4795: 4756: 4755:{\displaystyle nnz(A)} 4717: 4688: 4598: 4578: 4558: 4538: 4484: 4440: 4396: 4311: 4161: 3786:dominating set problem 3309: 2878: 2851: 2791: 2698: 2605: 2512: 2444: 2362: 2342: 2320: 2295: 2252: 2101: 2051: 1804: 1697: 1637: 1565:(limit on fertilizer) 1557: 1485:(limit on total area) 1477: 1420: 1270: 1243: 1125: 1062:Non-negative variables 1049: 828: 704:and the importance of 611:Frank Lauren Hitchcock 563: 553: 494: 464: 427: 379: 355: 333: 311: 286: 70: 54: 8634:Criss-cross algorithm 8457:Constrained nonlinear 8442: 8263:Golden-section search 8153:Lectures on Polytopes 8066:Alexander Schrijver, 7876:10.1007/s101070100261 7563:Doklady Akad Sci SSSR 7411:10.1287/opre.42.3.556 7205:arithmetic operations 7200: 6498:Quadratic programming 6482:Nonlinear programming 6337:NAG Numerical Library 5967:Copyleft (reciprocal) 5729: 5677: 5657: 5655:{\displaystyle x^{*}} 5630: 5591:, the linear program 5576: 5522:Further information: 5313: 5251: 5189: 5163: 5137: 5075: 5039: 5006: 4980: 4963:matrix multiplication 4956: 4939:matrix multiplication 4932: 4912: 4796: 4757: 4718: 4689: 4599: 4579: 4559: 4539: 4485: 4450:Vaidya's 89 algorithm 4441: 4406:Vaidya's 87 algorithm 4397: 4347:Karmarkar's algorithm 4312: 4223:criss-cross algorithm 4217:Criss-cross algorithm 4148: 3736:such that the matrix 3679:such that the matrix 3310: 2879: 2852: 2792: 2699: 2606: 2513: 2452:(objective function) 2445: 2363: 2343: 2321: 2296: 2253: 2102: 2052: 1805: 1698: 1645:(limit on pesticide) 1638: 1558: 1478: 1421: 1267: 1244: 1126: 1050: 841:of the following form 829: 670:interior-point method 559: 549: 495: 465: 428: 380: 356: 334: 312: 287: 149:finds a point in the 60: 40: 32:Broadcast programming 9062:Geometric algorithms 8551:Cutting-plane method 8035:. Berlin: Springer. 7831:Padberg, M. (1999). 7618:10.1287/moor.2.2.103 7119: 6826:. pp. 225–232. 6299:Optimization Toolbox 5694: 5666: 5639: 5595: 5538: 5483:cutting-plane method 5260: 5198: 5172: 5146: 5084: 5048: 5015: 4989: 4969: 4945: 4921: 4813: 4766: 4731: 4698: 4616: 4588: 4568: 4548: 4494: 4458: 4414: 4367: 4282: 3969: = 0, for 3942: = 0, for 3782:vertex cover problem 3568:Minimum vertex cover 2890: 2868: 2808: 2716: 2623: 2530: 2463: 2388: 2352: 2330: 2308: 2263: 2113: 2091: 1816: 1719: 1655: 1575: 1495: 1441: 1364: 1150: 1143:, and then becomes: 1074: 852: 743: 474: 441: 393: 369: 343: 321: 299: 167: 90:linear relationships 9067:P-complete problems 9057:Convex optimization 9003:exchange algorithms 8979:Mixed linear (MLCP) 8881:Simulated annealing 8699:Integer programming 8689:Dynamic programming 8529:Convex optimization 8390:Levenberg–Marquardt 7908:. Springer-Verlag. 7819:Evar D. Nering and 7398:Operations Research 6442:Job shop scheduling 6427:Dynamic programming 6108:integer programming 5435:integer programming 5358:strongly polynomial 4937:is the exponent of 4801:in the worst case. 4065:. Second, when the 4057: ≥ 2 and 3793:fractional coloring 3766:set packing problem 3549:Maximum set packing 3502:dual linear program 3325:Dual linear program 839:Problem constraints 693:multicommodity flow 682:operations research 651:observable universe 647:number of particles 517:dual linear program 82:linear optimization 9052:Linear programming 8561:Subgradient method 8445: 8370:Conjugate gradient 8278:Nelder–Mead method 8149:Ziegler, Günter M. 7937:Linear programming 7920:(Computer science) 7902:Vazirani, Vijay V. 7896:. Springer Verlag. 7858:(computer science) 7835:. Springer-Verlag. 7795:Linear programming 7738:10.1007/BF02614325 7679:, and introducing 7665:. Springer-Verlag. 7657:. Springer-Verlag. 7542:2011-06-29 at the 7487:"lp_solve command" 7195: 7076:10.1007/BF03025891 7028:10.1007/BF01585729 6941:10.1007/BF02614325 6796:10.1007/BF02579150 6724:Linear programming 6630:www.britannica.com 6437:Input–output model 6422:Convex programming 5774:totally unimodular 5724: 5672: 5652: 5625: 5571: 5469:totally unimodular 5308: 5246: 5184: 5158: 5132: 5070: 5034: 5001: 4975: 4951: 4927: 4907: 4791: 4752: 4713: 4684: 4594: 4574: 4554: 4534: 4480: 4436: 4392: 4307: 4263:This is the first 4234:in dimension 4211:complexity class P 4162: 3748:are non-negative. 3691:are non-negative. 3556:Minimum edge cover 3305: 3293: 3207: 3164: 3075: 2874: 2847: 2787: 2694: 2601: 2508: 2440: 2358: 2338: 2316: 2291: 2248: 2242: 2211: 2174: 2097: 2047: 2038: 2009: 1965: 1929: 1889: 1800: 1794: 1754: 1693: 1633: 1553: 1473: 1416: 1271: 1239: 1121: 1119: 1045: 1043: 824: 666:Narendra Karmarkar 620:From 1946 to 1947 579:Leonid Kantorovich 564: 554: 551:Leonid Kantorovich 490: 460: 437:. The constraints 435:objective function 423: 375: 351: 329: 307: 282: 280: 108:objective function 86:mathematical model 74:Linear programming 71: 55: 45:, a 2-dimensional 9039: 9038: 8916: 8915: 8899: 8898: 8839: 8838: 8835: 8834: 8798: 8797: 8759: 8758: 8655: 8654: 8651: 8650: 8647: 8646: 8518: 8517: 8514: 8513: 8434: 8433: 8430: 8429: 8408: 8407: 8112:978-1-4419-5512-8 8093:978-1-498-71016-9 8018:978-0-7167-1045-5 7989:978-3-540-65620-3 7932:Library resources 7915:978-3-540-65367-7 7804:978-0-471-09725-9 7706:978-0-7204-0765-5 7648:George B. Dantzig 7574:F. L. Hitchcock: 6841:978-1-4577-0394-2 6703:978-0-471-98232-6 6583:978-7-5218-0422-5 6514:Simplex algorithm 6412: 6411: 6406:dynamical systems 6101: 6100: 5963: 5962: 5675:{\displaystyle P} 5524:Integral polytope 5395:Hirsch conjecture 5384:ellipsoid methods 5272: 5210: 5096: 4825: 4710: 4676: 4628: 4597:{\displaystyle L} 4577:{\displaystyle n} 4557:{\displaystyle d} 4361:projective method 4327:iterative methods 4176:simplex algorithm 4129:simplex algorithm 4097:concave functions 4081:maximum principle 3882:, ..., 3778:set cover problem 3635: 3634: 3602: 3601: 3597:Rectangle packing 3544:Minimum set cover 3532:Covering problems 3500:infeasible. See 2877:{\displaystyle z} 2800: 2799: 2361:{\displaystyle z} 2100:{\displaystyle z} 2071:simplex algorithm 1709: 1708: 668:introduced a new 655:simplex algorithm 622:George B. Dantzig 378:{\displaystyle A} 257: 228: 196: 178: 133:of finitely many 116:linear inequality 16:(Redirected from 9074: 8943: 8936: 8929: 8920: 8919: 8845: 8844: 8761: 8760: 8727: 8726: 8704:Branch and bound 8694:Greedy algorithm 8674: 8673: 8661: 8660: 8581: 8580: 8537: 8536: 8524: 8523: 8465: 8464: 8452: 8451: 8400:Truncated Newton 8315:Wolfe conditions 8298: 8297: 8251: 8250: 8238: 8237: 8211: 8204: 8197: 8188: 8187: 8120:H. P. Williams, 8116: 8097: 8063: 8046: 8027:Gärtner, Bernd; 8022: 8011:. W.H. Freeman. 8003:David S. Johnson 7999:Michael R. Garey 7993: 7977: 7919: 7897: 7887: 7857: 7836: 7821:Albert W. Tucker 7816: 7786: 7757: 7731: 7722:(1–3): 369–395. 7710: 7666: 7638: 7629: 7571: 7547: 7534: 7528: 7522: 7516: 7515: 7504: 7498: 7497: 7495: 7493: 7483: 7477: 7476: 7474: 7472: 7462: 7456: 7455: 7453: 7452: 7438: 7432: 7431: 7413: 7389: 7383: 7382: 7372: 7348: 7342: 7341: 7339: 7323: 7317: 7316: 7314: 7298: 7292: 7291: 7289: 7273: 7267: 7266: 7264: 7248: 7242: 7241: 7215: 7209: 7208: 7204: 7202: 7201: 7196: 7182: 7181: 7157: 7156: 7126: 7110: 7104: 7103: 7054: 7048: 7047: 7011: 7005: 7000: 6994: 6989: 6983: 6978: 6972: 6970:Borgwardt (1987) 6967: 6961: 6960: 6934: 6925:(1–3): 369–395. 6907: 6896: 6891: 6882: 6877: 6866: 6860: 6854: 6853: 6825: 6814: 6808: 6807: 6779: 6770: 6769: 6757: 6746: 6745: 6719: 6708: 6707: 6689: 6683: 6682: 6660: 6651: 6640: 6639: 6637: 6636: 6622: 6616: 6615: 6597: 6588: 6587: 6569: 6563: 6562: 6550: 6544: 6543: 6531: 6493:Oriented matroid 6244:Gurobi Optimizer 6121: 6120: 5973: 5972: 5804: 5803: 5733: 5731: 5730: 5725: 5681: 5679: 5678: 5673: 5661: 5659: 5658: 5653: 5651: 5650: 5634: 5632: 5631: 5626: 5580: 5578: 5577: 5572: 5514:and in Beasley. 5498:Branch and price 5488:Branch and bound 5475:(TDI) property. 5429:Integer unknowns 5360:-time algorithm? 5356:Does LP admit a 5338: 5317: 5315: 5314: 5309: 5301: 5300: 5296: 5274: 5273: 5265: 5255: 5253: 5252: 5247: 5239: 5238: 5234: 5212: 5211: 5203: 5193: 5191: 5190: 5185: 5167: 5165: 5164: 5159: 5141: 5139: 5138: 5133: 5125: 5124: 5120: 5098: 5097: 5089: 5079: 5077: 5076: 5071: 5066: 5065: 5043: 5041: 5040: 5035: 5033: 5032: 5010: 5008: 5007: 5002: 4984: 4982: 4981: 4976: 4960: 4958: 4957: 4952: 4936: 4934: 4933: 4928: 4916: 4914: 4913: 4908: 4897: 4896: 4892: 4870: 4869: 4865: 4843: 4842: 4827: 4826: 4818: 4800: 4798: 4797: 4792: 4784: 4783: 4761: 4759: 4758: 4753: 4722: 4720: 4719: 4714: 4712: 4711: 4703: 4693: 4691: 4690: 4685: 4677: 4672: 4667: 4666: 4630: 4629: 4621: 4603: 4601: 4600: 4595: 4583: 4581: 4580: 4575: 4563: 4561: 4560: 4555: 4543: 4541: 4540: 4535: 4524: 4523: 4489: 4487: 4486: 4481: 4476: 4475: 4445: 4443: 4442: 4437: 4432: 4431: 4401: 4399: 4398: 4393: 4385: 4384: 4323:ellipsoid method 4319:Leonid Khachiyan 4316: 4314: 4313: 4308: 4300: 4299: 4087:convex functions 4040:concave function 3774:matching problem 3740:and the vectors 3683:and the vectors 3627: 3620: 3613: 3592:Polygon covering 3561:Maximum matching 3537:Packing problems 3528: 3527: 3517: 3516: 3314: 3312: 3311: 3306: 3298: 3297: 3290: 3289: 3276: 3275: 3262: 3261: 3248: 3247: 3234: 3233: 3212: 3211: 3169: 3168: 3161: 3160: 3147: 3146: 3133: 3132: 3119: 3118: 3105: 3104: 3080: 3079: 3057: 3056: 3045: 3044: 3011: 3010: 2999: 2998: 2933: 2932: 2918: 2917: 2883: 2881: 2880: 2875: 2856: 2854: 2853: 2848: 2846: 2845: 2833: 2832: 2820: 2819: 2796: 2794: 2793: 2788: 2780: 2779: 2767: 2766: 2754: 2753: 2741: 2740: 2728: 2727: 2703: 2701: 2700: 2695: 2687: 2686: 2674: 2673: 2661: 2660: 2648: 2647: 2635: 2634: 2610: 2608: 2607: 2602: 2594: 2593: 2581: 2580: 2568: 2567: 2555: 2554: 2542: 2541: 2517: 2515: 2514: 2509: 2501: 2500: 2488: 2487: 2475: 2474: 2449: 2447: 2446: 2441: 2439: 2438: 2426: 2425: 2413: 2412: 2400: 2399: 2381: 2380: 2367: 2365: 2364: 2359: 2347: 2345: 2344: 2339: 2337: 2325: 2323: 2322: 2317: 2315: 2300: 2298: 2297: 2292: 2284: 2270: 2257: 2255: 2254: 2249: 2247: 2246: 2239: 2216: 2215: 2208: 2199: 2179: 2178: 2171: 2164: 2145: 2144: 2143: 2137: 2106: 2104: 2103: 2098: 2056: 2054: 2053: 2048: 2043: 2042: 2014: 2013: 2006: 2005: 1992: 1991: 1970: 1969: 1934: 1933: 1926: 1925: 1912: 1911: 1894: 1893: 1886: 1885: 1874: 1873: 1860: 1859: 1848: 1847: 1809: 1807: 1806: 1801: 1799: 1798: 1791: 1790: 1777: 1776: 1759: 1758: 1751: 1750: 1739: 1738: 1702: 1700: 1699: 1694: 1686: 1685: 1667: 1666: 1642: 1640: 1639: 1634: 1626: 1625: 1613: 1612: 1600: 1599: 1587: 1586: 1562: 1560: 1559: 1554: 1546: 1545: 1533: 1532: 1520: 1519: 1507: 1506: 1482: 1480: 1479: 1474: 1466: 1465: 1453: 1452: 1435: 1425: 1423: 1422: 1417: 1415: 1414: 1402: 1401: 1389: 1388: 1376: 1375: 1355: 1354: 1248: 1246: 1245: 1240: 1228: 1220: 1212: 1201: 1200: 1195: 1186: 1178: 1173: 1172: 1171: 1165: 1130: 1128: 1127: 1122: 1120: 1110: 1109: 1090: 1089: 1054: 1052: 1051: 1046: 1044: 1040: 1039: 1025: 1024: 1015: 1014: 1002: 1001: 992: 991: 978: 977: 963: 962: 953: 952: 940: 939: 930: 929: 916: 915: 901: 900: 891: 890: 878: 877: 868: 867: 833: 831: 830: 825: 823: 822: 813: 812: 800: 799: 790: 789: 774: 773: 761: 760: 714:maximize profits 662:Leonid Khachiyan 630:John von Neumann 583:Wassily Leontief 561:John von Neumann 513:John von Neumann 499: 497: 496: 491: 489: 481: 469: 467: 466: 461: 459: 451: 432: 430: 429: 424: 422: 417: 416: 415: 409: 400: 384: 382: 381: 376: 360: 358: 357: 352: 350: 338: 336: 335: 330: 328: 316: 314: 313: 308: 306: 291: 289: 288: 283: 281: 274: 266: 260: 258: 255: 252: 248: 240: 231: 229: 226: 223: 219: 214: 213: 212: 206: 199: 197: 194: 191: 187: 181: 179: 176: 173: 21: 9082: 9081: 9077: 9076: 9075: 9073: 9072: 9071: 9042: 9041: 9040: 9035: 9021:Revised simplex 8993: 8989:Nonlinear (NCP) 8952: 8947: 8917: 8912: 8895: 8852: 8831: 8794: 8755: 8732: 8721: 8714: 8668: 8643: 8607: 8574: 8565: 8542: 8531: 8510: 8484: 8480:Penalty methods 8475:Barrier methods 8459: 8446: 8426: 8422:Newton's method 8404: 8356: 8319: 8287: 8268:Powell's method 8245: 8232: 8215: 8163: 8158: 8113: 8094: 8043: 8019: 7990: 7980:Springer-Verlag 7952: 7951: 7950: 7940: 7939: 7935: 7928: 7926:Further reading 7923: 7916: 7805: 7791:Murty, Katta G. 7707: 7555: 7550: 7544:Wayback Machine 7535: 7531: 7523: 7519: 7506: 7505: 7501: 7491: 7489: 7485: 7484: 7480: 7470: 7468: 7464: 7463: 7459: 7450: 7448: 7440: 7439: 7435: 7390: 7386: 7370:10.1.1.646.3539 7349: 7345: 7324: 7320: 7299: 7295: 7274: 7270: 7249: 7245: 7238: 7216: 7212: 7177: 7173: 7152: 7148: 7122: 7120: 7117: 7116: 7111: 7107: 7058:Strang, Gilbert 7055: 7051: 7012: 7008: 7001: 6997: 6990: 6986: 6979: 6975: 6968: 6964: 6908: 6899: 6892: 6885: 6878: 6869: 6861: 6857: 6842: 6823: 6815: 6811: 6780: 6773: 6768:(5): 1093–1096. 6758: 6749: 6734: 6720: 6711: 6704: 6690: 6686: 6658: 6652: 6643: 6634: 6632: 6624: 6623: 6619: 6612: 6598: 6591: 6584: 6572:Li, Wu (2019). 6570: 6566: 6551: 6547: 6532: 6528: 6524: 6519: 6472:LP-type problem 6417: 6217:Solver Function 6042:. Bundles the 5794: 5782:submodular flow 5734:is an integer. 5695: 5692: 5691: 5667: 5664: 5663: 5646: 5642: 5640: 5637: 5636: 5635:has an optimum 5596: 5593: 5592: 5539: 5536: 5535: 5526: 5520: 5431: 5349: 5348: 5343: 5340: 5333: 5324: 5292: 5282: 5278: 5264: 5263: 5261: 5258: 5257: 5230: 5220: 5216: 5202: 5201: 5199: 5196: 5195: 5173: 5170: 5169: 5147: 5144: 5143: 5116: 5106: 5102: 5088: 5087: 5085: 5082: 5081: 5061: 5057: 5049: 5046: 5045: 5028: 5024: 5016: 5013: 5012: 4990: 4987: 4986: 4970: 4967: 4966: 4946: 4943: 4942: 4922: 4919: 4918: 4888: 4878: 4874: 4861: 4851: 4847: 4838: 4834: 4817: 4816: 4814: 4811: 4810: 4807: 4779: 4775: 4767: 4764: 4763: 4732: 4729: 4728: 4725:soft O notation 4702: 4701: 4699: 4696: 4695: 4671: 4662: 4658: 4620: 4619: 4617: 4614: 4613: 4610: 4589: 4586: 4585: 4569: 4566: 4565: 4549: 4546: 4545: 4519: 4515: 4495: 4492: 4491: 4471: 4467: 4459: 4456: 4455: 4452: 4427: 4423: 4415: 4412: 4411: 4408: 4380: 4376: 4368: 4365: 4364: 4349: 4343: 4295: 4291: 4283: 4280: 4279: 4268:polynomial-time 4261: 4252: 4240:Klee–Minty cube 4219: 4207:polynomial time 4178:, developed by 4172: 4167: 4154:feasible region 4143: 4137: 4076: 4028:convex function 4024:linear function 4020:convex polytope 4016:feasible region 4012: 4007: 3968: 3960: 3941: 3933: 3913: 3904: 3897: 3890: 3881: 3874: 3867: 3858: 3851: 3840: 3831: 3824: 3809: 3801:independent set 3754: 3731: 3710: 3674: 3653: 3631: 3515: 3510: 3327: 3321: 3292: 3291: 3285: 3281: 3278: 3277: 3271: 3267: 3264: 3263: 3257: 3253: 3250: 3249: 3243: 3239: 3236: 3235: 3229: 3225: 3218: 3217: 3206: 3205: 3199: 3198: 3192: 3191: 3185: 3184: 3174: 3173: 3163: 3162: 3156: 3152: 3149: 3148: 3142: 3138: 3135: 3134: 3128: 3124: 3121: 3120: 3114: 3110: 3107: 3106: 3100: 3096: 3093: 3092: 3082: 3081: 3074: 3073: 3068: 3063: 3058: 3052: 3048: 3046: 3040: 3036: 3034: 3028: 3027: 3022: 3017: 3012: 3006: 3002: 3000: 2994: 2990: 2988: 2982: 2981: 2976: 2971: 2966: 2961: 2956: 2950: 2949: 2944: 2939: 2934: 2928: 2924: 2919: 2913: 2909: 2904: 2894: 2893: 2891: 2888: 2887: 2869: 2866: 2865: 2841: 2837: 2828: 2824: 2815: 2811: 2809: 2806: 2805: 2775: 2771: 2762: 2758: 2749: 2745: 2736: 2732: 2723: 2719: 2717: 2714: 2713: 2682: 2678: 2669: 2665: 2656: 2652: 2643: 2639: 2630: 2626: 2624: 2621: 2620: 2589: 2585: 2576: 2572: 2563: 2559: 2550: 2546: 2537: 2533: 2531: 2528: 2527: 2496: 2492: 2483: 2479: 2470: 2466: 2464: 2461: 2460: 2434: 2430: 2421: 2417: 2408: 2404: 2395: 2391: 2389: 2386: 2385: 2374: 2353: 2350: 2349: 2333: 2331: 2328: 2327: 2311: 2309: 2306: 2305: 2280: 2266: 2264: 2261: 2260: 2241: 2240: 2235: 2232: 2231: 2221: 2220: 2210: 2209: 2204: 2201: 2200: 2195: 2192: 2191: 2181: 2180: 2173: 2172: 2167: 2165: 2160: 2158: 2152: 2151: 2146: 2139: 2138: 2133: 2132: 2127: 2117: 2116: 2114: 2111: 2110: 2092: 2089: 2088: 2076:slack variables 2063: 2037: 2036: 2030: 2029: 2019: 2018: 2008: 2007: 2001: 1997: 1994: 1993: 1987: 1983: 1976: 1975: 1964: 1963: 1957: 1956: 1950: 1949: 1939: 1938: 1928: 1927: 1921: 1917: 1914: 1913: 1907: 1903: 1896: 1895: 1888: 1887: 1881: 1877: 1875: 1869: 1865: 1862: 1861: 1855: 1851: 1849: 1843: 1839: 1836: 1835: 1830: 1820: 1819: 1817: 1814: 1813: 1793: 1792: 1786: 1782: 1779: 1778: 1772: 1768: 1761: 1760: 1753: 1752: 1746: 1742: 1740: 1734: 1730: 1723: 1722: 1720: 1717: 1716: 1681: 1677: 1662: 1658: 1656: 1653: 1652: 1621: 1617: 1608: 1604: 1595: 1591: 1582: 1578: 1576: 1573: 1572: 1541: 1537: 1528: 1524: 1515: 1511: 1502: 1498: 1496: 1493: 1492: 1461: 1457: 1448: 1444: 1442: 1439: 1438: 1433: 1410: 1406: 1397: 1393: 1384: 1380: 1371: 1367: 1365: 1362: 1361: 1351: 1344: 1337: 1330: 1323: 1319: 1315: 1308: 1301: 1294: 1262: 1224: 1216: 1208: 1196: 1191: 1190: 1182: 1174: 1167: 1166: 1161: 1160: 1151: 1148: 1147: 1118: 1117: 1105: 1101: 1098: 1097: 1085: 1081: 1077: 1075: 1072: 1071: 1042: 1041: 1035: 1031: 1026: 1020: 1016: 1010: 1006: 997: 993: 987: 983: 980: 979: 973: 969: 964: 958: 954: 948: 944: 935: 931: 925: 921: 918: 917: 911: 907: 902: 896: 892: 886: 882: 873: 869: 863: 859: 855: 853: 850: 849: 818: 814: 808: 804: 795: 791: 785: 781: 769: 765: 756: 752: 744: 741: 740: 722: 678: 544: 538: 502:convex polytope 485: 477: 475: 472: 471: 455: 447: 442: 439: 438: 418: 411: 410: 405: 404: 396: 394: 391: 390: 370: 367: 366: 346: 344: 341: 340: 324: 322: 319: 318: 302: 300: 297: 296: 279: 278: 270: 262: 259: 254: 250: 249: 244: 236: 230: 225: 221: 220: 215: 208: 207: 202: 201: 198: 193: 189: 188: 183: 180: 175: 170: 168: 165: 164: 127:convex polytope 123:feasible region 112:linear equality 80:), also called 35: 28: 23: 22: 15: 12: 11: 5: 9080: 9070: 9069: 9064: 9059: 9054: 9037: 9036: 9034: 9033: 9028: 9023: 9018: 9007: 9005: 8995: 8994: 8992: 8991: 8986: 8981: 8976: 8971: 8966: 8960: 8958: 8954: 8953: 8946: 8945: 8938: 8931: 8923: 8914: 8913: 8911: 8910: 8904: 8901: 8900: 8897: 8896: 8894: 8893: 8888: 8883: 8878: 8873: 8868: 8863: 8857: 8854: 8853: 8850:Metaheuristics 8841: 8840: 8837: 8836: 8833: 8832: 8830: 8829: 8824: 8822:Ford–Fulkerson 8819: 8814: 8808: 8806: 8800: 8799: 8796: 8795: 8793: 8792: 8790:Floyd–Warshall 8787: 8782: 8781: 8780: 8769: 8767: 8757: 8756: 8754: 8753: 8748: 8743: 8737: 8735: 8724: 8716: 8715: 8713: 8712: 8711: 8710: 8696: 8691: 8686: 8680: 8678: 8670: 8669: 8657: 8656: 8653: 8652: 8649: 8648: 8645: 8644: 8642: 8641: 8636: 8631: 8626: 8620: 8618: 8609: 8608: 8606: 8605: 8600: 8595: 8593:Affine scaling 8589: 8587: 8585:Interior point 8578: 8567: 8566: 8564: 8563: 8558: 8553: 8547: 8545: 8533: 8532: 8520: 8519: 8516: 8515: 8512: 8511: 8509: 8508: 8503: 8498: 8492: 8490: 8489:Differentiable 8486: 8485: 8483: 8482: 8477: 8471: 8469: 8461: 8460: 8448: 8447: 8437: 8435: 8432: 8431: 8428: 8427: 8425: 8424: 8418: 8416: 8410: 8409: 8406: 8405: 8403: 8402: 8397: 8392: 8387: 8382: 8377: 8372: 8366: 8364: 8358: 8357: 8355: 8354: 8349: 8344: 8335: 8329: 8327: 8321: 8320: 8318: 8317: 8312: 8306: 8304: 8295: 8289: 8288: 8286: 8285: 8280: 8275: 8270: 8265: 8259: 8257: 8247: 8246: 8234: 8233: 8214: 8213: 8206: 8199: 8191: 8185: 8184: 8179: 8174: 8169: 8162: 8161:External links 8159: 8157: 8156: 8146: 8136: 8127: 8118: 8111: 8098: 8092: 8079: 8078:(mathematical) 8064: 8055: 8048: 8041: 8029:Matoušek, Jiří 8024: 8017: 7995: 7988: 7968:Overmars, Mark 7963: 7953: 7949: 7948: 7942: 7941: 7930: 7929: 7927: 7924: 7922: 7921: 7914: 7898: 7889: 7870:(3): 417–436. 7859: 7846: 7828: 7817: 7803: 7787: 7758: 7729:10.1.1.36.9373 7711: 7705: 7684: 7658: 7651: 7640: 7630: 7612:(2): 103–107. 7601: 7594: 7581: 7572: 7556: 7554: 7551: 7549: 7548: 7529: 7517: 7499: 7478: 7457: 7433: 7404:(3): 556–561. 7384: 7343: 7318: 7293: 7268: 7243: 7236: 7210: 7194: 7191: 7188: 7185: 7180: 7176: 7172: 7169: 7166: 7163: 7160: 7155: 7151: 7147: 7144: 7141: 7138: 7135: 7132: 7129: 7125: 7105: 7049: 7006: 6995: 6984: 6973: 6962: 6932:10.1.1.36.9373 6915:Terlaky, Tamás 6897: 6894:Padberg (1999) 6883: 6867: 6865:, p. 112) 6863:Vazirani (2001 6855: 6840: 6809: 6790:(4): 373–395. 6771: 6747: 6732: 6709: 6702: 6684: 6641: 6617: 6611:978-1498710169 6610: 6589: 6582: 6564: 6545: 6525: 6523: 6520: 6518: 6517: 6511: 6506: 6501: 6495: 6490: 6487:Odds algorithm 6484: 6479: 6474: 6469: 6464: 6459: 6457:Linear algebra 6454: 6449: 6444: 6439: 6434: 6429: 6424: 6418: 6416: 6413: 6410: 6409: 6398: 6392: 6391: 6383: 6377: 6376: 6365: 6358: 6357: 6354: 6348: 6347: 6339: 6333: 6332: 6329: 6323: 6322: 6319: 6313: 6312: 6309: 6303: 6302: 6295: 6289: 6288: 6285: 6279: 6278: 6266: 6260: 6259: 6255: 6249: 6248: 6246: 6240: 6239: 6237: 6231: 6230: 6228: 6222: 6221: 6218: 6211: 6210: 6199: 6193: 6192: 6189: 6183: 6182: 6175:Artelys Knitro 6166: 6160: 6159: 6156: 6150: 6149: 6146: 6140: 6139: 6135: 6129: 6128: 6125: 6099: 6098: 6095: 6092: 6086: 6085: 6082: 6079: 6073: 6072: 6061: 6058: 6052: 6051: 6032: 6029: 6023: 6022: 6019: 6016: 6010: 6009: 6006: 6003: 5997: 5996: 5993: 5990: 5984: 5983: 5980: 5977: 5961: 5960: 5941: 5936: 5930: 5929: 5926: 5921: 5915: 5914: 5911: 5906: 5900: 5899: 5872: 5867: 5861: 5860: 5857: 5852: 5846: 5845: 5826: 5821: 5815: 5814: 5811: 5808: 5793: 5790: 5770: 5769: 5758: 5723: 5720: 5717: 5714: 5711: 5708: 5705: 5702: 5699: 5686:, the optimal 5671: 5649: 5645: 5624: 5621: 5618: 5615: 5612: 5609: 5606: 5603: 5600: 5581:is said to be 5570: 5567: 5564: 5561: 5558: 5555: 5552: 5549: 5546: 5543: 5519: 5516: 5508: 5507: 5500: 5495: 5493:Branch and cut 5490: 5485: 5430: 5427: 5406: 5405: 5402: 5382:, such as the 5368: 5367: 5364: 5361: 5344: 5341: 5335: 5332: 5329: 5323: 5320: 5307: 5304: 5299: 5295: 5291: 5288: 5285: 5281: 5277: 5271: 5268: 5245: 5242: 5237: 5233: 5229: 5226: 5223: 5219: 5215: 5209: 5206: 5183: 5180: 5177: 5157: 5154: 5151: 5131: 5128: 5123: 5119: 5115: 5112: 5109: 5105: 5101: 5095: 5092: 5069: 5064: 5060: 5056: 5053: 5031: 5027: 5023: 5020: 5000: 4997: 4994: 4974: 4950: 4926: 4906: 4903: 4900: 4895: 4891: 4887: 4884: 4881: 4877: 4873: 4868: 4864: 4860: 4857: 4854: 4850: 4846: 4841: 4837: 4833: 4830: 4824: 4821: 4806: 4803: 4790: 4787: 4782: 4778: 4774: 4771: 4751: 4748: 4745: 4742: 4739: 4736: 4709: 4706: 4683: 4680: 4675: 4670: 4665: 4661: 4657: 4654: 4651: 4648: 4645: 4642: 4639: 4636: 4633: 4627: 4624: 4609: 4606: 4593: 4573: 4553: 4533: 4530: 4527: 4522: 4518: 4514: 4511: 4508: 4505: 4502: 4499: 4479: 4474: 4470: 4466: 4463: 4451: 4448: 4435: 4430: 4426: 4422: 4419: 4407: 4404: 4391: 4388: 4383: 4379: 4375: 4372: 4345:Main article: 4342: 4339: 4306: 4303: 4298: 4294: 4290: 4287: 4260: 4257: 4251: 4250:Interior point 4248: 4218: 4215: 4180:George Dantzig 4171: 4168: 4166: 4163: 4158:simple polygon 4136: 4133: 4094:principle for 4075: 4072: 4048:global maximum 4036:global minimum 4011: 4008: 4006: 4003: 3979: 3978: 3964: 3956: 3951: 3937: 3929: 3909: 3902: 3895: 3886: 3879: 3872: 3863: 3856: 3849: 3845: = ( 3836: 3829: 3822: 3818: = ( 3808: 3805: 3803:of the graph. 3753: 3750: 3734: 3733: 3715: 3712: 3703: 3677: 3676: 3658: 3655: 3646: 3633: 3632: 3630: 3629: 3622: 3615: 3607: 3604: 3603: 3600: 3599: 3594: 3588: 3587: 3582: 3576: 3575: 3570: 3564: 3563: 3558: 3552: 3551: 3546: 3540: 3539: 3534: 3524: 3523: 3514: 3511: 3509: 3506: 3472:strong duality 3463: 3462: 3437: 3436: 3435: 3403: 3402: 3377: 3376: 3375: 3323:Main article: 3320: 3317: 3316: 3315: 3304: 3301: 3296: 3288: 3284: 3280: 3279: 3274: 3270: 3266: 3265: 3260: 3256: 3252: 3251: 3246: 3242: 3238: 3237: 3232: 3228: 3224: 3223: 3221: 3215: 3210: 3204: 3201: 3200: 3197: 3194: 3193: 3190: 3187: 3186: 3183: 3180: 3179: 3177: 3172: 3167: 3159: 3155: 3151: 3150: 3145: 3141: 3137: 3136: 3131: 3127: 3123: 3122: 3117: 3113: 3109: 3108: 3103: 3099: 3095: 3094: 3091: 3088: 3087: 3085: 3078: 3072: 3069: 3067: 3064: 3062: 3059: 3055: 3051: 3047: 3043: 3039: 3035: 3033: 3030: 3029: 3026: 3023: 3021: 3018: 3016: 3013: 3009: 3005: 3001: 2997: 2993: 2989: 2987: 2984: 2983: 2980: 2977: 2975: 2972: 2970: 2967: 2965: 2962: 2960: 2957: 2955: 2952: 2951: 2948: 2945: 2943: 2940: 2938: 2935: 2931: 2927: 2923: 2920: 2916: 2912: 2908: 2905: 2903: 2900: 2899: 2897: 2885: 2873: 2844: 2840: 2836: 2831: 2827: 2823: 2818: 2814: 2802: 2801: 2798: 2797: 2786: 2783: 2778: 2774: 2770: 2765: 2761: 2757: 2752: 2748: 2744: 2739: 2735: 2731: 2726: 2722: 2711: 2708: 2707: 2704: 2693: 2690: 2685: 2681: 2677: 2672: 2668: 2664: 2659: 2655: 2651: 2646: 2642: 2638: 2633: 2629: 2618: 2615: 2614: 2611: 2600: 2597: 2592: 2588: 2584: 2579: 2575: 2571: 2566: 2562: 2558: 2553: 2549: 2545: 2540: 2536: 2525: 2522: 2521: 2518: 2507: 2504: 2499: 2495: 2491: 2486: 2482: 2478: 2473: 2469: 2458: 2454: 2453: 2450: 2437: 2433: 2429: 2424: 2420: 2416: 2411: 2407: 2403: 2398: 2394: 2373: 2370: 2357: 2336: 2314: 2302: 2301: 2290: 2287: 2283: 2279: 2276: 2273: 2269: 2258: 2245: 2238: 2234: 2233: 2230: 2227: 2226: 2224: 2219: 2214: 2207: 2203: 2202: 2198: 2194: 2193: 2190: 2187: 2186: 2184: 2177: 2170: 2166: 2163: 2159: 2157: 2154: 2153: 2150: 2147: 2142: 2136: 2131: 2128: 2126: 2123: 2122: 2120: 2108: 2096: 2067:augmented form 2062: 2059: 2058: 2057: 2046: 2041: 2035: 2032: 2031: 2028: 2025: 2024: 2022: 2017: 2012: 2004: 2000: 1996: 1995: 1990: 1986: 1982: 1981: 1979: 1973: 1968: 1962: 1959: 1958: 1955: 1952: 1951: 1948: 1945: 1944: 1942: 1937: 1932: 1924: 1920: 1916: 1915: 1910: 1906: 1902: 1901: 1899: 1892: 1884: 1880: 1876: 1872: 1868: 1864: 1863: 1858: 1854: 1850: 1846: 1842: 1838: 1837: 1834: 1831: 1829: 1826: 1825: 1823: 1810: 1797: 1789: 1785: 1781: 1780: 1775: 1771: 1767: 1766: 1764: 1757: 1749: 1745: 1741: 1737: 1733: 1729: 1728: 1726: 1707: 1706: 1703: 1692: 1689: 1684: 1680: 1676: 1673: 1670: 1665: 1661: 1650: 1647: 1646: 1643: 1632: 1629: 1624: 1620: 1616: 1611: 1607: 1603: 1598: 1594: 1590: 1585: 1581: 1570: 1567: 1566: 1563: 1552: 1549: 1544: 1540: 1536: 1531: 1527: 1523: 1518: 1514: 1510: 1505: 1501: 1490: 1487: 1486: 1483: 1472: 1469: 1464: 1460: 1456: 1451: 1447: 1436: 1430: 1429: 1426: 1413: 1409: 1405: 1400: 1396: 1392: 1387: 1383: 1379: 1374: 1370: 1359: 1349: 1342: 1335: 1328: 1321: 1317: 1313: 1306: 1299: 1292: 1261: 1258: 1250: 1249: 1238: 1234: 1231: 1227: 1223: 1219: 1215: 1211: 1207: 1204: 1199: 1194: 1189: 1185: 1181: 1177: 1170: 1164: 1158: 1155: 1134: 1133: 1132: 1131: 1116: 1113: 1108: 1104: 1100: 1099: 1096: 1093: 1088: 1084: 1080: 1079: 1065: 1064: 1058: 1057: 1056: 1055: 1038: 1034: 1030: 1027: 1023: 1019: 1013: 1009: 1005: 1000: 996: 990: 986: 982: 981: 976: 972: 968: 965: 961: 957: 951: 947: 943: 938: 934: 928: 924: 920: 919: 914: 910: 906: 903: 899: 895: 889: 885: 881: 876: 872: 866: 862: 858: 857: 843: 842: 835: 834: 821: 817: 811: 807: 803: 798: 794: 788: 784: 780: 777: 772: 768: 764: 759: 755: 751: 748: 736: 735: 721: 718: 710:microeconomics 702:decomposition, 677: 674: 626:simplex method 615:simplex method 603:T. C. Koopmans 543: 540: 535:, and design. 488: 484: 480: 458: 454: 450: 446: 421: 414: 408: 403: 399: 374: 349: 327: 305: 293: 292: 277: 273: 269: 265: 261: 253: 251: 247: 243: 239: 235: 232: 224: 222: 218: 211: 205: 200: 195:that maximizes 192: 190: 186: 182: 174: 172: 26: 18:Linear program 9: 6: 4: 3: 2: 9079: 9068: 9065: 9063: 9060: 9058: 9055: 9053: 9050: 9049: 9047: 9032: 9029: 9027: 9024: 9022: 9019: 9016: 9012: 9009: 9008: 9006: 9004: 9000: 8996: 8990: 8987: 8985: 8982: 8980: 8977: 8975: 8972: 8970: 8967: 8965: 8962: 8961: 8959: 8955: 8951: 8944: 8939: 8937: 8932: 8930: 8925: 8924: 8921: 8909: 8906: 8905: 8902: 8892: 8889: 8887: 8884: 8882: 8879: 8877: 8874: 8872: 8869: 8867: 8866:Hill climbing 8864: 8862: 8859: 8858: 8855: 8851: 8846: 8842: 8828: 8825: 8823: 8820: 8818: 8815: 8813: 8810: 8809: 8807: 8805: 8804:Network flows 8801: 8791: 8788: 8786: 8783: 8779: 8776: 8775: 8774: 8771: 8770: 8768: 8766: 8765:Shortest path 8762: 8752: 8749: 8747: 8744: 8742: 8739: 8738: 8736: 8734: 8733:spanning tree 8728: 8725: 8723: 8717: 8709: 8705: 8702: 8701: 8700: 8697: 8695: 8692: 8690: 8687: 8685: 8682: 8681: 8679: 8675: 8671: 8667: 8666:Combinatorial 8662: 8658: 8640: 8637: 8635: 8632: 8630: 8627: 8625: 8622: 8621: 8619: 8617: 8614: 8610: 8604: 8601: 8599: 8596: 8594: 8591: 8590: 8588: 8586: 8582: 8579: 8577: 8572: 8568: 8562: 8559: 8557: 8554: 8552: 8549: 8548: 8546: 8544: 8538: 8534: 8530: 8525: 8521: 8507: 8504: 8502: 8499: 8497: 8494: 8493: 8491: 8487: 8481: 8478: 8476: 8473: 8472: 8470: 8466: 8462: 8458: 8453: 8449: 8441: 8423: 8420: 8419: 8417: 8415: 8411: 8401: 8398: 8396: 8393: 8391: 8388: 8386: 8383: 8381: 8378: 8376: 8373: 8371: 8368: 8367: 8365: 8363: 8362:Other methods 8359: 8353: 8350: 8348: 8345: 8343: 8339: 8336: 8334: 8331: 8330: 8328: 8326: 8322: 8316: 8313: 8311: 8308: 8307: 8305: 8303: 8299: 8296: 8294: 8290: 8284: 8281: 8279: 8276: 8274: 8271: 8269: 8266: 8264: 8261: 8260: 8258: 8256: 8252: 8248: 8244: 8239: 8235: 8231: 8227: 8223: 8219: 8212: 8207: 8205: 8200: 8198: 8193: 8192: 8189: 8183: 8180: 8178: 8175: 8173: 8170: 8168: 8165: 8164: 8154: 8150: 8147: 8144: 8140: 8137: 8134: 8133: 8128: 8125: 8124: 8119: 8114: 8108: 8104: 8099: 8095: 8089: 8086:. CRC Press. 8085: 8080: 8077: 8076:0-471-98232-6 8073: 8069: 8065: 8061: 8056: 8053: 8049: 8044: 8042:3-540-30697-8 8038: 8034: 8030: 8025: 8020: 8014: 8010: 8009: 8004: 8000: 7996: 7991: 7985: 7981: 7976: 7975: 7969: 7964: 7961: 7960: 7955: 7954: 7947: 7944: 7943: 7938: 7933: 7917: 7911: 7907: 7903: 7899: 7895: 7890: 7885: 7881: 7877: 7873: 7869: 7865: 7860: 7855: 7851: 7847: 7844: 7840: 7834: 7829: 7826: 7822: 7818: 7814: 7810: 7806: 7800: 7796: 7792: 7788: 7784: 7780: 7776: 7772: 7768: 7764: 7759: 7755: 7751: 7747: 7743: 7739: 7735: 7730: 7725: 7721: 7717: 7712: 7708: 7702: 7698: 7694: 7690: 7685: 7682: 7678: 7674: 7670: 7664: 7659: 7656: 7652: 7649: 7645: 7641: 7636: 7631: 7627: 7623: 7619: 7615: 7611: 7607: 7602: 7599: 7595: 7592: 7588: 7587: 7583:G.B Dantzig: 7582: 7579: 7578: 7573: 7569: 7565: 7564: 7558: 7557: 7545: 7541: 7538: 7533: 7526: 7521: 7513: 7509: 7503: 7488: 7482: 7467: 7461: 7447: 7443: 7437: 7429: 7425: 7421: 7417: 7412: 7407: 7403: 7399: 7395: 7388: 7380: 7376: 7371: 7366: 7362: 7358: 7354: 7347: 7338: 7333: 7329: 7322: 7313: 7308: 7304: 7297: 7288: 7283: 7279: 7272: 7263: 7258: 7254: 7247: 7239: 7237:0-8186-1982-1 7233: 7229: 7225: 7221: 7214: 7206: 7189: 7183: 7178: 7170: 7167: 7164: 7158: 7153: 7149: 7142: 7139: 7136: 7123: 7109: 7101: 7097: 7093: 7089: 7085: 7081: 7077: 7073: 7069: 7065: 7064: 7059: 7053: 7045: 7041: 7037: 7033: 7029: 7025: 7021: 7017: 7010: 7004: 6999: 6993: 6988: 6982: 6977: 6971: 6966: 6958: 6954: 6950: 6946: 6942: 6938: 6933: 6928: 6924: 6920: 6916: 6912: 6911:Fukuda, Komei 6906: 6904: 6902: 6895: 6890: 6888: 6881: 6876: 6874: 6872: 6864: 6859: 6851: 6847: 6843: 6837: 6833: 6829: 6822: 6821: 6813: 6805: 6801: 6797: 6793: 6789: 6785: 6784:Combinatorica 6778: 6776: 6767: 6763: 6756: 6754: 6752: 6743: 6739: 6735: 6729: 6725: 6718: 6716: 6714: 6705: 6699: 6695: 6688: 6680: 6676: 6672: 6668: 6664: 6657: 6650: 6648: 6646: 6631: 6627: 6621: 6613: 6607: 6603: 6596: 6594: 6585: 6579: 6575: 6568: 6560: 6556: 6549: 6541: 6537: 6530: 6526: 6515: 6512: 6510: 6507: 6505: 6502: 6499: 6496: 6494: 6491: 6488: 6485: 6483: 6480: 6478: 6475: 6473: 6470: 6468: 6465: 6463: 6460: 6458: 6455: 6453: 6450: 6448: 6445: 6443: 6440: 6438: 6435: 6433: 6430: 6428: 6425: 6423: 6420: 6419: 6407: 6403: 6402:block diagram 6399: 6397: 6394: 6393: 6389: 6384: 6382: 6379: 6378: 6374: 6370: 6366: 6363: 6360: 6359: 6355: 6353: 6350: 6349: 6344: 6340: 6338: 6335: 6334: 6330: 6328: 6325: 6324: 6320: 6318: 6315: 6314: 6310: 6308: 6305: 6304: 6300: 6296: 6294: 6291: 6290: 6286: 6284: 6281: 6280: 6276: 6272: 6267: 6265: 6262: 6261: 6256: 6254: 6251: 6250: 6247: 6245: 6242: 6241: 6238: 6236: 6233: 6232: 6229: 6227: 6224: 6223: 6219: 6216: 6213: 6212: 6208: 6204: 6200: 6198: 6195: 6194: 6190: 6188: 6185: 6184: 6180: 6176: 6172: 6167: 6165: 6162: 6161: 6157: 6155: 6152: 6151: 6147: 6145: 6142: 6141: 6136: 6134: 6131: 6130: 6126: 6123: 6122: 6119: 6118: 6116: 6111: 6109: 6105: 6096: 6093: 6091: 6088: 6087: 6083: 6080: 6078: 6075: 6074: 6070: 6066: 6062: 6059: 6057: 6054: 6053: 6049: 6045: 6041: 6040:flow networks 6037: 6033: 6030: 6028: 6025: 6024: 6020: 6017: 6015: 6012: 6011: 6007: 6004: 6002: 5999: 5998: 5994: 5991: 5989: 5986: 5985: 5981: 5978: 5975: 5974: 5971: 5970: 5968: 5958: 5954: 5950: 5946: 5942: 5940: 5937: 5935: 5932: 5931: 5927: 5925: 5922: 5920: 5917: 5916: 5912: 5910: 5907: 5905: 5902: 5901: 5898:optimization 5897: 5893: 5889: 5885: 5881: 5877: 5873: 5871: 5868: 5866: 5863: 5862: 5858: 5856: 5853: 5851: 5848: 5847: 5844:optimization 5843: 5839: 5835: 5831: 5827: 5825: 5822: 5820: 5817: 5816: 5812: 5809: 5806: 5805: 5802: 5801: 5799: 5789: 5787: 5783: 5779: 5775: 5767: 5763: 5759: 5756: 5752: 5751: 5750: 5747: 5745: 5740: 5735: 5718: 5715: 5712: 5709: 5706: 5703: 5689: 5685: 5669: 5647: 5643: 5619: 5616: 5613: 5610: 5607: 5604: 5590: 5586: 5585: 5565: 5562: 5559: 5556: 5553: 5550: 5544: 5541: 5533: 5532: 5525: 5515: 5513: 5505: 5501: 5499: 5496: 5494: 5491: 5489: 5486: 5484: 5481: 5480: 5479: 5476: 5474: 5470: 5465: 5463: 5458: 5456: 5452: 5448: 5444: 5440: 5436: 5426: 5422: 5420: 5417:of polytopal 5416: 5410: 5403: 5400: 5399: 5398: 5396: 5393:Although the 5391: 5389: 5385: 5381: 5377: 5374:as among the 5373: 5372:Stephen Smale 5365: 5362: 5359: 5355: 5354: 5353: 5347: 5328: 5319: 5302: 5297: 5293: 5289: 5286: 5283: 5279: 5266: 5240: 5235: 5231: 5227: 5224: 5221: 5217: 5204: 5181: 5178: 5175: 5155: 5152: 5149: 5126: 5121: 5117: 5113: 5110: 5107: 5103: 5090: 5062: 5058: 5051: 5029: 5025: 5021: 5018: 4998: 4995: 4992: 4972: 4964: 4948: 4940: 4924: 4901: 4893: 4889: 4885: 4882: 4879: 4875: 4871: 4866: 4862: 4858: 4855: 4852: 4848: 4844: 4839: 4835: 4819: 4802: 4785: 4780: 4776: 4769: 4746: 4740: 4737: 4734: 4726: 4704: 4678: 4673: 4663: 4659: 4655: 4649: 4643: 4640: 4637: 4622: 4605: 4591: 4571: 4551: 4528: 4525: 4520: 4512: 4509: 4506: 4497: 4472: 4468: 4461: 4447: 4428: 4424: 4417: 4403: 4386: 4381: 4377: 4370: 4362: 4358: 4353: 4348: 4338: 4336: 4332: 4329:developed by 4328: 4324: 4320: 4301: 4296: 4292: 4285: 4277: 4273: 4269: 4266: 4256: 4247: 4245: 4241: 4237: 4233: 4229: 4224: 4214: 4212: 4208: 4202: 4200: 4196: 4191: 4189: 4185: 4181: 4177: 4159: 4155: 4152: 4147: 4142: 4132: 4130: 4126: 4122: 4118: 4114: 4110: 4106: 4101: 4099: 4098: 4093: 4089: 4088: 4083: 4082: 4071: 4068: 4064: 4060: 4056: 4051: 4049: 4045: 4044:local maximum 4041: 4037: 4033: 4032:local minimum 4029: 4025: 4021: 4018:, which is a 4017: 4002: 3998: 3996: 3992: 3988: 3984: 3976: 3972: 3967: 3963: 3959: 3955: 3952: 3949: 3945: 3940: 3936: 3932: 3928: 3925: 3924: 3923: 3921: 3917: 3912: 3908: 3901: 3894: 3889: 3885: 3878: 3871: 3866: 3862: 3855: 3848: 3844: 3839: 3835: 3828: 3821: 3817: 3814:Suppose that 3812: 3804: 3802: 3798: 3794: 3789: 3787: 3783: 3779: 3775: 3771: 3767: 3763: 3759: 3749: 3747: 3743: 3739: 3729: 3725: 3721: 3718: 3713: 3709: 3706: 3701: 3700: 3699: 3697: 3692: 3690: 3686: 3682: 3672: 3668: 3664: 3661: 3656: 3652: 3649: 3644: 3643: 3642: 3640: 3628: 3623: 3621: 3616: 3614: 3609: 3608: 3606: 3605: 3598: 3595: 3593: 3590: 3589: 3586: 3583: 3581: 3578: 3577: 3574: 3571: 3569: 3566: 3565: 3562: 3559: 3557: 3554: 3553: 3550: 3547: 3545: 3542: 3541: 3538: 3535: 3533: 3530: 3529: 3526: 3525: 3522: 3519: 3518: 3505: 3503: 3497: 3495: 3492: 3488: 3485: 3481: 3477: 3473: 3469: 3460: 3456: 3452: 3449: 3445: 3442: 3438: 3434:dual problem, 3433: 3429: 3428: 3426: 3422: 3419: 3415: 3412: 3408: 3407: 3406: 3400: 3396: 3392: 3389: 3385: 3382: 3378: 3374:dual problem, 3373: 3369: 3368: 3366: 3362: 3358: 3355: 3351: 3348: 3344: 3343: 3342: 3340: 3336: 3332: 3326: 3302: 3299: 3294: 3286: 3282: 3272: 3268: 3258: 3254: 3244: 3240: 3230: 3226: 3219: 3213: 3208: 3202: 3195: 3188: 3181: 3175: 3170: 3165: 3157: 3153: 3143: 3139: 3129: 3125: 3115: 3111: 3101: 3097: 3089: 3083: 3076: 3070: 3065: 3060: 3053: 3049: 3041: 3037: 3031: 3024: 3019: 3014: 3007: 3003: 2995: 2991: 2985: 2978: 2973: 2968: 2963: 2958: 2953: 2946: 2941: 2936: 2929: 2925: 2921: 2914: 2910: 2906: 2901: 2895: 2886: 2871: 2863: 2862: 2861: 2858: 2842: 2838: 2834: 2829: 2825: 2821: 2816: 2812: 2784: 2781: 2776: 2772: 2768: 2763: 2759: 2755: 2750: 2746: 2742: 2737: 2733: 2729: 2724: 2720: 2712: 2710: 2709: 2705: 2691: 2688: 2683: 2679: 2675: 2670: 2666: 2662: 2657: 2653: 2649: 2644: 2640: 2636: 2631: 2627: 2619: 2617: 2616: 2612: 2598: 2595: 2590: 2586: 2582: 2577: 2573: 2569: 2564: 2560: 2556: 2551: 2547: 2543: 2538: 2534: 2526: 2524: 2523: 2519: 2505: 2502: 2497: 2493: 2489: 2484: 2480: 2476: 2471: 2467: 2459: 2456: 2455: 2451: 2435: 2431: 2427: 2422: 2418: 2414: 2409: 2405: 2401: 2396: 2392: 2382: 2379: 2378: 2377: 2369: 2355: 2288: 2285: 2277: 2274: 2271: 2259: 2243: 2228: 2222: 2217: 2212: 2188: 2182: 2175: 2155: 2148: 2129: 2124: 2118: 2109: 2094: 2086: 2085: 2084: 2082: 2078: 2077: 2072: 2068: 2044: 2039: 2033: 2026: 2020: 2015: 2010: 2002: 1998: 1988: 1984: 1977: 1971: 1966: 1960: 1953: 1946: 1940: 1935: 1930: 1922: 1918: 1908: 1904: 1897: 1890: 1882: 1878: 1870: 1866: 1856: 1852: 1844: 1840: 1832: 1827: 1821: 1811: 1795: 1787: 1783: 1773: 1769: 1762: 1755: 1747: 1743: 1735: 1731: 1724: 1714: 1713: 1712: 1704: 1690: 1687: 1682: 1678: 1674: 1671: 1668: 1663: 1659: 1651: 1649: 1648: 1644: 1630: 1627: 1622: 1618: 1614: 1609: 1605: 1601: 1596: 1592: 1588: 1583: 1579: 1571: 1569: 1568: 1564: 1550: 1547: 1542: 1538: 1534: 1529: 1525: 1521: 1516: 1512: 1508: 1503: 1499: 1491: 1489: 1488: 1484: 1470: 1467: 1462: 1458: 1454: 1449: 1445: 1437: 1432: 1431: 1427: 1411: 1407: 1403: 1398: 1394: 1390: 1385: 1381: 1377: 1372: 1368: 1356: 1353: 1348: 1341: 1334: 1327: 1312: 1305: 1298: 1291: 1287: 1283: 1279: 1276: 1266: 1257: 1255: 1232: 1229: 1221: 1213: 1205: 1202: 1197: 1187: 1179: 1146: 1145: 1144: 1142: 1140: 1114: 1111: 1106: 1102: 1094: 1091: 1086: 1082: 1070: 1069: 1067: 1066: 1063: 1060: 1059: 1036: 1032: 1028: 1021: 1017: 1011: 1007: 1003: 998: 994: 988: 984: 974: 970: 966: 959: 955: 949: 945: 941: 936: 932: 926: 922: 912: 908: 904: 897: 893: 887: 883: 879: 874: 870: 864: 860: 848: 847: 845: 844: 840: 837: 836: 819: 815: 809: 805: 801: 796: 792: 786: 782: 778: 770: 766: 762: 757: 753: 746: 738: 737: 734: 730: 729: 728: 726: 725:Standard form 720:Standard form 717: 715: 711: 707: 703: 700: 696: 694: 690:problems and 689: 688: 683: 673: 671: 667: 663: 658: 656: 652: 648: 642: 639: 635: 631: 627: 623: 618: 616: 612: 608: 604: 600: 595: 591: 587: 584: 580: 575: 573: 569: 562: 558: 552: 548: 539: 536: 534: 530: 526: 522: 518: 514: 510: 505: 503: 482: 452: 444: 436: 388: 372: 364: 275: 267: 241: 233: 177:Find a vector 163: 162: 161: 159: 158:standard form 154: 152: 148: 144: 140: 136: 132: 128: 124: 120: 117: 113: 110:, subject to 109: 106: 102: 97: 95: 91: 87: 83: 79: 75: 68: 64: 59: 52: 48: 44: 39: 33: 19: 8963: 8871:Local search 8817:Edmonds–Karp 8773:Bellman–Ford 8570: 8543:minimization 8375:Gauss–Newton 8325:Quasi–Newton 8310:Trust region 8218:Optimization 8152: 8142: 8130: 8121: 8105:. Springer. 8102: 8083: 8067: 8059: 8051: 8032: 8007: 7973: 7957: 7936: 7905: 7893: 7867: 7863: 7853: 7832: 7824: 7794: 7766: 7719: 7715: 7688: 7662: 7654: 7643: 7634: 7609: 7605: 7597: 7590: 7584: 7575: 7567: 7561: 7532: 7520: 7511: 7502: 7490:. Retrieved 7481: 7469:. Retrieved 7460: 7449:. Retrieved 7445: 7436: 7401: 7397: 7387: 7360: 7356: 7346: 7327: 7321: 7302: 7296: 7277: 7271: 7252: 7246: 7219: 7213: 7114: 7108: 7067: 7061: 7052: 7022:(1): 79–84. 7019: 7018:. Series A. 7015: 7009: 6998: 6992:Murty (1983) 6987: 6976: 6965: 6922: 6918: 6858: 6819: 6812: 6787: 6783: 6765: 6761: 6723: 6693: 6687: 6669:(2): 43–48. 6666: 6662: 6633:. Retrieved 6629: 6620: 6601: 6573: 6567: 6558: 6555:Econometrica 6554: 6548: 6539: 6535: 6529: 6509:Shadow price 6113: 6112: 6102: 6048:GNU MathProg 5965: 5964: 5796: 5795: 5785: 5771: 5765: 5761: 5754: 5748: 5736: 5687: 5683: 5588: 5583: 5582: 5530: 5529: 5527: 5509: 5477: 5466: 5461: 5459: 5450: 5446: 5438: 5432: 5423: 5411: 5407: 5392: 5369: 5350: 5325: 5011:matrix by a 4808: 4723:denotes the 4694:time, where 4611: 4453: 4409: 4357:N. Karmarkar 4354: 4350: 4331:Naum Z. Shor 4275: 4271: 4262: 4253: 4235: 4220: 4205:solvable in 4203: 4198: 4192: 4173: 4124: 4120: 4116: 4112: 4108: 4104: 4102: 4095: 4091: 4085: 4079: 4077: 4062: 4058: 4054: 4052: 4013: 3999: 3994: 3990: 3986: 3982: 3980: 3974: 3970: 3965: 3961: 3957: 3953: 3947: 3943: 3938: 3934: 3930: 3926: 3919: 3915: 3910: 3906: 3899: 3892: 3887: 3883: 3876: 3869: 3864: 3860: 3853: 3846: 3842: 3837: 3833: 3826: 3819: 3815: 3813: 3810: 3790: 3755: 3745: 3741: 3737: 3735: 3727: 3723: 3719: 3716: 3714:subject to: 3707: 3704: 3693: 3688: 3684: 3680: 3678: 3670: 3666: 3662: 3659: 3657:subject to: 3650: 3647: 3636: 3580:Bin covering 3498: 3493: 3490: 3486: 3483: 3479: 3475: 3468:weak duality 3464: 3458: 3454: 3450: 3447: 3443: 3440: 3431: 3424: 3420: 3417: 3413: 3410: 3404: 3398: 3394: 3390: 3387: 3383: 3380: 3371: 3364: 3360: 3356: 3353: 3349: 3346: 3341:problem as: 3338: 3335:dual problem 3330: 3328: 2859: 2803: 2457:subject to: 2375: 2303: 2081:block matrix 2074: 2066: 2064: 1710: 1346: 1339: 1332: 1325: 1310: 1303: 1296: 1289: 1285: 1281: 1274: 1272: 1251: 1137: 1135: 1061: 838: 732: 724: 723: 705: 701: 698: 692: 687:network flow 685: 679: 659: 643: 619: 596: 592: 588: 576: 565: 537: 506: 294: 155: 131:intersection 101:optimization 98: 81: 77: 73: 72: 9026:Criss-cross 8984:Mixed (MCP) 8891:Tabu search 8302:Convergence 8273:Line search 8062:. Springer. 7070:(2): 4–10. 6981:Todd (2002) 6317:Mathematica 6127:Brief info 6115:Proprietary 5982:Brief info 5870:MPL License 5824:MIT License 5813:Brief info 4359:proposed a 3645:Minimize: 3639:covering LP 3585:Bin packing 3466:dual. The 3446:subject to 3416:subject to 3386:subject to 3352:subject to 1812:subject to 1434:Subject to: 638:game theory 609:. In 1941, 385:is a given 135:half spaces 119:constraints 9046:Categories 8722:algorithms 8230:heuristics 8222:Algorithms 7570:: 211–214. 7553:References 7512:lehigh.edu 7492:3 December 7471:3 December 7451:2023-08-10 7363:(2): 170. 7337:2004.07470 7312:1905.04447 7287:1810.07896 7262:1503.01752 6733:0387948333 6635:2023-11-20 6561:: 115–135. 6373:SAS System 6275:What'sBest 6173:, Gurobi, 6069:MPS format 6063:An LP and 5798:Permissive 5044:matrix in 4265:worst-case 4244:worst case 4209:, i.e. of 4139:See also: 4135:Algorithms 4070:function. 4063:infeasible 3981:So if the 3791:Finding a 3784:, and the 3772:, and the 3702:Maximize: 3696:packing LP 3508:Variations 3439:Minimize 3432:asymmetric 3379:Minimize 2384:Maximize: 1358:Maximize: 574:is named. 533:assignment 529:scheduling 500:specify a 361:are given 227:subject to 63:polyhedron 8677:Paradigms 8576:quadratic 8293:Gradients 8255:Functions 7724:CiteSeerX 7420:0030-364X 7365:CiteSeerX 7100:123541868 7084:0343-6993 6927:CiteSeerX 6820:CVPR 2011 6400:A visual 6187:APMonitor 6164:Analytica 6117:licenses: 6090:R-Project 6060:LGPL v2.1 5969:licenses: 5939:Apache v2 5924:Apache v2 5855:Apache v2 5800:licenses: 5716:∈ 5710:∣ 5648:∗ 5617:∈ 5611:∣ 5563:≥ 5554:∣ 5270:~ 5208:~ 5176:α 5150:ω 5094:~ 5030:α 5022:× 4996:× 4973:α 4949:α 4925:ω 4859:α 4856:− 4840:ω 4823:~ 4708:~ 4626:~ 4242:, in the 4195:algorithm 3409:Maximize 3372:symmetric 3345:Maximize 3300:≥ 2922:− 2907:− 2864:Maximize 2782:≥ 2663:⋅ 2637:⋅ 2570:⋅ 2544:⋅ 2428:⋅ 2402:⋅ 2286:≥ 2272:≥ 2130:− 2087:Maximize 2016:≥ 1936:≤ 1715:maximize 1688:≥ 1669:≥ 1628:≤ 1615:⋅ 1589:⋅ 1548:≤ 1535:⋅ 1509:⋅ 1468:≤ 1404:⋅ 1378:⋅ 1254:variables 1230:≥ 1222:∧ 1214:≤ 1203:∧ 1188:∈ 1180:∣ 1112:≥ 1092:≥ 1029:≤ 967:≤ 905:≤ 706:convexity 509:economics 483:≥ 453:≤ 402:↦ 268:≥ 242:≤ 147:algorithm 51:level set 8908:Software 8785:Dijkstra 8616:exchange 8414:Hessians 8380:Gradient 8141:, 1997, 8139:Yinyu Ye 8031:(2006). 8005:(1979). 7904:(2001). 7843:Odysseus 7823:, 1993, 7793:(1983). 7669:pivoting 7540:Archived 7044:33463483 6850:17707171 6742:35318475 6679:Archived 6415:See also 6056:lp solve 5979:License 5959:in Java 5810:License 5584:integral 5531:integral 5437:(IP) or 4333:and the 4188:stalling 4184:polytope 4067:polytope 3752:Examples 1278:hectares 699:duality, 695:problems 521:planning 151:polytope 141:-valued 47:polytope 9015:Dantzig 9011:Simplex 8751:Kruskal 8741:Borůvka 8731:Minimum 8468:General 8226:methods 7884:6464735 7813:0720547 7775:1438311 7754:2794181 7746:1464775 7677:Benders 7626:3689647 7446:mit.edu 7092:0883185 7036:1045573 6957:2794181 6949:1464775 6804:7257867 6307:Mathcad 5934:SuanShu 5512:Padberg 5443:NP-hard 4199:cycling 4092:minimum 3898:, 3875:, 3852:, 3825:, 3319:Duality 2372:Example 1260:Example 649:in the 634:duality 568:Fourier 542:History 525:routing 363:vectors 43:polygon 8613:Basis- 8571:Linear 8541:Convex 8385:Mirror 8342:L-BFGS 8228:, and 8109: 8090: 8074: 8039: 8015: 7986: 7934:about 7912: 7882: 7811: 7801: 7773: 7752: 7744: 7726: 7703: 7624: 7428:171894 7426: 7418: 7367: 7234: 7098: 7090: 7082: 7042: 7034: 6955: 6947: 6929: 6848: 6838: 6802: 6740: 6730: 6700: 6608: 6580: 6542:: 1–9. 6396:VisSim 6381:XPRESS 6352:OptimJ 6293:MATLAB 6226:FortMP 6207:TOMLAB 6177:, and 6171:XPRESS 6144:ALGLIB 6046:-like 5992:GPL 2+ 5988:ALGLIB 5894:, and 5840:, and 5760:in an 5753:in an 5419:graphs 4917:time, 4727:, and 4446:time. 4317:time. 4238:, the 4151:convex 4005:Theory 3780:, the 3768:, the 3482:, and 3339:primal 3331:primal 2804:where 2304:where 2083:form: 1139:matrix 387:matrix 365:, and 121:. Its 105:linear 67:planes 9031:Lemke 8999:Basis 8812:Dinic 8720:Graph 7880:S2CID 7750:S2CID 7622:JSTOR 7424:JSTOR 7332:arXiv 7307:arXiv 7282:arXiv 7257:arXiv 7096:S2CID 7040:S2CID 6953:S2CID 6846:S2CID 6824:(PDF) 6800:S2CID 6659:(PDF) 6522:Notes 6327:MOSEK 6283:Maple 6271:LINGO 6264:LINDO 6215:Excel 6197:CPLEX 6179:MOSEK 6133:AIMMS 6124:Name 6104:MINTO 5976:Name 5904:Pyomo 5819:Gekko 5807:Name 5688:value 5142:when 4046:is a 4034:is a 4026:is a 3950:, and 3797:graph 3795:of a 3367:≥ 0; 1068:e.g. 846:e.g. 739:e.g. 125:is a 103:of a 8778:SPFA 8746:Prim 8340:and 8107:ISBN 8088:ISBN 8072:ISBN 8037:ISBN 8013:ISBN 8001:and 7984:ISBN 7910:ISBN 7841:for 7799:ISBN 7781:and 7701:ISBN 7675:and 7494:2021 7473:2021 7416:ISSN 7232:ISBN 7080:ISSN 6836:ISBN 6738:OCLC 6728:ISBN 6698:ISBN 6606:ISBN 6578:ISBN 6388:GAMS 6235:GAMS 6203:GAMS 6154:AMPL 6077:Qoca 6044:AMPL 6027:glpk 6005:LGPL 5949:SOCP 5919:SCIP 5888:SOCP 5880:QCQP 5865:JuMP 5850:GLOP 5834:QCQP 5386:and 5168:and 4941:and 4232:cube 4174:The 4084:for 4022:. A 3918:and 3744:and 3687:and 3461:≥ 0. 3401:≥ 0. 1345:and 1331:and 1141:form 676:Uses 599:USSR 470:and 339:and 139:real 114:and 8708:cut 8573:and 7872:doi 7734:doi 7693:doi 7614:doi 7406:doi 7375:doi 7361:140 7224:doi 7179:1.5 7072:doi 7024:doi 6937:doi 6828:doi 6792:doi 6766:224 6671:doi 6364:/OR 6362:SAS 6277:). 6094:GPL 6081:GPL 6065:MIP 6036:API 6031:GPL 6018:CPL 6014:CLP 5957:SQP 5953:SDP 5909:BSD 5896:MIP 5892:NLP 5884:SDP 5842:MIP 5838:NLP 5701:max 5602:max 5449:or 5256:to 4965:. 4853:2.5 4781:2.5 4521:1.5 4473:2.5 4382:3.5 3730:≥ 0 3673:≥ 0 1154:max 256:and 160:as 96:). 9048:: 8224:, 8220:: 7982:. 7878:. 7868:91 7866:. 7845:.) 7809:MR 7807:. 7777:. 7771:MR 7748:. 7742:MR 7740:. 7732:. 7720:79 7718:. 7699:. 7683:.) 7620:. 7608:. 7568:28 7566:. 7510:. 7444:. 7422:. 7414:. 7402:42 7400:. 7396:. 7373:. 7359:. 7355:. 7330:. 7230:. 7094:. 7088:MR 7086:. 7078:. 7066:. 7038:. 7032:MR 7030:. 7020:46 6951:. 6945:MR 6943:. 6935:. 6923:79 6921:. 6913:; 6900:^ 6886:^ 6870:^ 6844:. 6834:. 6798:. 6786:. 6774:^ 6764:. 6750:^ 6736:. 6712:^ 6677:. 6665:. 6661:. 6644:^ 6628:. 6592:^ 6559:24 6557:. 6540:13 6538:. 6408:. 6375:. 6181:. 5955:, 5951:, 5947:, 5945:QP 5890:, 5886:, 5882:, 5878:, 5876:QP 5836:, 5832:, 5830:QP 5457:. 5445:. 5318:. 5298:18 4246:. 4213:. 4050:. 3726:, 3722:≤ 3669:, 3665:≥ 3637:A 3496:. 3457:, 3453:= 3427:; 3423:≤ 3397:, 3393:≥ 3363:, 3359:≤ 3303:0. 2785:0. 1012:32 989:31 950:22 927:21 888:12 865:11 731:A 531:, 527:, 523:, 78:LP 9017:) 9013:( 9001:- 8942:e 8935:t 8928:v 8706:/ 8210:e 8203:t 8196:v 8115:. 8096:. 8045:. 8021:. 7992:. 7918:. 7886:. 7874:: 7785:. 7756:. 7736:: 7709:. 7695:: 7650:) 7628:. 7616:: 7610:2 7514:. 7496:. 7475:. 7454:. 7430:. 7408:: 7381:. 7377:: 7340:. 7334:: 7315:. 7309:: 7290:. 7284:: 7265:. 7259:: 7240:. 7226:: 7193:) 7190:L 7187:) 7184:n 7175:) 7171:n 7168:+ 7165:m 7162:( 7159:+ 7154:2 7150:n 7146:) 7143:n 7140:+ 7137:m 7134:( 7131:( 7128:( 7124:O 7102:. 7074:: 7068:9 7046:. 7026:: 6959:. 6939:: 6852:. 6830:: 6806:. 6794:: 6788:4 6744:. 6706:. 6673:: 6667:1 6638:. 6614:. 6586:. 5786:g 5766:c 5722:} 5719:P 5713:x 5707:x 5704:c 5698:{ 5684:c 5670:P 5644:x 5623:} 5620:P 5614:x 5608:x 5605:c 5599:{ 5589:c 5569:} 5566:0 5560:x 5557:A 5551:x 5548:{ 5545:= 5542:P 5506:. 5339:: 5306:) 5303:L 5294:/ 5290:1 5287:+ 5284:2 5280:n 5276:( 5267:O 5244:) 5241:L 5236:6 5232:/ 5228:1 5225:+ 5222:2 5218:n 5214:( 5205:O 5182:1 5179:= 5156:2 5153:= 5130:) 5127:L 5122:6 5118:/ 5114:1 5111:+ 5108:2 5104:n 5100:( 5091:O 5068:) 5063:2 5059:n 5055:( 5052:O 5026:n 5019:n 4999:n 4993:n 4905:) 4902:L 4899:) 4894:6 4890:/ 4886:1 4883:+ 4880:2 4876:n 4872:+ 4867:2 4863:/ 4849:n 4845:+ 4836:n 4832:( 4829:( 4820:O 4789:) 4786:L 4777:n 4773:( 4770:O 4750:) 4747:A 4744:( 4741:z 4738:n 4735:n 4705:O 4682:) 4679:L 4674:d 4669:) 4664:2 4660:d 4656:+ 4653:) 4650:A 4647:( 4644:z 4641:n 4638:n 4635:( 4632:( 4623:O 4592:L 4572:n 4552:d 4532:) 4529:L 4526:n 4517:) 4513:d 4510:+ 4507:n 4504:( 4501:( 4498:O 4478:) 4469:n 4465:( 4462:O 4434:) 4429:3 4425:n 4421:( 4418:O 4390:) 4387:L 4378:n 4374:( 4371:O 4305:) 4302:L 4297:6 4293:n 4289:( 4286:O 4276:L 4272:n 4236:D 4160:. 4125:x 4121:d 4117:d 4113:x 4109:d 4059:x 4055:x 3995:j 3991:j 3987:i 3983:i 3977:. 3975:m 3971:i 3966:i 3962:y 3958:i 3954:w 3948:n 3944:j 3939:j 3935:z 3931:j 3927:x 3920:y 3916:x 3911:n 3907:z 3903:2 3900:z 3896:1 3893:z 3888:m 3884:w 3880:2 3877:w 3873:1 3870:w 3865:m 3861:y 3857:2 3854:y 3850:1 3847:y 3843:y 3838:n 3834:x 3830:2 3827:x 3823:1 3820:x 3816:x 3746:c 3742:b 3738:A 3732:, 3728:x 3724:b 3720:x 3717:A 3711:, 3708:x 3705:c 3689:c 3685:b 3681:A 3675:, 3671:y 3667:c 3663:y 3660:A 3654:, 3651:y 3648:b 3626:e 3619:t 3612:v 3494:y 3491:b 3489:= 3487:x 3484:c 3480:y 3476:x 3459:y 3455:c 3451:y 3448:A 3444:y 3441:b 3425:b 3421:x 3418:A 3414:x 3411:c 3399:y 3395:c 3391:y 3388:A 3384:y 3381:b 3365:x 3361:b 3357:x 3354:A 3350:x 3347:c 3295:] 3287:5 3283:x 3273:4 3269:x 3259:3 3255:x 3245:2 3241:x 3231:1 3227:x 3220:[ 3214:, 3209:] 3203:P 3196:F 3189:L 3182:0 3176:[ 3171:= 3166:] 3158:5 3154:x 3144:4 3140:x 3130:3 3126:x 3116:2 3112:x 3102:1 3098:x 3090:z 3084:[ 3077:] 3071:1 3066:0 3061:0 3054:2 3050:P 3042:1 3038:P 3032:0 3025:0 3020:1 3015:0 3008:2 3004:F 2996:1 2992:F 2986:0 2979:0 2974:0 2969:1 2964:1 2959:1 2954:0 2947:0 2942:0 2937:0 2930:2 2926:S 2915:1 2911:S 2902:1 2896:[ 2884:: 2872:z 2843:5 2839:x 2835:, 2830:4 2826:x 2822:, 2817:3 2813:x 2777:5 2773:x 2769:, 2764:4 2760:x 2756:, 2751:3 2747:x 2743:, 2738:2 2734:x 2730:, 2725:1 2721:x 2692:P 2689:= 2684:5 2680:x 2676:+ 2671:2 2667:x 2658:2 2654:P 2650:+ 2645:1 2641:x 2632:1 2628:P 2599:F 2596:= 2591:4 2587:x 2583:+ 2578:2 2574:x 2565:2 2561:F 2557:+ 2552:1 2548:x 2539:1 2535:F 2506:L 2503:= 2498:3 2494:x 2490:+ 2485:2 2481:x 2477:+ 2472:1 2468:x 2436:2 2432:x 2423:2 2419:S 2415:+ 2410:1 2406:x 2397:1 2393:S 2356:z 2335:x 2313:s 2289:0 2282:s 2278:, 2275:0 2268:x 2244:] 2237:b 2229:0 2223:[ 2218:= 2213:] 2206:s 2197:x 2189:z 2183:[ 2176:] 2169:I 2162:A 2156:0 2149:0 2141:T 2135:c 2125:1 2119:[ 2107:: 2095:z 2045:. 2040:] 2034:0 2027:0 2021:[ 2011:] 2003:2 1999:x 1989:1 1985:x 1978:[ 1972:, 1967:] 1961:P 1954:F 1947:L 1941:[ 1931:] 1923:2 1919:x 1909:1 1905:x 1898:[ 1891:] 1883:2 1879:P 1871:1 1867:P 1857:2 1853:F 1845:1 1841:F 1833:1 1828:1 1822:[ 1796:] 1788:2 1784:x 1774:1 1770:x 1763:[ 1756:] 1748:2 1744:S 1736:1 1732:S 1725:[ 1691:0 1683:2 1679:x 1675:, 1672:0 1664:1 1660:x 1631:P 1623:2 1619:x 1610:2 1606:P 1602:+ 1597:1 1593:x 1584:1 1580:P 1551:F 1543:2 1539:x 1530:2 1526:F 1522:+ 1517:1 1513:x 1504:1 1500:F 1471:L 1463:2 1459:x 1455:+ 1450:1 1446:x 1412:2 1408:x 1399:2 1395:S 1391:+ 1386:1 1382:x 1373:1 1369:S 1350:2 1347:x 1343:1 1340:x 1336:2 1333:x 1329:1 1326:x 1322:2 1318:1 1314:2 1311:P 1307:2 1304:F 1300:1 1297:P 1293:1 1290:F 1286:P 1282:F 1275:L 1237:} 1233:0 1226:x 1218:b 1210:x 1206:A 1198:n 1193:R 1184:x 1176:x 1169:T 1163:c 1157:{ 1115:0 1107:2 1103:x 1095:0 1087:1 1083:x 1037:3 1033:b 1022:2 1018:x 1008:a 1004:+ 999:1 995:x 985:a 975:2 971:b 960:2 956:x 946:a 942:+ 937:1 933:x 923:a 913:1 909:b 898:2 894:x 884:a 880:+ 875:1 871:x 861:a 820:2 816:x 810:2 806:c 802:+ 797:1 793:x 787:1 783:c 779:= 776:) 771:2 767:x 763:, 758:1 754:x 750:( 747:f 487:0 479:x 457:b 449:x 445:A 420:x 413:T 407:c 398:x 373:A 348:b 326:c 304:x 276:. 272:0 264:x 246:b 238:x 234:A 217:x 210:T 204:c 185:x 76:( 34:. 20:)

Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.

Knowledge

Linear programming

Index