Integer programming is a powerful tool for solving complex optimization problems with discrete decisions. It extends linear programming by restricting some or all variables to integer values, enabling more accurate modeling of real-world scenarios involving indivisible units or yes/no choices.

Formulating integer programming models requires careful identification of decision variables, constraints, and objective functions. This process involves translating problem requirements into mathematical expressions, incorporating logical conditions, and capturing discrete choices using binary variables or special ordered sets.

Formulating Integer Programming Models

Integer Programming Fundamentals

• Integer programming models involve decision variables restricted to integer values for problems with indivisible units or discrete choices
• Objective function represents the goal to be optimized (maximizing profit or minimizing cost) as a linear function of decision variables
• Constraints define limitations or requirements of the problem using mathematical expressions (inequalities or equalities)
• Binary variables (0-1 variables) model yes/no decisions or mutually exclusive choices
• Special ordered sets (SOS) model situations where only one or a specific number of variables from a set can be non-zero

Advanced Modeling Techniques

• Logical constraints incorporate if-then conditions using binary variables and appropriate mathematical formulations
• Real-world applications include production planning, resource allocation, facility location, and scheduling problems
• Piecewise linear functions model non-linear relationships using binary variables and additional constraints
• Multi-period models capture time-dependent decisions and constraints across multiple planning periods
• Network flow problems represent transportation or distribution systems using nodes and arcs

Example Formulations

• Knapsack problem: Maximize value of items selected subject to weight limit constraint
• Traveling salesman problem: Minimize total distance traveled visiting all cities exactly once
• Facility location problem: Determine optimal locations for facilities to minimize total cost of serving customers
• Production planning: Decide production quantities for multiple products over time periods to meet demand and minimize costs
• Vehicle routing problem: Optimize delivery routes for a fleet of vehicles serving multiple customers

Identifying Variables and Constraints

Decision Variables

• Represent quantities or choices to be determined with clearly defined domains (non-negative integers, binary)
• Examples:
  • Number of products to manufacture
  • Binary variable for selecting a facility location
• Must capture all relevant decisions in the problem context
• Can include auxiliary variables to simplify constraint formulation

Constraint Types

• Structural constraints define fundamental limitations (resource availability, capacity restrictions)
• Logical constraints enforce relationships between decision variables using binary variables
• Bound constraints specify allowable ranges for decision variables (upper and lower limits)
• Integrality constraints explicitly state which variables must take integer values
• Linking constraints establish connections between different sets of variables (multi-period or multi-stage problems)
• Non-negativity constraints ensure decision variables cannot take negative values in most practical applications

Constraint Formulation Examples

• Resource constraint: $\sum_{i=1}^n a_i x_i \leq b$ (total resource usage ≤ available resource)
• Logical constraint: $y \leq Mx$ (variable y can be positive only if binary variable x is 1, M is a large constant)
• Assignment constraint: $\sum_{j=1}^m x_{ij} = 1$ (exactly one option j must be assigned to each item i)
• Capacity constraint: $\sum_{i=1}^n q_i x_i \leq C$ (total production quantity ≤ production capacity)
• Demand satisfaction: $x_i \geq d_i$ (production of item i must meet or exceed demand)

Linear vs Integer Programming

Problem Structure

• Linear programming (LP) allows continuous decision variables, integer programming (IP) requires some or all variables to be integers
• Feasible region in LP forms a convex polyhedron, IP consists of discrete points within or on polyhedron boundaries
• Mixed Integer Programming (MIP) combines continuous and integer variables for more flexible modeling

Solution Methods

• LP problems solved efficiently using algorithms like simplex method
• IP problems require more complex techniques (branch-and-bound, cutting plane methods)
• Relaxation techniques solve LP relaxation of IP problem to obtain bounds and guide integer solution search
• Computational complexity generally higher for IP problems compared to LP, often making them NP-hard

Special Cases

• Certain problem structures (network flow problems) may have integer solutions when formulated as LP (integrality property)
• Totally unimodular constraint matrices guarantee integer solutions for LP relaxations
• Some IP problems can be solved efficiently using specialized algorithms (matching problems, shortest path)

Modeling Considerations

• IP models can capture discrete decisions and logical relationships more accurately than LP
• LP relaxations provide bounds and insights for IP problems
• Choosing between LP and IP depends on problem requirements, solution quality, and computational resources

Interpreting Integer Programming Solutions

Solution Characteristics

• Optimal solutions provide discrete, implementable decisions satisfying all constraints and optimizing objective function
• Integer solutions represent indivisible units (people, machines, products) directly applicable to real-world scenarios
• Feasibility often more critical than optimality in complex IP problems

Analysis Techniques

• Sensitivity analysis more complex in IP than LP due to discrete nature of feasible region
• Integrality gap (difference between IP optimal solution and LP relaxation) provides insight into impact of integer restrictions
• Post-optimality analysis examines alternative optimal solutions and near-optimal solutions for decision-maker options

Practical Interpretation

• Translate mathematical solution into actionable decisions (production quantities, resource allocations)
• Consider implementation challenges and practical constraints not captured in the model
• Evaluate solution robustness to parameter uncertainties or data inaccuracies
• Communicate results effectively to stakeholders, explaining trade-offs and limitations

Example Interpretations

• Facility location problem: Optimal solution indicates which facilities to open and which customers to assign to each
• Production planning: Solution provides production quantities for each product in each time period
• Vehicle routing: Optimal routes and schedules for each vehicle in the fleet to serve all customers