BU275 Lecture Notes - Lecture 8: Integer Lattice, Microbrewery, Feasible Region
Document Summary
A craft brewery: max 80x1+100x2, s. t. Now an integer program: every integer point creates a "lattice, integer points in the feasible region. Are called integer feasible points: possibly covered: The optimal solution to the ip is the integer feasible point with the best objective value: how to find the optimal solution: Lets try rounding the lp optimal solution (9, 2. 5) Round down because rounding up would make the solution unfeasible: candidates. 80(8)+100(3)=940: turns out the optimal solution to the ip is d(8,3) (which we couldn"t find by rounding, not covered: Let"s "branch" into 2 problems by rounding: Then solve them both as linear programs. We can add fake constraints (cutting planes) and solve the linear program the solution will be integer. Capital budgeting: a community is planning some public works: We have . 2 million and 12 acres, formulate an ip that maximizes the appeal of the chosen building. Let xi=1 if we choose building i=1 4.
