A Tutorial on Integer Programming - Clemson University

← Back to document page

A Tutorial on Integer ProgrammingG erard Cornu ejolsMichael A. TrickMatthew J. Saltzman1995These notes are meant as an adjunct to Chapter 9 and 10 in Murty. Youare responsible for what appears in these notes as well as Sections { , { , , , in the Introduction22 Modeling with Integer CapitalBudgeting ........................ MultiperiodCapitalBudgeting ............. Knapsack ............................. a Single-Constraint 0-1 IP to a KnapsackProblem .......................... and General Integer Knapsack Prob-lems ............................ TheLockboxProblem ...................... 133 Solving Integer RelationshiptoLinearProgramming .............. BranchandBound ........................ CuttingPlaneTechniques .................... CutsforSpecialStructure.}}

AMPL, one can easily change a linear programming problem into an integer program. The downside of all this power, however, is that problems with as few as 40 variables can be beyond the abilities of even the most sophisticated computers. While these small problems are somewhat arti cial, most real

  Programming, Linear programming, Linear, Lamp, Tutorials