1.1 Fundamentals of optimization and mathematical modeling

Optimization is about finding the best solution among alternatives. It involves defining decision variables, an objective function to maximize or minimize, and constraints that limit feasible solutions. These components work together to solve complex problems efficiently.

Formulating optimization problems requires clear problem definition, decision variable identification, and mathematical expression of objectives and constraints. Understanding local vs. global optima is crucial, as real-world problems often have multiple local optima but only one global optimum.

Fundamentals of Optimization

Components of optimization

• Optimization finds best solution from alternatives maximizing or minimizing objective subject to constraints (production planning)
• Decision variables represent quantities to determine (number of products to manufacture)
• Objective function mathematically expresses goal to optimize (maximize profit)
• Constraints limit feasible solutions (resource availability, demand requirements)
• Feasible region encompasses all solutions satisfying constraints (production capacity limits)

Formulation of optimization problems

• Identify problem and goal clearly define desired outcome (minimize transportation costs)
• Define decision variables assign symbols to unknown quantities (x1 = units shipped from warehouse 1)
• Formulate objective function express goal mathematically using variables (minimize total shipping cost)
• Determine constraints identify and express limitations mathematically (truck capacity, delivery time windows)
• Specify variable types and bounds continuous, integer, or binary with limits (non-negative integer quantities)

Elements of optimization problems

• Decision variables unknown quantities to determine represented by symbols (x, y, z)
• Objective function mathematical expression of goal to optimize maximize f(x) or minimize f(x)
• Constraints equations or inequalities limiting feasible solutions g(x) ≤ b or h(x) = c
• Variable bounds specify upper and lower limits on decision variables (0 ≤ x ≤ 100)

Local vs global optima

• Local optimum best solution within neighborhood no better solutions in immediate vicinity (hill climbing)
• Global optimum absolute best solution among all feasible solutions (Mount Everest)
• Multiple local optima possible but only one global optimum for given problem
• Convex problems local optimum equals global optimum (quadratic programming)
• Global optimization methods:
  1. Use global algorithms (genetic algorithms, simulated annealing)
  2. Multiple starting points in local search
  3. Branch and bound for certain problem types (mixed-integer programming)