Chapter II: Integer Linear Programming

From Continuous to Discrete Optimization

Discover how to solve optimization problems where decisions must be whole numbers, like the number of cars to produce, employees to hire, or projects to select. Welcome to the world of Integer Linear Programming!

1. From Linear Programming to Integer Linear Programming

The Limitation of Continuous Solutions

🚗 Real-World Problem: Automotive Manufacturing

Scenario: A car manufacturer wants to optimize production of two vehicle models to maximize profit.

Linear Programming solution says:

Produce 1.33 cars of Model A and 3.33 cars of Model B

❌ The Problem: You cannot manufacture 0.33 of a car!

❌ Naive Solution: Just round to 1 car of Model A and 3 cars of Model B?

⚠️ Warning: This may not be optimal, or even feasible!

Other Real-World Situations Requiring Integer Solutions

👥 Workforce Planning

Number of employees to hire or schedule for shifts

Can't hire 2.7 employees!

🏗️ Project Selection

Which investment projects to undertake

Either invest or don't: no half measures!

🏪 Facility Location

Number of warehouses or stores to open

A store is either open or closed!

📦 Production Batches

Number of production runs or batches

Must produce in whole units!

Comparing LP and ILP: A Simple Example

The Same Problem, Two Different Formulations

📐 Linear Programming (LP)

Variables: x₁, x₂ ∈ ℝ₊ (positive real numbers)

Maximize: z = 3x₁ + 2x₂

Subject to:
2x₁ + x₂ ≤ 6
x₁ + 2x₂ ≤ 8
x₁, x₂ ≥ 0

Optimal Solution:
x₁ = 1.33, x₂ = 3.33
Z = 10.67

🔢 Integer Linear Programming (ILP)

Variables: x₁, x₂ ∈ ℤ₊ (positive integers)

Maximize: z = 3x₁ + 2x₂

Subject to:
2x₁ + x₂ ≤ 6
x₁ + 2x₂ ≤ 8
x₁, x₂ ∈ ℤ₊

Optimal Solution:
x₁ = 1, x₂ = 3
Z = 9

⚠️ Critical Warning

The integer optimal solution is NOT simply the rounded continuous solution!

In this example:

  • Rounding LP solution (1.33, 3.33) → (1, 3) gives Z = 9 ✓ (happens to be optimal)
  • But rounding to (1, 4) gives Z = 11, which is infeasible! (violates constraints)
  • In many cases, rounding produces suboptimal or infeasible solutions

2. LP vs ILP: Key Differences

Aspect Linear Programming (LP) Integer Linear Programming (ILP)
Variables Continuous: xi ∈ ℝ₊ Integer: xi ∈ ℤ₊
Optimal Solution (1.33, 3.33) (1, 3)
Objective Value Z = 10.67 Z = 9
Complexity Polynomial time (efficient) NP-hard (difficult for large problems)
Solution Method Simplex Algorithm Branch-and-Bound, Cutting Planes
Feasible Region Convex polyhedron (continuous) Discrete points (finite or countable)
Applications Resource allocation, blending Scheduling, selection, assignment

3. Types of Integer Programming Problems

Classification by Variable Types

1️⃣ Pure Integer Linear Programming (ILP)

Characteristic: ALL variables must be integers

x₁, x₂, ..., xₙ ∈ ℤ₊

Example: Determining how many units of different products to manufacture

  • x₁ = number of Product A units
  • x₂ = number of Product B units
  • Both must be whole numbers

2️⃣ Mixed Integer Linear Programming (MILP)

Characteristic: SOME variables are integers, SOME are continuous

x₁, x₂, ..., xₖ ∈ ℤ₊
xₖ₊₁, xₖ₊₂, ..., xₙ ∈ ℝ₊

Example: Production planning with batch decisions

  • y = number of production batches (integer)
  • x = quantity produced per batch (continuous)

3️⃣ Binary (0-1) Integer Programming

Characteristic: Variables can only be 0 or 1 (yes/no decisions)

x₁, x₂, ..., xₙ ∈ {0, 1}

Example: Project selection or facility location

  • xᵢ = 1 if project i is selected, 0 otherwise
  • yⱼ = 1 if warehouse j is opened, 0 otherwise

💡 Note: Binary programming is a special case of pure ILP, but it's so important and common that it deserves its own category!

4. Binary Variables: The Power of Yes/No Decisions

