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:
- Mutually Exclusive: Courses 1 and 2 cover similar material, so at most one can be taken
- Prerequisite: If Course 3 is taken, then Course 5 must also be taken (Course 5 is a prerequisite for Course 3)
- Multiple Choice: Exactly one of Courses 4 and 6 must be chosen
- 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 1 Node 2 (Z=1033.33)
(Z=1000) x₂≥6
↓
┌────┴────┐
Node 3 Node 4
x₁≤1 x₁≥2
🌳 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:
📝 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:
- Define binary decision variables
- Formulate all constraints (including logical constraints)
- Write objective function to minimize total cost
✅ Self-Check Questions
- Why can't we just round LP solutions to get integer solutions?
- What are the three pruning criteria in branch-and-bound?
- How do you model "if-then" relationships with binary variables?
- What is the difference between pure ILP and mixed ILP?
- Why is ILP harder (NP-hard) compared to LP (polynomial)?
- 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