Omniadisce

Applied maths 19.2: Integer programming

Lesson Intermediate

Join free to take this lesson

Anyone can look around, but taking a lesson needs a free account. With one, your answers are checked step by step and your progress is saved, so you can stop and pick up where you left off on any device.

10 steps ยท about 17 min

By the end you can

  • Explain why rounding a linear programme's answer can be infeasible or far from the best
  • Model yes-or-no decisions with binary variables, including fixed costs
  • Solve a small knapsack problem by checking combinations, and see where greedy choice fails
  • Describe how branch and bound uses bounds to discard parts of the search

Who it is for: You have met linear programming (unit 14): maximise a linear objective subject to linear constraints.

The steps

  1. Round the answer?
  2. When the answer must be whole
  3. Rounding up
  4. Yes-or-no decisions: binary variables
  5. Pick the projects
  6. Load the van
  7. Branch and bound
  8. Explore or discard?
  9. Is it worth opening the line?
  10. Why not just round?

Discussion 0 comments

Log in to join the discussion.

× Enlarged view