What Are Binary Variables?

Binary variables represent discrete yes-or-no decisions. They can only take two values: 0 or 1.

xᵢ = 1 if option i is selected (YES)
xᵢ = 0 if option i is not selected (NO)

Why Binary Variables Are So Useful

🎯 Represent Selection

Example: Choosing investment projects

  • xᵢ = 1: Invest in project i
  • xᵢ = 0: Don't invest in project i

🏪 Model Facility Status

Example: Store opening decisions

  • yⱼ = 1: Open store at location j
  • yⱼ = 0: Don't open store at location j

⚙️ Control Fixed Costs

Example: Production setup

  • zₖ = 1: Activate production line k (incur setup cost)
  • zₖ = 0: Line k inactive (no cost)

🔗 Enforce Logical Relationships

Example: Prerequisite constraints

  • If project A selected, then project B must be selected
  • Expressed as: xₐ ≤ xᵦ

5. Complete Example: Capital Budgeting (Project Selection)

Problem Statement

Context: An investment firm must decide which projects to fund from a portfolio of 4 potential investments.

Financial Data:

Project January Cost (k€) February Cost (k€) March Cost (k€) Net Return (k€)
1 58 42 35 217
2 44 33 28 125
3 26 19 16 88
4 23 17 14 109

💰 Budget Constraints:
• January: 120k€ available
• February: 90k€ available
• March: 75k€ available

🎯 Goal: Select projects to maximize total net return while staying within monthly budgets.

Mathematical Formulation

Step 1: Decision Variables

For each project i = 1, 2, 3, 4:

xᵢ = 1 if project i is selected
xᵢ = 0 if project i is not selected

xᵢ ∈ {0, 1} for i = 1, 2, 3, 4

Step 2: Objective Function

Maximize total net return:

Maximize: Z = 217x₁ + 125x₂ + 88x₃ + 109x₄

(Each project contributes its net return if selected)

Step 3: Budget Constraints

January budget (120k€):

58x₁ + 44x₂ + 26x₃ + 23x₄ ≤ 120

February budget (90k€):

42x₁ + 33x₂ + 19x₃ + 17x₄ ≤ 90

March budget (75k€):

35x₁ + 28x₂ + 16x₃ + 14x₄ ≤ 75

✅ Complete Model

Maximize: Z = 217x₁ + 125x₂ + 88x₃ + 109x₄

Subject to:
58x₁ + 44x₂ + 26x₃ + 23x₄ ≤ 120 (January)
42x₁ + 33x₂ + 19x₃ + 17x₄ ≤ 90 (February)
35x₁ + 28x₂ + 16x₃ + 14x₄ ≤ 75 (March)
x₁, x₂, x₃, x₄ ∈ {0, 1} (Binary)

Optimal Solution

📊 Decision:
x₁ = 1, x₂ = 0, x₃ = 1, x₄ = 1

Interpretation:

  • ✅ Select: Projects 1, 3, and 4
  • ❌ Reject: Project 2
  • 💰 Total Net Return: 217 + 88 + 109 = 414k€

Budget Utilization Verification:

Month Cost Calculation Total Spent Budget Status
January 58(1) + 0 + 26(1) + 23(1) 107k€ 120k€ ✅ OK
February 42(1) + 0 + 19(1) + 17(1) 78k€ 90k€ ✅ OK
March 35(1) + 0 + 16(1) + 14(1) 65k€ 75k€ ✅ OK

💡 Key Insight: All monthly budgets are satisfied, and we achieve the maximum possible return of 414k€. Notice that we have some unused budget each month, this is common in optimization, as the optimal solution balances multiple constraints.

6. Modeling Logical Relationships with Binary Variables

Common Logical Constraints in Binary Programming

1. Mutually Exclusive Choices

Situation: At most one of several options can be selected

Example: Projects 1 and 2 cannot both be undertaken

x₁ + x₂ ≤ 1

Interpretation: The sum is at most 1, so either x₁=1 OR x₂=1 OR both are 0

2. Conditional (If-Then) Relationships

Situation: If option A is chosen, then option B must also be chosen

Example: If project 3 is selected, then project 5 must be selected

x₃ ≤ x₅

Interpretation: If x₃=1, then x₅ must equal 1. But x₅ can be 1 even if x₃=0

3. Multiple Choice (Exactly One)

Situation: Exactly one option from a set must be selected

