Integer Programming and Network FlowsThe book consists of three parts, linear programming, network flows, and integer programming. Emphasis is placed on the algorithm, its proof, theory and application. Much of the material is new and numerous references are given to cover all aspects of the subject. (Author). |
Common terms and phrases
a₁ all-integer arc capacities arc flows artificial variables Assume b₁ basic variables basis c₁ coefficients column vector components computation consider constraints convex combination convex cone convex hull convex set corresponding cost cut separating cycles cyclic group defined denote dual feasible dual program dual simplex method entries equal equation example face of P(G feasible solution finite number flow augmenting path g₁ Gomory cut group element hyperplane implies INCIDENCE MATRIX inequality integer program Lemma lexicographically linear program max-flow min-cut theorem maximal flow maximal flow values maximum minimum cut N₁ N₂ nodes nonbasic variables objective function obtained optimum solution pairs of nodes permanent label pivot column pivot row primal feasible problem Proof S₁ satisfied shortest chain shortest path shown in Fig simplex method slack variables solve starting tableau subset t₁ Theorem tree units of flow VERTICES x₁ x₂ y₁ zero