🧮Combinatorial Optimization Unit 3 – Linear Programming and Duality

Key Concepts and Definitions

• Linear programming (LP) involves optimizing a linear objective function subject to linear equality and inequality constraints
• Decision variables represent the quantities to be determined in an optimization problem
• Objective function is a linear function of the decision variables that is either maximized or minimized
• Constraints are linear equalities or inequalities that define the feasible region for the decision variables
• Feasible region is the set of all points satisfying all constraints in an LP problem
• Optimal solution is a feasible solution that achieves the best value of the objective function
• Slack variables are added to inequality constraints to convert them into equalities
• Surplus variables are subtracted from inequality constraints to convert them into equalities

Linear Programming Fundamentals

• LP problems aim to allocate limited resources optimally to achieve a specific objective
• Standard form of an LP problem:
  • Maximize or minimize a linear objective function
  • Subject to linear equality and inequality constraints
  • Non-negativity constraints on decision variables
• Graphical method can solve LP problems with two decision variables by plotting constraints and identifying the optimal point
• Simplex method is an iterative algorithm for solving LP problems with more than two variables
  • Moves from one vertex of the feasible region to another, improving the objective function value at each step
• Sensitivity analysis examines how changes in the problem parameters affect the optimal solution

Formulating LP Problems

• Identify decision variables and express them in mathematical terms
• Determine the objective function as a linear combination of decision variables
• Identify constraints and express them as linear equalities or inequalities
  • Consider resource limitations, demand requirements, and other problem-specific restrictions
• Ensure all variables are non-negative, unless otherwise specified
• Express the problem in standard form for solving
• Verify the linearity of the objective function and constraints
• Check for redundant or inconsistent constraints that may affect the feasible region

Solving LP Problems

• Graphical method for problems with two decision variables
  • Plot constraints as lines and identify the feasible region
  • Evaluate the objective function at the vertices of the feasible region to find the optimal solution
• Simplex method for problems with more than two variables
  • Convert the problem to standard form by adding slack or surplus variables
  • Create an initial basic feasible solution
  • Iteratively improve the solution by selecting entering and leaving variables
  • Terminate when no further improvements can be made
• Interior point methods, such as the ellipsoid method and Karmarkar's algorithm, solve LP problems in polynomial time
• Software tools (CPLEX, Gurobi) can efficiently solve large-scale LP problems

Duality Theory

• Every LP problem (primal) has a corresponding dual problem
• Primal and dual problems are related by the duality theorems:
  • Weak duality theorem: The objective function value of the dual at any feasible solution is always less than or equal to the objective function value of the primal at any feasible solution
  • Strong duality theorem: If the primal has an optimal solution, the dual also has an optimal solution, and their objective function values are equal
• Complementary slackness conditions link the optimal solutions of the primal and dual problems
• Dual variables (shadow prices) provide information about the sensitivity of the optimal solution to changes in the constraints
• Duality can be used to derive optimality conditions and sensitivity analysis results

Applications and Examples

• Resource allocation problems (allocating limited resources among competing activities to maximize profit or minimize cost)
• Production planning (determining production quantities to meet demand while minimizing costs)
• Transportation problems (finding the most cost-effective way to transport goods from suppliers to customers)
• Diet problems (selecting foods to meet nutritional requirements while minimizing cost)
• Portfolio optimization (selecting investments to maximize return while satisfying risk constraints)
• Scheduling problems (assigning tasks to resources to minimize completion time or maximize efficiency)
• Network flow problems (maximizing flow or minimizing cost in a network subject to capacity constraints)

Advanced Techniques

• Integer programming (IP) extends LP by requiring some or all variables to take integer values
  • Branch-and-bound and cutting plane methods are used to solve IP problems
• Mixed-integer programming (MIP) allows both continuous and integer variables
• Nonlinear programming (NLP) deals with optimization problems with nonlinear objective functions and/or constraints
  • Karush-Kuhn-Tucker (KKT) conditions provide necessary conditions for optimality in NLP
• Stochastic programming incorporates uncertainty by considering random variables in the problem formulation
• Robust optimization seeks solutions that remain feasible and perform well under worst-case scenarios
• Decomposition methods (Dantzig-Wolfe, Benders) break large problems into smaller, more manageable subproblems

Common Pitfalls and Tips

• Ensure the linearity of the objective function and constraints before applying LP techniques
• Check for redundant or inconsistent constraints that may lead to infeasible or unbounded solutions
• Verify the non-negativity of decision variables, unless otherwise specified
• Scale the problem data to avoid numerical instability issues
• Interpret the results in the context of the original problem, considering any assumptions made during the modeling process
• Conduct sensitivity analysis to understand the robustness of the solution and identify critical parameters
• Consider using specialized software or solvers for large-scale or complex problems
• Be aware of the limitations of LP, such as the assumption of deterministic data and the inability to capture nonlinear relationships