Example: Exactly one of projects 4 and 6 must be chosen

x₄ + x₆ = 1

Interpretation: Either x₄=1, x₆=0 OR x₄=0, x₆=1 (not both, not neither)

4. Capacity Constraints

Situation: At most K options can be selected

Example: At most 4 courses can be selected from 6 available

x₁ + x₂ + x₃ + x₄ + x₅ + x₆ ≤ 4

Interpretation: The sum of selected courses cannot exceed 4

5. Minimum Selection Requirements

Situation: At least K options must be selected

Example: At least 2 projects from a portfolio must be funded

x₁ + x₂ + x₃ + x₄ ≥ 2

Interpretation: The sum must be at least 2

6. Co-requisite (Both or Neither)

Situation: Two options must be selected together or not at all

Example: Projects 2 and 5 must be selected together

x₂ = x₅

Interpretation: Either both are 1 or both are 0

7. Practice Exercise: Course Selection Problem

Problem Statement

Context: A university student must select elective courses for the semester. There are 6 available courses, but various constraints apply.

Course Requirements and Constraints:

  1. Mutually Exclusive: Courses 1 and 2 cover similar material, so at most one can be taken
  2. Prerequisite: If Course 3 is taken, then Course 5 must also be taken (Course 5 is a prerequisite for Course 3)
  3. Multiple Choice: Exactly one of Courses 4 and 6 must be chosen
  4. Capacity: The student can register for at most 4 courses total

🎯 Your Task: Formulate this as a binary integer programming problem. Define variables, constraints, and an objective function.

Solution: Course Selection Model

Step 1: Decision Variables

For each course i = 1, 2, 3, 4, 5, 6:

xᵢ = 1 if course i is selected
xᵢ = 0 if course i is not selected

xᵢ ∈ {0, 1} for i = 1, 2, 3, 4, 5, 6

Step 2: Objective Function

Example objective: Maximize total educational value

Maximize: Z = 3x₁ + 4x₂ + 2x₃ + 5x₄ + 3x₅ + 4x₆

(Coefficients represent educational value/interest in each course)

Step 3: Logical Constraints

Constraint 1: Mutually exclusive (Courses 1 and 2)

x₁ + x₂ ≤ 1

Constraint 2: Conditional prerequisite (If Course 3, then Course 5)

x₃ ≤ x₅

Constraint 3: Multiple choice (Exactly one of Courses 4 and 6)

x₄ + x₆ = 1

Constraint 4: Maximum capacity (At most 4 courses)

x₁ + x₂ + x₃ + x₄ + x₅ + x₆ ≤ 4

✅ Complete Model

Maximize: Z = 3x₁ + 4x₂ + 2x₃ + 5x₄ + 3x₅ + 4x₆

Subject to:
x₁ + x₂ ≤ 1 (Mutually exclusive)
x₃ ≤ x₅ (Prerequisite)
x₄ + x₆ = 1 (Multiple choice)
x₁ + x₂ + x₃ + x₄ + x₅ + x₆ ≤ 4 (Capacity)
xᵢ ∈ {0, 1} for i = 1..6 (Binary)

📊 Example Solution

One possible optimal solution:

x₁ = 0, x₂ = 1, x₃ = 1, x₄ = 1, x₅ = 1, x₆ = 0

Interpretation: Select Courses 2, 3, 4, and 5

Total value: Z = 4 + 2 + 5 + 3 = 14

Verification:

  • Courses 1 and 2: Only Course 2 selected ✓
  • Prerequisite: Course 3 selected AND Course 5 selected ✓
  • Multiple choice: Course 4 selected (not Course 6) ✓
  • Capacity: 4 courses selected ✓

8. Solution Methods for Integer Programming

Why Is ILP Harder Than LP?

✅ Linear Programming (LP)

  • Complexity: Polynomial time
  • Feasible region: Continuous convex set
  • Optimum: At a vertex of the polyhedron
  • Method: Simplex algorithm (efficient)
  • Rounding: Not applicable

⚠️ Integer Linear Programming (ILP)

  • Complexity: NP-hard (exponential worst-case)
  • Feasible region: Discrete points
  • Optimum: Must search among integer points
  • Method: Branch-and-Bound, cutting planes
  • Rounding: May give infeasible/suboptimal solution

