AMPL is a high-level algebraic modeling language for mathematical programming. It enables expressing optimization models in a natural mathematical notation close to textbook formulations. AMPL separates model structure from data, allowing the same model to be used with different datasets. Key features: support for linear, nonlinear, integer programming; interfaces with multiple solvers (CPLEX, Gurobi, MINOS, SNOPT); scripting capabilities for scenario analysis; extensive built-in functions. Model structure includes: sets, parameters, variables, objective, constraints. AMPL facilitates rapid prototyping, model maintenance, and allows users to focus on formulation rather than implementation details. Widely used in academia and industry for operations research applications.

Approximation Algorithms provide feasible solutions with guaranteed worst-case performance bounds for NP-hard optimization problems. An α-approximation algorithm for minimization ensures: solution value ≤ α × optimal value. For maximization: solution ≥ (1/α) × optimal. Examples: (1) Christofides algorithm for metric TSP (1.5-approximation); (2) greedy set cover (ln-approximation); (3) vertex cover (2-approximation). Performance ratio analysis balances: solution quality, computational complexity, and practical effectiveness. Some problems admit polynomial-time approximation schemes (PTAS) - algorithms achieving (1+ε)-approximation for any ε > 0. Others are APX-hard, meaning constant-factor approximation is best possible (unless P=NP).

The Assignment Problem optimally assigns n tasks to n agents (one-to-one assignment) minimizing total cost. Formulated as: minimize Σᵢ Σⱼ cᵢⱼxᵢⱼ subject to: Σⱼ xᵢⱼ = 1 for all i (each agent assigned one task), Σᵢ xᵢⱼ = 1 for all j (each task assigned to one agent), xᵢⱼ ∈ {0,1}. Despite being an integer program, it can be solved efficiently in polynomial time using the Hungarian algorithm (O(n³)). Applications include: job assignment, vehicle routing, task scheduling, and resource allocation. Variants include: bottleneck assignment (minimize maximum cost), generalized assignment (agents can handle multiple tasks), and quadratic assignment (costs depend on assignment pairs).

Benders Decomposition solves mixed-integer programs by decomposing into master problem (integer variables) and subproblem (continuous variables). For each master solution, the subproblem checks feasibility and optimality, generating cuts added to the master problem. Types of cuts: (1) Optimality cuts - improve objective function bounds; (2) Feasibility cuts - eliminate infeasible master solutions. The algorithm iterates until convergence. Benders is particularly effective for problems with complicating integer variables - when fixing integers, the remaining problem is easy to solve. Modern accelerations include: multi-cut strategies, cut strengthening, and combinatorial Benders. Applications: facility location, network design, production planning, and two-stage stochastic programming (L-shaped method).

Binary Programming is a special case of integer programming where decision variables are restricted to binary values: 0 or 1. These variables represent yes/no decisions such as: select a project or not, open a facility or not, assign a task or not. Binary variables are used in: knapsack problems, set covering, facility location, scheduling, and network design. Formulation often involves logical constraints using binary variables to model conditional relationships, implications, and disjunctions.

Branch and Bound is a systematic enumeration method for solving integer and combinatorial optimization problems. The algorithm works by: (1) Branching - partitioning the solution space into smaller subproblems by fixing variables; (2) Bounding - computing upper and lower bounds on the optimal solution for each subproblem using LP relaxations; (3) Pruning - eliminating subproblems that cannot contain better solutions than the current best. The process continues until all subproblems are either solved or pruned. Efficiency depends on branching strategy, bounding quality, and node selection rules.

Branch-and-Cut combines branch-and-bound with cutting plane methods for solving integer programs. At each node of the branch-and-bound tree: (1) solve LP relaxation; (2) if fractional, generate and add cuts to strengthen bounds; (3) if still fractional, branch on fractional variable; (4) prune nodes using bounds and cuts. This synergy is more powerful than either method alone - cuts improve bounds throughout the tree, reducing enumeration. Modern implementations include: cut pools, cut selection strategies, branching rules, and preprocessing techniques. Branch-and-cut is the core technology in commercial solvers (CPLEX, Gurobi, SCIP) and has enabled solving previously intractable large-scale integer programs in routing, scheduling, and logistics.

Column Generation is a technique for solving large-scale linear programs with many variables (columns) by generating only promising variables as needed. Based on Dantzig-Wolfe decomposition, it alternates between: (1) Restricted Master Problem (RMP) - LP with current subset of columns; (2) Pricing Problem - identifies new columns with negative reduced cost to add to RMP. The process continues until no improving columns exist (optimality). Often combined with branch-and-bound (branch-and-price) for integer programs. Applications: crew scheduling, vehicle routing with many routes, cutting stock problems, and airline scheduling. Effectiveness depends on efficiently solving the pricing problem, which often has special structure (shortest path, knapsack).

The Cutting Stock Problem minimizes waste when cutting raw materials (rolls, sheets) into smaller pieces. Classical formulation has exponential columns (cutting patterns). Column generation approach: (1) Master Problem - selects patterns minimizing total rolls used; (2) Pricing Subproblem - finds new pattern (knapsack problem) with negative reduced cost. The algorithm generates only needed patterns iteratively. Gilmore-Gomory method applies this framework to solve large-scale instances. Extensions handle: multiple stock sizes, two-dimensional cutting, and trim loss minimization. Applications: paper industry, steel manufacturing, glass cutting, and textile production. This problem pioneered column generation methodology, demonstrating effectiveness for problems with many variables.

The Conjugate Gradient method is an efficient algorithm for solving linear systems Ax = b where A is symmetric positive definite, and for unconstrained optimization of quadratic functions. Instead of steepest descent directions, it uses conjugate directions that ensure each iteration makes progress independent of previous iterations. For n-dimensional problems, it theoretically converges in at most n iterations (without roundoff errors). In practice, it's used iteratively for large sparse systems. Nonlinear conjugate gradient extends this to general smooth functions, commonly used in large-scale optimization and machine learning.