Skip to content
Tutorials Center
My learning

Topics

Lesson 17 of 49 ยท Linear and Integer Programming

Chapter 3 Review: Linear and Integer Programming

Review Chapter 3: graphical method, simplex, duality and sensitivity, integer programming and branch and bound, with a one-page summary and ten quiz questions.

Chapter 3 covered the solution methods of linear and integer programming. You saw a picture-based method for two variables, the tableau method that scales to thousands of variables, the dual problem that prices resources, and branch and bound for whole-number decisions. This review lays out the chapter on one page, lets you compare the LP bound with the integer optimum on random problems, and tests the whole chapter with ten questions.

A one-page summary: graphical method, simplex, duality and branch and bound, each with its key fact and the bakery numbers
Chapter 3 in one picture: corners, pivots, prices and branches, all anchored on the bakery numbers 520, 26.67 and 6.67.

What you will learn

  • A recap of every lesson in Chapter 3.
  • When to use each method.
  • How big the gap between LP and integer optimum can be, by experiment.

Key terms

Corner (vertex): where optimal LP solutions live. Slack: unused resource. Pivot: a simplex step.

Shadow price: value of one more unit of a resource. Reduced cost: profit rise needed before a product is made.

Relaxation bound: LP value that bounds the integer optimum. Incumbent: best integer plan so far.

Recap table

Lesson Core idea Bakery number
Overview Optimum is at a corner Corners (0,0), (8,0), (6,4), (0,7)
Graphical method Draw, intersect, slide the profit line Best corner (6, 4), $520
Simplex Slack variables, entering/leaving, pivot Path 0 โ†’ 480 โ†’ 520
Duality and sensitivity Dual prices resources; ranging Prices 26.67 and 6.67; cake profit range 20 to 80
Integer programming Relaxation bound, branch, prune Rounding fails; (6, 3) = 480 vs LP 486.67

Which method when?

Situation Tool
Two variables, want insight Graphical method
Many variables, continuous linprog (simplex or interior point)
Want prices and ranges Dual values and sensitivity report
Whole numbers or yes/no milp (branch and cut)
Network structure (Chapter 4) Specialized network algorithms; LP is already integer

Practice: how big is the integrality gap?

The experiment solves random whole-number problems and compares the LP relaxation with the true integer optimum. The relaxation is never smaller (for maximization) and the gap is usually modest, but sometimes it is wide.

Python LP relaxation vs integer optimum on random models

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Flashcards: Chapter 3 terms

Choosing a tool: three short scenarios

Scenario 1. A bakery with two products wants to see, on one picture, why a particular plan is best and how the answer moves when a price changes. Use the graphical method. Two variables are all it needs, and the iso-profit line shows the effect of a price change directly: tilting the line moves the optimum from corner to corner.

Scenario 2. A refinery has 2,000 decision variables and 600 constraints, and the planner wants to know which capacity limits are costing the most money. Use simplex or an interior-point solver through linprog, and read the shadow prices. No picture is possible, but the dual values rank the bottlenecks, and sensitivity ranges say how far each can be trusted.

Scenario 3. A courier firm must decide how many vans to buy and which of 12 depots to open. The numbers of vans are whole numbers and the depots are yes/no decisions. Use milp. The LP relaxation gives an upper bound on profit, and the solver's gap tells you how far a plan can be from the best possible. If the gap is large and time is short, you accept a good plan, and Chapter 8 will show how heuristics find one.

Three questions that catch most errors

  1. Does the solution satisfy every constraint when I substitute it by hand? A solver can only optimize the model you wrote.
  2. Which constraints are binding, and what are their shadow prices? They tell you where the business is limited.
  3. Would rounding be safe? If the answer is "not sure", solve the integer model.

Common misconceptions

"Simplex and interior-point methods give different answers." Both find an optimal value; if several optima exist they may return different optimal plans.

"Shadow prices apply forever." Only within their ranges.

"A zero integrality gap is typical." It happens for network-structured models; elsewhere the gap can be large.

Check your understanding

Quick check ยท 10 questions

of 10 answered You scored / 10 ยท perfect!

  1. 1. Why is it enough to check corner points of an LP's feasible region?

    A linear objective reaches its optimum at a vertex of the feasible region.
  2. 2. At the first simplex step for the bakery, which variable leaves the basis?

    The ratios are 16 รท 2 = 8 and 14 รท 1 = 14; the smaller one leaves.
  3. 3. What are the shadow prices of oven and baker hours at the optimum?

    From the final tableau or the dual: u = 80/3 and v = 20/3.
  4. 4. What does the infeasible outcome of an LP mean?

    Infeasible means the feasible region is empty.
  5. 5. With bread profit at $40, the plan (6, 4) stays optimal for cake profits between...

    The objective slope must lie between the slopes of the two binding constraints, which gives 20 to 80.
  6. 6. A resource has slack at the optimum. Its shadow price is...

    Complementary slackness: slack implies zero price.
  7. 7. In branch and bound for a maximization IP, a node is pruned by bound when...

    Nothing in that branch can beat the incumbent, so it need not be explored.
  8. 8. The bakery with 15 oven hours and 13 baker hours has LP optimum 486.67. What is the whole-batch optimum?

    The best whole-batch plan is (6, 3) with profit 480.
  9. 9. Which problem types have LP relaxations whose corners are already integer?

    Network flow structure guarantees integer corners when the data are integers.
  10. 10. The dual of a maximization problem with โ‰ค constraints is...

    The dual minimizes bยทy subject to Aแต€y โ‰ฅ c, y โ‰ฅ 0.

Summary

  • The optimum of an LP is at a corner; graphical solutions show why, and simplex walks along edges.
  • The dual gives shadow prices; sensitivity ranges tell when plans and prices remain valid.
  • Integer programs use relaxation bounds and branching; rounding is unreliable.
  • Pick the method by problem size, structure and whether you need prices or whole numbers.
  • Bakery anchors: LP optimum $520 at (6, 4), shadow prices 26.67 and 6.67, whole-batch optimum 480 at (6, 3) in the 15/13 variant.

Next: Chapter 4 overview: Network Optimization