💡 Key Insight: Even small ILP problems can have an enormous number of possible integer solutions to check. For example, a problem with 20 binary variables has 2²⁰ = 1,048,576 possible combinations!

Main Solution Techniques

1. Branch-and-Bound

Idea: Intelligently explore solution tree

  • Relax integrality constraints
  • Branch on fractional variables
  • Prune branches that can't improve
  • Guaranteed optimal solution

Most widely used method

2. Cutting Planes

Idea: Add valid inequalities to tighten LP relaxation

  • Start with LP relaxation
  • Add cuts that remove fractional solutions
  • Don't eliminate any integer solutions
  • Iteratively solve and add cuts

Often combined with branch-and-bound

3. Heuristics

Idea: Find good (not necessarily optimal) solutions quickly

  • Rounding-based methods
  • Local search procedures
  • Metaheuristics (genetic algorithms, etc.)
  • Useful for very large problems

Trade optimality for speed

9. Branch-and-Bound Algorithm: Step-by-Step

Understanding Branch-and-Bound

Branch-and-Bound is the most powerful exact method for solving integer programming problems. It systematically explores the solution space while eliminating (pruning) branches that cannot lead to better solutions.

The Three Fundamental Steps

🔓 Step 1: Relaxation

What: Ignore integrality constraints

How: Solve the problem as a regular LP (continuous variables)

Why: LP gives an upper bound (for maximization) on the optimal integer solution

Example: If LP relaxation gives Z = 1055.56, we know the optimal integer solution cannot exceed this value.

🌳 Step 2: Branching

What: Divide the problem into subproblems

When: When LP solution is fractional (not all integers)

How: Choose a fractional variable xⱼ = 3.7, create two branches:

  • Left branch: xⱼ ≤ 3
  • Right branch: xⱼ ≥ 4

✂️ Step 3: Pruning

What: Eliminate branches that cannot improve the solution

When: Three pruning conditions (explained below)

Why: Avoid wasting time exploring unpromising branches

Key insight: Pruning is what makes branch-and-bound efficient!

The Three Pruning Criteria

1. Bound Pruning (Optimality)

Condition: Upper bound of node ≤ Best known integer solution (lower bound)

If UBnode ≤ LBglobal → PRUNE

Reasoning: This branch cannot produce a better integer solution than what we already have

Example: Current best integer solution Z = 1000. Node has UB = 995. Prune it!

2. Infeasibility Pruning

Condition: LP relaxation of the node is infeasible

If LP relaxation infeasible → PRUNE

Reasoning: If even the relaxed problem has no solution, the integer problem definitely has no solution

Example: After branching, constraints become x₁ ≥ 10 and x₁ ≤ 5 (impossible!)

3. Integrality Pruning (Completion)

Condition: LP relaxation solution is already all-integer

If LP solution is integer → UPDATE best solution, then PRUNE

Reasoning: We found a feasible integer solution! Update best known solution, no need to branch further

Example: LP gives x₁ = 2, x₂ = 5 (both integers). Update LB and prune.

10. Complete Example: Machine Shop Problem

Problem Statement

Context: A manufacturing workshop wants to purchase machines to maximize daily profit.

Machine Type Daily Profit Purchase Price Floor Space
Press €100/day €8,000 15 ft²
Lathe €150/day €4,000 30 ft²

🏭 Constraints:
• Total budget: €40,000
• Available floor space: 200 ft²

🎯 Question: How many presses and lathes should be purchased to maximize daily profit?

Mathematical Formulation

Decision Variables

x₁ = number of presses to purchase
x₂ = number of lathes to purchase
x₁, x₂ ∈ ℤ₊ (non-negative integers)

Objective Function

Maximize: Z = 100x₁ + 150x₂

(Maximize daily profit)

Constraints

8000x₁ + 4000x₂ ≤ 40000 (Budget constraint)
15x₁ + 30x₂ ≤ 200 (Space constraint)
x₁, x₂ ≥ 0 and integer

Branch-and-Bound Solution: Step-by-Step

🔓 Node 0: Initial LP Relaxation

Problem: Solve without integrality constraints

Maximize: Z = 100x₁ + 150x₂
Subject to:
8000x₁ + 4000x₂ ≤ 40000
15x₁ + 30x₂ ≤ 200
x₁, x₂ ≥ 0

LP Solution:

x₁ = 2.22, x₂ = 5.56
Z = 1055.56

