Skip to main content
MathidiaMathematics Academy
Operations research
Lesson 51 of 75
Introduction

Integer programming

Objective. Formulate discrete optimisation models.

  1. 1. Learn
  2. 2. Worked example
  3. 3. Practice
  4. 4. Feedback
  5. 5. Continue

Learn: the key idea

Integer programming (IP) is optimisation where some or all decision variables must take integer (often 0–1) values, ruling out fractional solutions that linear programming allows. The LP relaxation drops integrality and gives a bound; branch and bound then splits the feasible region on a fractional variable, solving relaxations on each branch and pruning branches whose bound cannot beat the best known integer solution. For example, if the relaxation gives x = 2.4, branch into x ≤ 2 and x ≥ 3, resolve each, and keep exploring only promising branches. Binary variables model yes/no decisions such as selecting a project, and cutting planes can tighten the relaxation further before branching.

Worked example

In an integer programming model, a project selection problem has LP relaxation optimum x₁ = 1, x₂ = 1.5 with objective 2x₁ + 3x₂, and x₂ must be 0 or 1 in the integer model. Branching on x₂ gives two subproblems: x₂ = 0 (best integer solution x₁=1, x₂=0, objective 2) and x₂ = 1 (best integer solution x₁=1, x₂=1, objective 5). What is the optimal integer objective value?

11.5230101
Bar chart of the values 1, 1.5, 2, 3, 0, 1, 0, 1
  1. 1The LP relaxation is infeasible for the integer model since x₂ = 1.5 is not integer, so branch on x₂.
  2. 2Branch x₂ = 0: resolving gives feasible integer point x₁=1, x₂=0 with objective 2(1)+3(0) = 2.
  3. 3Branch x₂ = 1: resolving gives feasible integer point x₁=1, x₂=1 with objective 2(1)+3(1) = 5.
  4. 4Compare the two branch objectives, 2 and 5, and keep the larger as optimal.

Answer: 5

Concept mastery

Based on your past attempts at this lesson — the question types to practise again come first.

Complete a practice set to see your concept breakdown here.

Practice

Practice happens on its own screen, one question at a time. Answers stay hidden until you submit yours, and you can stop and pick up at the same question later.

Start practising

Common mistake. A common mistake is rounding the LP relaxation's fractional optimum to the nearest integers and assuming this is optimal or even feasible; rounding can violate constraints or give a far-from-optimal answer, so branch and bound (or explicit re-solving) is needed.

Your progress

Tick each step as you finish it. Your exact reading position is saved automatically, so Continue drops you back on the same line.

0 of 5 steps complete

Your place saves automatically as you read.

My dashboard