5.1 Formulation of integer and mixed-integer problems

Integer and mixed-integer programming tackle discrete decision-making scenarios, logical constraints, and combinatorial optimization problems. These methods are crucial for solving real-world issues like resource allocation, facility location, and scheduling, which require integer solutions.

Formulating integer models involves using binary, general integer, and continuous variables. The objective function and constraints incorporate integer decision impacts, logical conditions, and special ordered sets. This approach offers greater modeling flexibility compared to linear programming, but faces computational challenges.

Understanding Integer and Mixed-Integer Programming

Problems for integer programming

Top images from around the web for Problems for integer programming

• 

  Black-box combinatorial optimization using models with integer-valued minima | Annals of ... View original

  Is this image relevant?

• 

  Integer programming models and branch-and-cut approaches to generalized {0,1,2}-survivable ... View original

  Is this image relevant?

• 

  Frontiers | A Mixed-Integer Linear Programming Formulation for Optimizing Multi-Scale Material ... View original

  Is this image relevant?

• 

  Black-box combinatorial optimization using models with integer-valued minima | Annals of ... View original

  Is this image relevant?

• 

  Integer programming models and branch-and-cut approaches to generalized {0,1,2}-survivable ... View original

  Is this image relevant?

1 of 3

Top images from around the web for Problems for integer programming

• 

  Black-box combinatorial optimization using models with integer-valued minima | Annals of ... View original

  Is this image relevant?

• 

  Integer programming models and branch-and-cut approaches to generalized {0,1,2}-survivable ... View original

  Is this image relevant?

• 

  Frontiers | A Mixed-Integer Linear Programming Formulation for Optimizing Multi-Scale Material ... View original

  Is this image relevant?

• 

  Black-box combinatorial optimization using models with integer-valued minima | Annals of ... View original

  Is this image relevant?

• 

  Integer programming models and branch-and-cut approaches to generalized {0,1,2}-survivable ... View original

  Is this image relevant?

1 of 3

• Discrete decision-making scenarios involve allocating indivisible resources (machine assignments) and determining facility locations (warehouse placement)
• Logical constraints encompass yes/no decisions (product launch) and if-then conditions (production line setup)
• Combinatorial optimization problems include traveling salesman (optimal route planning) and knapsack (item selection within weight limit)
• Scheduling problems address job shop scheduling (task sequencing on machines) and airline crew scheduling (assigning crews to flights)
• Network design problems optimize supply chain networks (distribution center locations) and telecommunications planning (cell tower placement)

Formulation of integer models

• Decision variables use binary (product selection), general integer (number of units), and continuous variables (production quantities)
• Objective function maximizes profit or minimizes cost incorporating integer decision impacts (fixed costs, economies of scale)
• Constraints include logical constraints using binary variables (mutually exclusive choices), capacity constraints with integer variables (machine utilization), and budget constraints (investment limits)
• Special ordered sets Type 1 allow at most one non-zero variable (selecting one supplier) while Type 2 permit two adjacent non-zero variables (piecewise linear approximations)
• Indicator constraints link binary variables to other constraints (activating production lines)
• Big M method uses large constants to enforce logical conditions (facility opening triggers fixed costs)

Linear vs integer programming

• Continuous vs discrete solution space differentiates LP (real-valued variables) from IP (integer-restricted variables)
• Convexity properties contrast LP's convex feasible region with IP's non-convex region due to integer restrictions
• Solution methods differ with LP using simplex and interior point methods while IP employs branch and bound and cutting plane algorithms
• Optimality guarantees vary as LP finds global optima efficiently while IP struggles with global optimality assurance
• Modeling flexibility allows IP to capture complex logical relationships beyond LP's linear constraints
• Computational complexity classifies LP as polynomial-time solvable while IP is generally NP-hard

Limitations of integer programming

• Computational complexity results in exponential worst-case time complexity hindering large-scale problem solving
• Integrality gap between IP and LP relaxation solutions impacts solution quality and algorithm performance
• Branching strategies in branch and bound require effective variable selection balancing tree depth and width
• Cutting plane generation identifies strong valid inequalities but incurs computational overhead
• Symmetry in problem formulation creates multiple equivalent solutions expanding the search space
• Numerical instability arises from rounding errors in fractional solutions and sensitivity to input data changes
• Memory requirements for storing branch and bound trees and managing cut pools can be substantial
• Solution time unpredictability manifests in performance variability across similar instances complicating resource estimation