Skip to content

Full index

Models and bounds

  1. Integer linear programming
    • 1.1 Canonical maximization form
    • 1.2 Possible outcomes
    • 1.3 Complete enumeration
    • 1.4 Typical mistakes
    • 1.5 In summary
  2. Primal and dual bounds
    • 2.1 Primal and dual bounds
    • 2.2 Primal bounds: heuristic solutions
    • 2.3 The LP relaxation
    • 2.4 Rounding the solution of the LP relaxation
    • 2.5 Upper bounds on the variables
    • 2.6 Dual bounds
    • 2.7 Typical mistakes
    • 2.8 In summary

Strengthening the formulation

  1. Ideal formulations
    • 3.1 The convex hull
    • 3.2 Formulations and ideal formulations
    • 3.3 Comparing formulations
    • 3.4 Existence of ideal formulations
    • 3.5 Typical mistakes
    • 3.6 In summary
  2. Valid inequalities
    • 4.1 Valid inequalities
    • 4.2 Deriving valid inequalities by rounding
    • 4.3 Improving a valid inequality
    • 4.4 Families of valid inequalities and cuts
    • 4.5 Typical mistakes
    • 4.6 In summary
  3. Cover inequalities
    • 5.1 A constraint with positive coefficients and its LP relaxation
    • 5.2 Covers and cover inequalities
    • 5.3 Geometric interpretation
    • 5.4 Separation of cover inequalities
    • 5.5 Transforming the CSP into a complementary problem
    • 5.6 Extended cover inequalities
    • 5.7 Violation and distance from a cover inequality
    • 5.8 Typical mistakes
    • 5.9 In summary

Exact methods

  1. The cutting plane algorithm with Gomory fractional cuts
    • 6.1 Gomory fractional cuts
    • 6.2 A cutting-plane algorithm based on Gomory fractional cuts
    • 6.3 The car example
    • 6.4 Typical mistakes
    • 6.5 In summary
  2. LP-based branch-and-bound
    • 7.1 The idea in words and in a picture
    • 7.2 Definitions and notation
    • 7.3 The algorithm
    • 7.4 A short recap of the dual simplex algorithm
    • 7.5 Branching-variable selection strategies
    • 7.6 Branching-node selection strategies
    • 7.7 Worked examples on the car example
    • 7.8 Typical mistakes
    • 7.9 Extensions
    • 7.10 In summary
  3. Branch-and-cut
    • 8.1 Branch-and-cut algorithms
    • 8.2 Global and local valid inequalities
    • 8.3 Cut-and-branch and branch-and-cut
    • 8.4 Worked example: cut-and-branch with Gomory cuts
    • 8.5 Local cuts: an example
    • 8.6 Practical aspects
    • 8.7 Typical mistakes
    • 8.8 In summary

MIP solvers

  1. MIP solvers: what they do
    • 9.1 From the branch-and-cut algorithm to a MIP solver
    • 9.2 The components of a MIP solver
    • 9.3 How to read the log of Gurobi
    • 9.4 Typical mistakes
    • 9.5 In summary

MIP heuristics

  1. MIP heuristics
    • 10.1 MIP-based heuristics
    • 10.2 The examples of the chapter
    • 10.3 Rounding
    • 10.4 Diving
    • 10.5 The feasibility pump
    • 10.6 Improving an incumbent with a sub-MIP
    • 10.7 Relax-and-fix and fix-and-optimize
    • 10.8 Heuristics inside the solver
    • 10.9 What MIP-based heuristics give
    • 10.10 Python implementation
    • 10.11 Typical mistakes
    • 10.12 In summary