🧮Combinatorial Optimization Unit 4 – Integer programming

What's Integer Programming?

• Branch of mathematical optimization dealing with linear programs where some or all variables are restricted to integer values
• Extends linear programming by adding integrality constraints on decision variables
• Allows modeling of discrete optimization problems (scheduling, resource allocation, network design)
• Objective function and constraints are linear expressions, but variables must take on integer values
  • Can include binary variables (0 or 1) for modeling yes/no decisions
• More challenging to solve than continuous linear programs due to combinatorial nature of integer constraints
• Widely applicable in operations research, computer science, and engineering

Key Concepts and Terminology

• Decision variables represent the quantities to be determined (production quantities, resource assignments)
• Objective function expresses the goal to be optimized (maximizing profit, minimizing cost)
• Constraints define the feasible region and limitations (resource capacities, demand requirements)
• Integrality constraints restrict variables to integer values
• Linear relaxation removes integrality constraints, yielding a continuous linear program
  • Provides a bound on the optimal value of the integer program
• Branch-and-bound algorithm systematically enumerates candidate solutions by solving a series of linear relaxations
• Cutting planes are inequalities that cut off fractional solutions without eliminating any integer feasible solutions

Formulating Integer Programs

• Identify the decision variables and their domains (integer, binary)
• Define the objective function as a linear expression of the decision variables
  • Coefficients represent costs, profits, or weights associated with each variable
• Express constraints as linear inequalities or equations
  • Represent resource limitations, capacity constraints, and logical relationships
• Specify integrality constraints for variables that must take on integer values
• Ensure the formulation is complete, consistent, and captures all relevant aspects of the problem
• Consider alternative formulations that may lead to tighter linear relaxations or improved solver performance

Solving Techniques

• Branch-and-bound is the most common exact solution method for integer programs
  • Recursively partitions the feasible region into smaller subproblems
  • Solves linear relaxations to obtain bounds and prune suboptimal branches
• Cutting plane methods iteratively add valid inequalities (cuts) to strengthen the linear relaxation
  • Gomory cuts, mixed-integer rounding cuts, and problem-specific cuts
• Heuristics and approximation algorithms provide suboptimal solutions quickly
  • Rounding fractional solutions, local search, and metaheuristics (simulated annealing, genetic algorithms)
• Decomposition techniques exploit problem structure to solve large-scale instances
  • Benders decomposition, Dantzig-Wolfe decomposition, and column generation
• Preprocessing and reformulation techniques can tighten the formulation and improve solver performance
  • Variable fixing, constraint tightening, and symmetry breaking

Applications and Real-World Examples

• Production planning optimizes production quantities and resource allocation (manufacturing, supply chain management)
• Facility location determines optimal locations for warehouses, distribution centers, or service facilities
• Scheduling problems assign tasks to resources over time (machine scheduling, workforce planning)
• Network design optimizes the topology and capacity of transportation, communication, or energy networks
• Portfolio optimization selects investments to maximize return while managing risk
• Combinatorial auctions determine optimal allocation of items to bidders
• Crew scheduling assigns personnel to shifts or flights while satisfying complex rules and regulations

Common Challenges and Pitfalls

• Computational complexity increases exponentially with problem size, leading to long solve times
• Weak linear relaxations can result in large search trees and slow convergence
• Symmetry in the problem formulation can lead to redundant exploration of equivalent solutions
• Numerical instability can arise from ill-conditioned constraint matrices or large coefficients
• Modeling errors, such as incorrect constraints or omitted variables, can yield suboptimal or infeasible solutions
• Overconstraining the problem can result in infeasibility or overly narrow feasible regions
• Insufficient problem understanding can lead to inappropriate formulations or overlooked opportunities for simplification

Advanced Topics

• Stochastic integer programming incorporates uncertainty through probabilistic constraints or objective functions
• Robust optimization seeks solutions that remain feasible under worst-case parameter realizations
• Bi-level and multi-level optimization problems involve hierarchical decision-making (leader-follower games)
• Non-linear integer programming extends integer programming to include non-linear objective functions or constraints
  • Requires specialized solution techniques (outer approximation, generalized Benders decomposition)
• Constraint programming is an alternative paradigm for modeling and solving combinatorial problems
  • Expresses constraints using logical and arithmetic operators, allowing for more expressive modeling
• Integration of integer programming with other techniques (machine learning, simulation) for enhanced decision support

Practice Problems and Resources

• Textbooks on integer programming provide comprehensive coverage of theory and algorithms (Wolsey, Nemhauser and Wolsey)
• Online resources offer tutorials, case studies, and sample code (NEOS Guide, COIN-OR)
• Practice problem sets and competitions help develop modeling and solving skills (INFORMS optimization challenges)
• Optimization modeling languages (AMPL, GAMS, Pyomo) facilitate problem formulation and interface with solvers
• Open-source and commercial solvers implement state-of-the-art algorithms (CPLEX, Gurobi, SCIP)
• Research papers present novel formulations, algorithms, and applications, advancing the field of integer programming
• Collaboration with domain experts is crucial for understanding problem context and ensuring solution practicality