❌ Problem: Solution is fractional (not integer)
✅ Action: Must branch! Upper bound = 1055.56

Variable selection for branching:

  • x₁ = 2.22 → fractional part = 0.22
  • x₂ = 5.56 → fractional part = 0.56 ← Largest fractional part!

Decision: Branch on x₂

🌳 First Branching: Creating Nodes 1 and 2

Node 0
Z = 1055.56
x₁=2.22, x₂=5.56
↓
┌─────────┴─────────┐
Node 1          Node 2
x₂ ≤ 5          x₂ ≥ 6

Node 1: x₂ ≤ 5

Additional constraint: x₂ ≤ 5

LP Solution:
x₁ = 2.5, x₂ = 5
Z = 1000

Still fractional (x₁ = 2.5)!
UB = 1000

Node 2: x₂ ≥ 6

Additional constraint: x₂ ≥ 6

LP Solution:
x₁ = 1.33, x₂ = 6
Z = 1033.33

Fractional (x₁ = 1.33)!
UB = 1033.33 → Best bound

📊 Status: Node 2 has best upper bound (1033.33) → Explore this branch next

🌳 Second Branching: From Node 2

Current node: Node 2 (x₁ = 1.33, x₂ = 6, Z = 1033.33)

Branch on: x₁ (fractional part = 0.33)

Node 0 (Z=1055.56)
↓
┌─────────┴─────────┐
Node 1          Node 2 (Z=1033.33)
(Z=1000)          x₂≥6
                    ↓
              ┌────┴────┐
            Node 3    Node 4
            x₁≤1      x₁≥2

Node 3: x₂ ≥ 6, x₁ ≤ 1

LP Solution:
x₁ = 1, x₂ = 6
Z = 1000

✅ Integer solution!
Update: LBglobal = 1000
Prune (integrality)

Node 4: x₂ ≥ 6, x₁ ≥ 2

LP Solution:
INFEASIBLE

❌ No feasible solution
(Constraints contradict)
Prune (infeasibility)

🌳 Exploring Remaining Node 1

Current best: LB = 1000 (x₁=1, x₂=6)

Node 1 to explore: x₁ = 2.5, x₂ = 5, UB = 1000

⚠️ Pruning Decision:

UBNode1 = 1000 ≤ LBglobal = 1000

Action: Prune by bound! (Cannot improve current best)

Note: Even if we explore it, the best integer solution from Node 1 branch would be (2, 5) with Z = 950, or (3, 4) with Z = 900, both worse than our current best of 1000.

🎉 Optimal Solution Found!

Final Decision

Purchase:
• 1 press (x₁ = 1)
• 6 lathes (x₂ = 6)

Maximum daily profit: €1,000

Constraint Verification

Constraint Calculation Limit Status
Budget 8000(1) + 4000(6) = 32,000 ≤ 40,000 ✅ OK
Space 15(1) + 30(6) = 195 ≤ 200 ✅ OK

Algorithm Performance

  • Total nodes explored: 4 (out of potentially many more)
  • Pruned nodes: 3 (saved computation time)
  • Optimal solution: Guaranteed by branch-and-bound
  • Efficiency: Much faster than complete enumeration!

11. Branch-and-Bound: General Algorithm

Complete Algorithm Pseudocode

INITIALIZATION:

1. Solve LP relaxation of original problem → Node 0

2. Set LB = -∞ (no integer solution yet)

3. Set UB = objective value of Node 0

4. Add Node 0 to list of active nodes


MAIN LOOP (while active nodes exist):

5. Select an active node from the list

6. Solve LP relaxation of this node


  IF LP is infeasible:

    → PRUNE (infeasibility), go to step 5


  IF LP objective ≤ LB:

    → PRUNE (bound), go to step 5


  IF LP solution is all-integer:

    → Update LB = LP objective

    → Save this solution as best

    → PRUNE (integrality), go to step 5


  OTHERWISE (fractional solution):

    7. Choose fractional variable xj

    8. Create two child nodes:

      • Left: add constraint xj ≤ ⌊xj*⌋

      • Right: add constraint xj ≥ ⌈xj*⌉

    9. Add both nodes to active list


TERMINATION:

10. When no active nodes remain:

    → Best integer solution found is optimal!

🎯 Key Algorithm Decisions

Node Selection Strategy:

  • Best-first: Select node with best (highest for max) upper bound
  • Depth-first: Explore one branch completely before backtracking
  • Breadth-first: Explore all nodes at same level before going deeper

Branching Variable Selection:

  • Largest fractional part: Choose variable furthest from integer
  • Most important variable: Based on objective coefficient
  • Pseudocost: Based on historical impact of branching on this variable

12. Software Tools for Integer Programming

📊 Excel Solver

Best for: Small educational problems (up to ~200 variables)

Pros:

  • Easy to use, widely available
  • Good for learning and teaching
  • Visual interface

Cons:

  • Limited to small problems
  • Slower than specialized solvers

🔧 LINDO/LINGO

Best for: Learning and medium-sized problems

Pros:

  • User-friendly interface
  • Educational licenses available
  • Good documentation

Cons:

  • Commercial license required
  • Less powerful than top solvers

⚡ Gurobi / CPLEX

Best for: Large industrial problems

Pros:

  • Extremely fast and powerful
  • Industry standard
  • Handles millions of variables
  • Free academic licenses

Cons:

  • Expensive commercial licenses
  • Steeper learning curve

🐍 Python (PuLP, OR-Tools)

Best for: Custom applications and integration

Pros:

  • Free and open-source
  • Flexible programming
  • Easy integration with data science

Cons:

  • Requires programming knowledge
  • Can use Gurobi/CPLEX as backend

13. Practice Exercises and Self-Assessment

📝 Exercise 1: Production Planning

Problem: A bakery produces two types of bread: white and whole wheat.

Type Flour (cups) Labor (hours) Profit/loaf
White 2 1 $3
Whole Wheat 3 1.5 $4

Available: 600 cups flour, 300 hours labor per day

Tasks:

  1. Formulate as an integer programming problem
  2. Solve LP relaxation graphically
  3. Use branch-and-bound to find optimal integer solution
  4. Verify your solution satisfies all constraints

📝 Exercise 2: Warehouse Location

Problem: A company must choose which warehouses to open from 4 potential locations.

Warehouse Fixed Cost Capacity Operating Cost/unit
1 $50,000 1000 units $5
2 $40,000 800 units $6
3 $45,000 900 units $5.5
4 $35,000 700 units $7

Requirements:

  • Total capacity must be at least 1500 units
  • At least 2 warehouses must be opened
  • If warehouse 1 is opened, warehouse 2 cannot be opened

Tasks:

  1. Define binary decision variables
  2. Formulate all constraints (including logical constraints)
  3. Write objective function to minimize total cost

✅ Self-Check Questions

  1. Why can't we just round LP solutions to get integer solutions?
  2. What are the three pruning criteria in branch-and-bound?
  3. How do you model "if-then" relationships with binary variables?
  4. What is the difference between pure ILP and mixed ILP?
  5. Why is ILP harder (NP-hard) compared to LP (polynomial)?
  6. When should you use branch-and-bound vs heuristics?

14. Additional Resources and Further Reading

📖 Recommended Textbooks

1. Introduction to Operations Research (Hillier & Lieberman)

Authors: Frederick S. Hillier, Gerald J. Lieberman

Edition: 11th Edition (latest)

Why it's great:

  • Comprehensive coverage of integer programming
  • Excellent examples and case studies
  • Clear explanation of branch-and-bound algorithm
  • Includes software tutorials (Excel Solver, LINGO)
  • Practice problems with solutions

📌 Best for: Comprehensive learning with theory and applications

2. Integer Programming (Wolsey)

Author: Laurence A. Wolsey

Edition: Wiley-Interscience, 1998

Why it's great:

  • Deep theoretical treatment of integer programming
  • Advanced formulation techniques
  • Cutting plane methods explained in detail
  • Polyhedral theory foundations
  • For serious students and researchers

📌 Best for: Advanced mathematical understanding and research

3. Operations Research: Applications and Algorithms (Winston)

Author: Wayne L. Winston

Edition: 4th Edition

Why it's great:

  • Practical, application-oriented approach
  • Many real-world examples and case studies
  • Step-by-step solution procedures
  • Accessible writing style for students
  • Excel-based examples and exercises

📌 Best for: Practical problem-solving and applications

4. Integer and Combinatorial Optimization (Nemhauser & Wolsey)

Authors: George L. Nemhauser, Laurence A. Wolsey

Edition: Wiley, 1988 (Classic reference)

