A Tutorial on Integer Programming
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.}}
In fact, ignoring integrality constraints, the optimal linear pro-gramming solution is x 1 =1,x 2=1,x 3=0:5, x 4 = 0 for a value of $22,000. Unfortunately, this solution is not integral. Rounding x 3 down to 0 gives a feasible solution with a value of $19,000. There is …
Download A Tutorial on Integer Programming
Information
Domain:
Source:
Link to this page:
Please notify us if you found a problem with this document: