Linear Programming (LP)

The objective function is a linear equation that defines the quantity to be optimized, either maximized (e.g., profit, revenue) or minimized (e.g., cost, time). It is expressed as a weighted sum of the decision variables.

• Standard Form: Z = c₁x₁ + c₂x₂ + ... + cₙxₙ, where Z is the objective value, cᵢ are cost/profit coefficients, and xᵢ are decision variables.
• Example: In a production problem, Z = 50x₁ + 30x₂ could represent total profit, where x₁ and x₂ are units of two products, and 50 and 30 are their respective profit margins per unit.

Decision variables are the unknown quantities the model solves for. They represent the controllable inputs or choices (e.g., 'how much to produce,' 'how many to ship'). In standard LP, these variables are continuous and non-negative.

• Notation: Typically denoted as x₁, x₂, ..., xₙ.
• Domain: xᵢ ≥ 0 for all i. This non-negativity constraint is a fundamental LP assumption, reflecting that quantities like production volume cannot be negative.
• Role: The solution to an LP model is the specific set of values for these variables that optimizes the objective while satisfying all constraints.

Linear constraints are a system of linear inequalities or equations that define the feasible region—the set of all possible solutions that satisfy the problem's limitations. Each constraint consumes resources (like raw materials, time, or budget).

• Standard Forms: a₁₁x₁ + a₁₂x₂ + ... + a₁ₙxₙ ≤ b₁ (resource limitation), ≥ (minimum requirement), or = (exact balance).
• Coefficients (aᵢⱼ): Represent the consumption rate of resource i by activity j.
• Right-Hand Side (bᵢ): Represents the total available amount of resource i.
• Example: A constraint 2x₁ + 4x₂ ≤ 100 could model a machine time limit, where products x₁ and x₂ consume 2 and 4 hours per unit, respectively, with 100 total hours available.

The feasible region is the geometric set of all points (combinations of decision variable values) that simultaneously satisfy every linear constraint and the non-negativity conditions. It is a convex polytope—a multi-dimensional polygon.

• Convexity: A key property where any line segment connecting two points within the region lies entirely within the region. This guarantees that a local optimum is also a global optimum.
• Vertices (Extreme Points): The feasible region's corners. A fundamental theorem of LP states that if an optimal solution exists, at least one vertex of the polytope is an optimal solution. This is why algorithms like the Simplex method move from vertex to vertex.

LP problems are converted into standard or canonical forms for algorithmic processing. These forms impose a consistent structure for solvers.

• Standard Form (for Simplex):
  • Objective: Maximize cᵀx.
  • Constraints: Equality constraints, Ax = b.
  • Variables: x ≥ 0.
  • Any LP can be converted to this form using slack/surplus variables.
• Canonical Form:
  • Objective: Maximize cᵀx.
  • Constraints: Inequality constraints, Ax ≤ b.
  • Variables: x ≥ 0.
• Conversion: Minimization problems are converted to maximization by negating the objective. ≥ constraints are multiplied by -1 to become ≤.

Slack and surplus variables are non-negative auxiliary variables added to transform inequality constraints into equalities, which is required for the tableau-based Simplex algorithm.

• Slack Variable (s): Added to a ≤ constraint to represent unused resource capacity.
  • 2x₁ + 4x₂ ≤ 100 becomes 2x₁ + 4x₂ + s = 100, with s ≥ 0.
• Surplus Variable (e): Subtracted from a ≥ constraint to represent excess over a minimum requirement.
  • x₁ + x₂ ≥ 20 becomes x₁ + x₂ - e = 20, with e ≥ 0.
• Role in Solution: In an optimal solution, a slack variable's value directly indicates how much of a resource is left unused. A zero value means the constraint is binding.

LP is the engine behind modern logistics, solving core problems like the Transportation Problem (minimizing shipping costs from multiple suppliers to multiple consumers) and the Blending Problem (optimizing raw material mixes). It determines:

• Optimal production schedules across factories
• Most efficient distribution routes and warehouse locations
• Inventory levels to balance holding costs with service levels

For example, a global manufacturer uses LP to decide how much product to make at each plant and ship to each regional hub to meet demand at the lowest total cost of production and freight.

In finance, LP is used for asset allocation and portfolio selection. The classic Markowitz mean-variance model can be formulated as a quadratic program, but LP solves related problems like:

• Maximizing expected return for a given level of risk (modeled as a constraint)
• Minimizing transaction costs when rebalancing a portfolio
• Managing cash flow and liquidity under regulatory constraints

Fund managers use these models to construct portfolios that optimally balance risk and reward according to an investor's specific tolerance.

Creating efficient schedules for employees is a massive constraint-satisfaction challenge. LP optimizes:

• Shift assignments for nurses, call center agents, or retail staff
• Crew scheduling for airlines and public transportation
• Matching employee skills, availability, and labor regulations (e.g., break requirements) to forecasted demand

The objective is typically to minimize labor costs while ensuring all shifts are covered and contractual rules are met. A hospital might use LP to schedule nurses across departments while respecting union rules on consecutive working days.

Power companies rely on LP for economic dispatch—deciding which power generators (coal, gas, nuclear, hydro) to turn on and at what output level to meet electricity demand at the lowest possible cost. Key constraints include:

• Generator minimum and maximum output capacities
• Transmission line limits
• Fuel availability and costs
• Environmental regulations on emissions

This application is critical for integrating variable renewable sources like wind and solar, as LP models can adjust conventional generation in real-time to compensate for fluctuations.

LP determines the optimal product mix for a factory given limited resources. This is the classic product-mix problem. A manufacturer must decide:

• How many units of each product to produce
• Subject to constraints on machine hours, labor availability, and raw materials
• To maximize total profit or contribution margin

For instance, an automotive plant uses LP to allocate limited assembly line time and parts inventory between different car models (sedans, SUVs) to maximize profitability, considering the different margins and resource needs of each model.

LP efficiently models the flow of commodities through networks. Key applications include:

• Maximum Flow Problem: Finding the greatest possible flow (data, water, traffic) from a source to a sink in a capacitated network.
• Minimum Cost Flow Problem: Shipping a required amount of flow at the lowest total cost.
• Shortest Path Problem: Finding the cheapest or fastest route, solvable as a special case of min-cost flow.

Telecom providers use these models for network design and routing, determining how to route data packets through their infrastructure to minimize latency and congestion while using capacity efficiently.

A Constraint Optimization Problem (COP) extends a standard Constraint Satisfaction Problem by adding an objective function to be maximized or minimized. While a CSP seeks any feasible solution, a COP requires finding the best feasible solution according to a quantifiable metric (e.g., minimize cost, maximize profit).

• Key Difference from LP: LPs have linear constraints and a linear objective. COPs can have arbitrary, non-linear constraints and objectives.
• Solution Methods: Often solved using branch and bound search combined with constraint propagation, or by converting to an Integer Programming model.
• Example: Scheduling employees to cover shifts (constraint) while minimizing total payroll cost (objective).

Integer Programming (IP) is a mathematical optimization model where some or all decision variables are restricted to be integers. It is a powerful framework for modeling discrete, yes/no, or indivisible quantity decisions.

• Relation to LP: IP problems often start as LP relaxations (where integer constraints are ignored). The simplex algorithm solves the LP, and then techniques like branch and bound are used to enforce integrality.
• Mixed-Integer Programming (MIP): A common variant where only some variables must be integers.
• Applications: Facility location (open or closed), vehicle routing (integer number of trucks), project selection (binary choices).

The simplex algorithm is the most widely-used and historically dominant method for solving Linear Programming problems. It operates by moving iteratively from one vertex (corner point) of the feasible region to an adjacent vertex with a better objective value, until an optimum is found.

• Mechanism: Uses linear algebra to pivot between solutions defined by a basis of variables.
• Efficiency: In practice, it often solves problems with a number of steps polynomial in the problem size, despite having exponential worst-case complexity.
• Foundation: Forms the computational core of commercial solvers like IBM ILOG CPLEX and Gurobi Optimizer for LP problems.

Branch and bound is a general, tree-search algorithm paradigm for finding optimal solutions to discrete optimization problems, including Integer Programming and Constraint Optimization Problems.

• Process:
  • Branching: Recursively splits the problem into smaller subproblems (e.g., variable x=0 vs. x=1).
  • Bounding: For each subproblem, solves a relaxed version (e.g., its LP relaxation) to get a bound on the best possible solution within that branch.
  • Pruning: Discards (prunes) branches whose bound is worse than the best-known feasible solution.
• Role in IP: It is the primary method for solving IPs, using the simplex algorithm to solve LP relaxations at each node.

The Vehicle Routing Problem (VRP) is a canonical combinatorial optimization and constraint satisfaction problem that often utilizes LP and IP techniques. The goal is to find optimal routes for a fleet of vehicles delivering to a set of customers.

• Core Constraints: Vehicle capacity, delivery time windows, driver working hours.
• Objective: Typically minimize total distance, time, or number of vehicles used.
• Modeling: Often formulated as a Mixed-Integer Program with binary variables indicating if a specific vehicle travels between two locations. Sophisticated branch and bound and cutting-plane methods are used for solutions.
• Scale: Real-world VRPs for large logistics companies can involve thousands of delivery points and hundreds of vehicles.