PL.ILP Integer Linear Programming - JulTob/Mathematics GitHub Wiki

1. Introduction to Integer Linear Programming (ILP)

  • ILP deals with problems where some or all variables are restricted to integer values. If all variables are integers, it's called pure integer programming; otherwise, it's mixed-integer programming (MIP).
  • If the objective function and constraints are linear, it is referred to as linear integer programming.
  • Applications: Includes transportation problems, task scheduling, knapsack problems, traveling salesman problems, and network design.
  • Challenges:
    • No universally computationally efficient algorithm for all ILP problems.
    • Rounding errors in numerical solutions can lead to infeasibility.

2. Basic Concepts

  • Relaxation: ILP problems are initially solved as continuous linear programs (LP) by ignoring the integer constraint. The solution is then rounded. However:
    1. Rounded solutions may not always be feasible.
    2. Even if feasible, the solution may deviate significantly from the optimal one.
  • Methods: Explicit enumeration and implicit enumeration (heuristics or exact methods like branch and bound).

3. Exact Solution Methods

Enumeration Techniques

  1. Explicit Enumeration:
    • Evaluates all feasible solutions and their objective function values.
    • Practically limited to small problems due to exponential growth in computational effort.
  2. Implicit Enumeration:
    • Explores only relevant feasible solutions using pruning techniques, such as the branch and bound method.

4. Branch and Bound Method

  • A systematic way to solve ILP problems by dividing them into smaller subproblems.
  • Steps:
    1. Solve the relaxed LP problem (ignoring integer constraints).
    2. If the relaxed solution satisfies integer constraints, it's optimal. Otherwise:
      • Choose a variable with a fractional value and branch the problem into two:
        • One where the variable is ≤ its floor.
        • One where the variable is ≥ its ceiling.
      • Repeat recursively for subproblems.
    3. Use bounding to discard subproblems:
      • Subproblems that are infeasible.
      • Subproblems whose bounds are worse than the best feasible solution found.
  • Algorithm Characteristics:
    • Continues until all subproblems are closed.
    • Computational complexity increases rapidly with problem size.

5. Heuristic Methods

  • Tailored to specific problems.
  • Provide quick, approximate solutions without guaranteeing optimality.
  • Commonly used for large-scale ILP problems.

6. Key Observations on Solution Methods

  • Rounding from relaxed LP can be unreliable.
  • Explicit enumeration is impractical for large problems.
  • Branch and bound combines feasibility checks and bounds optimization to efficiently handle moderate problem sizes.

This summary encapsulates the key theoretical points from the document. If you need a detailed explanation of specific algorithms, examples, or practical applications, let me know!