Why it's great:

  • The definitive reference for integer programming
  • Comprehensive coverage of theory and algorithms
  • Detailed treatment of combinatorial optimization
  • Advanced formulation techniques
  • Used in graduate courses worldwide

📌 Best for: Graduate students and advanced practitioners

5. Model Building in Mathematical Programming (Williams)

Author: H. Paul Williams

Edition: 5th Edition, Wiley

Why it's great:

  • Focus on practical formulation techniques
  • Many real-world modeling examples
  • Covers binary variables and logical constraints extensively
  • Tips for good modeling practice
  • Accessible for beginners and useful for experts

📌 Best for: Learning effective formulation and modeling

6. Optimization in Operations Research (Rardin)

Author: Ronald L. Rardin

Edition: 2nd Edition, Pearson

Why it's great:

  • Comprehensive treatment of optimization methods
  • Good balance between theory and practice
  • Clear explanations with worked examples
  • Extensive problem sets for practice
  • Covers both linear and integer programming

📌 Best for: University courses and self-study

🌐 Online Resources

🎓 Academic Courses and Lectures

MIT OpenCourseWare - Integer Programming and Combinatorial Optimization

Link: ocw.mit.edu

  • Free video lectures from MIT professors
  • Complete course materials and problem sets
  • Lecture notes and exams with solutions

Stanford University - Discrete Optimization (Coursera)

Link: coursera.org

  • Interactive online course with quizzes
  • Practical programming assignments
  • Certificate upon completion
  • Topics include branch-and-bound, constraint programming

Operations Research: An Introduction (edX)

Link: edx.org

  • Multiple courses from top universities
  • Self-paced learning
  • Free audit option available

📺 YouTube Channels and Playlists

StatQuest with Josh Starmer

  • Clear, visual explanations of optimization concepts
  • Excellent for building intuition

MIT OpenCourseWare YouTube Channel

  • Complete lectures on operations research
  • Branch-and-bound demonstrations
  • Real-world applications

Search terms:

  • "Integer programming tutorial"
  • "Branch and bound algorithm explained"
  • "Binary variables in optimization"
  • "MILP modeling examples"

🛠️ Software Documentation and Tutorials

Gurobi Optimization Documentation

Link: gurobi.com/documentation

  • Comprehensive solver documentation
  • Modeling examples in multiple languages
  • Webinars and training videos
  • Free academic licenses available

IBM CPLEX Optimization Studio

Link: ibm.com/analytics/cplex-optimizer

  • Professional optimization software
  • Tutorials and getting started guides
  • Academic initiative for free licenses
  • Community forums

PuLP (Python Library) Documentation

Link: coin-or.github.io/pulp

  • Free, open-source Python library
  • Easy to learn for beginners
  • Many example problems with code
  • Active community support

Google OR-Tools

Link: developers.google.com/optimization

  • Free optimization software suite
  • Supports Python, C++, Java, C#
  • Excellent documentation and examples
  • Used by Google internally

🏛️ Professional Organizations and Communities

INFORMS (Institute for Operations Research and Management Sciences)

Link: informs.org

  • Leading professional society for OR
  • Journals: Operations Research, INFORMS Journal on Computing
  • Annual conferences and workshops
  • Student chapters and career resources
  • Case studies and applications library

Mathematical Optimization Society (MOS)

Link: mathopt.org

  • International society for optimization
  • Triennial optimization symposium
  • Research publications and newsletters

OR-Exchange Community Forum

Link: or.stackexchange.com

  • Q&A community for operations research
  • Ask questions and get expert answers
  • Browse solved problems and discussions
  • Active community of practitioners and academics

📊 Interactive Tools and Visualizations

Wolfram Alpha

Link: wolframalpha.com

  • Solve small optimization problems online
  • Visualize feasible regions graphically
  • Step-by-step solutions available

GeoGebra

Link: geogebra.org

  • Free graphing and visualization tool
  • Plot constraints and feasible regions
  • Interactive exploration of LP/ILP problems

Desmos Graphing Calculator

Link: desmos.com

  • Free online graphing calculator
  • Visualize 2D constraint systems
  • Easy to use and share

🎓 Chapter 2 Complete!

You've mastered Integer Linear Programming! You can now model and solve discrete optimization problems using binary variables, logical constraints, and the branch-and-bound algorithm.

Next Chapter: Scheduling with PERT and MPM methods

Last modified: Sunday, 19 October 2025, 11:52 AM