Skip to content
Tutorials Center
My learning

Topics

Lesson 12 of 49 ยท Linear and Integer Programming

Chapter 3 Overview: Linear and Integer Programming

Chapter 3 overview: why linear programs have corner-point solutions, how the graphical method, simplex, duality and integer programming fit together.

Chapter 2 taught you to write models. This chapter teaches you how they are solved and what the solution tells you. Linear programming (LP) is the workhorse of operations research: the objective and all constraints are linear, and a clean mathematical fact makes the problems easy to solve. Integer programming (IP) adds the requirement that some variables are whole numbers, which makes problems harder but far more realistic.

By the end of the chapter you will be able to solve small LPs by drawing them, solve any LP by hand with the simplex method, read the "price" information in the dual problem, and understand how integer programs are solved by branch and bound.

A hero picture with four tiles: graphical method, simplex method, duality, and integer programming, each with a tiny drawing
Four tools for one family of problems: a picture for two variables, a table for many, prices from the dual, and a search tree for whole numbers.

What you will learn

  • Why the best plan of a linear program always lies at a corner of the feasible region.
  • How the four lessons of the chapter build on one another.
  • The vocabulary you need before the details: feasible region, vertex, basis, relaxation.

Key terms

Feasible region: all plans that satisfy every constraint; for an LP it is a convex polygon (or polyhedron).

Vertex (corner point): a feasible point where constraint boundaries meet; the places where optimal solutions live.

Basis: the set of variables that are allowed to be nonzero at a vertex.

Dual problem: a companion LP whose variables are the prices of the original resources.

LP relaxation: the integer program with the integer requirement dropped.

The central fact

If a linear program has an optimal solution, then at least one vertex of its feasible region is optimal. Why? Imagine sliding a straight line (all plans with the same profit) across the region in the direction of increasing profit. The last point it touches before leaving the region is a corner, or an entire edge that ends in corners. The same reasoning works in any number of dimensions with flat surfaces instead of lines.

This fact turns a search over infinitely many plans into a search over finitely many corners. Even so, the number of corners can be astronomically large for big models, which is why we need an organized way to walk from corner to corner: the simplex method.

Graphical method

Two variables Draw the region
Corners Compare their profits

Perfect for building intuition.

1 / 4

What each lesson covers

  1. The graphical method solves two-variable problems by drawing, and shows the three special outcomes: no solution, unbounded, and many solutions.
  2. The simplex method explains slack variables, the tableau and pivoting, and you run a small simplex program yourself.
  3. Duality and sensitivity analysis introduces the dual problem, complementary slackness and the ranges over which a solution stays valid.
  4. Integer programming and branch and bound shows why rounding fails and how branching proves optimality.
  5. Chapter 3 review recaps and tests the chapter.

Warm-up: count the corners

For small problems we can find the best corner by brute force: take every pair of constraint lines, find where they cross, keep the crossings that satisfy all constraints, and compare their profits. The program below does exactly that for Sunrise Bakery, and it is a preview of why corners matter.

Python Brute-force the corners of the bakery

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.

Slide the objective line

Drag the sliders. The pink dashed line is the set of plans with the same profit as the best corner. Notice that the best corner changes only when the slope of that line passes the slope of a region edge, and that the optimum is always a corner (or a whole edge when two corners tie).

Common misconceptions

"Linear programming means writing a computer program." The word programming here means planning or scheduling. It predates software.

"The optimum of an LP can be in the middle of the region." For a linear objective the best value is on the boundary, at a corner.

"Integer problems are just LPs with rounding." Rounding can give infeasible or far-from-optimal plans. Chapter 3 shows the proper methods.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Where can the optimal solution of a linear program be found?

    If an optimum exists, at least one vertex of the feasible region is optimal.
  2. 2. What does "programming" mean in linear programming?

    The term comes from military planning programs; it has nothing to do with computer code.
  3. 3. What is the LP relaxation of an integer program?

    Relaxation lets variables take fractional values, which gives an easy LP bound.
  4. 4. Which method is designed to walk from corner to corner of the feasible region?

    The simplex method moves along edges to neighbouring corners that improve the objective.

Summary

  • A linear program has an optimal vertex whenever it has an optimum, so search can be restricted to corners.
  • The graphical method, simplex, duality and branch and bound are four tools you will use in order.
  • The dual problem prices the resources; integer programming handles whole-number decisions.
  • "Programming" means planning.

Next: The Graphical Method