Linear Programming

Linear programming focuses on solving optimization problems with a linear objective function subject to linear constraints.

Decision Variable

A quantity $x_j$ whose value is chosen by the solver to optimize the objective.

Values of these variables are determined by solving the LP.

Linear Objective Function

Expression that must be maximized or minimized. Linear in terms of the decision variables; no products or powers of $x_j$ terms.

Linear Constraint

A linear inequality or equality that restricts the values decision variables can take.

• Structural constraint
  Limits imposed by resources, demand, or policy.
• Non-negativity constraint
  $x_j \ge 0$ for every decision variable. Negative quantities are not physically meaningful.
• Bound constraint
  Fixes an upper or lower limit on a single variable.

Types by direction:

• Less than or equal to ($\le$)
  Caps usage, common for limited resources.
• Greater than or equal to ($\ge$)
  Enforces a minimum, common for demand or quality requirements.
• Equal to ($=$)
  Forces exact equality, common for balance conditions.

Linear Program

A linear program is an optimization problem with a linear objective function subject to linear constraints.

Subject to:

• $x_1, \dots, x_n$: decision variables
• $c_1, \dots, c_n$: objective coefficients
• $a_{ij}$: constraint coefficients
• $b_i$: constraint bounds

To solve a linear program:

• Identify decision variables
• Express the objective and constraints as linear functions
• Use a linear programming solver to find the optimal solution

Standard Model Types

A standard model type is a recurring pattern of variables, objective, and constraints for building a linear program.

• Product mix
  Maximize profit from $n$ products under limited resources.
• Blending
  Minimize cost of mixing $n$ ingredients into a product meeting quality specs.
  • Diet
    Special case of blending. Minimize food cost subject to minimum nutrient requirements.
• Transportation
  Minimize shipping cost of one commodity from $m$ supply points to $n$ fixed demand points.
  • Assignment
    Special case of transportation with unit supply and demand. Minimize cost of assigning $n$ agents to $n$ tasks, one-to-one.
• Transshipment
  Minimize shipping cost when goods pass through intermediate nodes instead of direct supply-to-demand routes.

Choosing Between Models

LP requires linear relationships, a single objective, no time-staging, and no integrality restriction. Use instead:

• Nonlinear programming
  Relationships aren’t linear.
• Pure integer programming
  Every variable must be an integer.
• Mixed integer linear programming
  Only some variables must be integers.
• Goal programming
  Multiple competing objectives balanced against targets.
• Dynamic programming
  Sequential, stage-based decisions where one stage affects later ones.