Revision #199 → #1368 · back to history
addedLinear programming (formal definition)f7a523d7d346
addedFeasible region as convex polytopeb1133d692f17
addedStandard form of a linear program9903191d09ca
addedObjective function3ed85799b3ea
addedStandard form (three parts)643bfc29bd9a
addedReduction of other forms to standard formf109d2e130d5
addedFarmer wheat/barley LPcd6494e97f42
addedAugmented (slack) form1c230c8e248a
addedFarmer LP in augmented form660acd65aa3b
addedPrimal and dual problem03783a46acaa
addedDual of the dual is the primal42952694063a
addedWeak duality theorem2230c720ac9a
addedStrong duality theorem6df7745124e7
addedUnbounded primal implies infeasible duala7121315c6b5
addedCovering LP3b4bb922b22f
addedPacking LP (dual of covering LP)3550e1ea902c
addedPacking and covering LP relaxations5ea4f65cf1e0
addedFractional coloring as covering LP42d1971b5296
addedComplementary slackness theorem255af9fd7feb
addedLinearity implies local optima are globalbb5dd9d1ed1d
addedOptimal solution need not existbc28712e0e77
addedOptimum attained on boundary when boundedb15b03c83d2a
addedConvex combination of solutions is a solution4779ed847827
addedBasic feasible solutions (vertices)43f4a8929ba1
addedFundamental theorem of linear inequalities (vertices)b228e017dd1e
addedSimplex algorithma46095eb3a9f
addedSimplex efficient on random problems37f8edd96784
addedKlee–Minty exponential worst case4e7ccadfe4e2
addedCriss-cross algorithmbd21335f79dc
addedWorst case on Klee–Minty cube413f409692b7
addedInterior-point methodsfae7cd82339f
addedEllipsoid method polynomial timeee11556eaffd
addedKarmarkar's improved polynomial boundbc0d5396df6e
addedVaidya 1987 running timeb403d5eb9482
addedVaidya 1989 running time54778002ea78
addedLee–Sidford input sparsity timecf002637d416
addedCohen–Lee–Song matrix-multiplication timeb6f5dc902310
addedPolytopes have subexponential diameter6cd11f6bee91
addedArrangement polytope graphs have small diameter0f066a406d16
addedInteger (linear) programmingb14ab89252cb
addedInteger programming is NP-hard4e64547ba5ff
added0–1 (binary) integer programming51b146e8814e
addedMixed integer programmingbde21b3cfc25
addedTotally unimodular subclasses solvablea8144f6eb672
addedIntegral linear programc3850efe22e7
addedIntegral polyhedrondea4a0e941ac
addedEdmonds–Giles equivalent characterization907ee2a0147c
addedConvex hull of solutions is integral polyhedrond142e5e26da3
addedTotal unimodularity implies integrality8f7865763667