History of Linear Programming

History of Linear Programming

• Dantzig published the Simplex Algorithm for linear programming in 1947
• Optimization techniques have been parallel to computer science, operations research, numerical analysis, game theory, economics, and control theory

Elements of the Optimization Problem

• An objective function is maximized or minimized
  • Examples include: expected return on a stock portfolio, a company’s production costs or profits, the time of arrival of a vehicle at a specified destination, or the vote share of a political candidate.
• Decision variables are quantities manipulated to optimize the objective function
  • Examples include: quantities of stock to be bought or sold, the amount of various resources to be allocated to different production activities, the route to be followed by a vehicle through a traffic network, or the policies advocated by a candidate.
• Constraints restrict the values that the variables can take
  • Examples include: a manufacturing process cannot require more resources than are available, nor can it employ less than zero resources.

Formulation of the Optimization Problem

• The most general formulation of an optimization problem can be expressed as:
  • Objective function
  • Equality constraints
  • Inequality constraints
  • Variable bounds

The Objective Function

• Objective functions tell us how to rate decisions.
• There is no fundamental difference between maximizing or minimizing problems.

The Objective Function (cont’d)

• In some cases, there is no objective function. This is called a feasibility problem.
• In some cases, there are multiple objective functions which may be reformulated into a single objective function

Decision Variables

• Decision variables represent planning and management actions.
  • Design: reactor volume, reservoir volume, reclaimed area for agriculture, etc.
  • Operations/ Management: released flow, diverted flow, crop rotation policy, etc.

Constraints

• Limitations on possible solutions to the problem.
  • Safety
  • Product quality
  • Equipment damage
  • Equipment operation
  • Legal/ethical considerations

Equality Constraints

• Examples include: material, energy, current, etc. balances -{accumulation} = {rate in} – {rate out} + {generated rate}
• Constitutive relations
• Equilibrium relations
• Imposed by the decision maker

Inequality Constraints

• Examples include:
  • Max investment available
  • Max flow rate due to pump limit
  • Max flow

Variable Bounds

• Variable bounds specify the domain of definition for decision variables.
• The most common variable bound constraint in environmental engineering is non-negativity.

Optimization Classes

• Linear programming: no variables are raised to higher powers.

Let’s practice: Problem Formulation

• Example of a company that has been contracted to provide copper and nickel and wants to minimize costs.

The Multi-Objective Problem

• Management of a regulated reservoir
  • Infinite alternatives
  • q objectives (different objectives that need to be minimized)

Pareto Efficiency (or Optimality)

• Definition of a solution that is NOT dominated by other solutions.
• The set of these solutions is known as the Pareto Frontier.
• A solution to a problem having multiple and conflicting objectives is EFFICENT/OPTIMAL/NON-INFERIOR if there exists no other feasible solution with better performance with respect to any objective, without worsening the performance of at least one other objective.

The Utopia Point

• The point in the objective space that minimizes (or maximizes) all the objectives.
• Often outside the feasible region

How to solve a MO problem

• Solving a multi-objective problem involves two phases:
  • Determining the Pareto frontier.
  • Choosing the best point of the Pareto frontier.

Weighting method

• Combines objectives into a single function
• By varying the weights, different points on the Pareto frontier can be generated.

Determining the Pareto Frontier

• There are a few different methods for determining the Pareto Frontier:
  • Lexicographic method
  • Weighting method
  • Constraint method
  • Reference point method

Constraint method

• The decision maker sets a threshold for the second objective.
• The Pareto point is found by minimizing the first objective, subject to the constraint that the second objective does not exceed the threshold.

How to choose the right method

• The appropriate method will depend on the specific problem and the preferences of the decision maker.