Introduction How to Approach Mathematical Optimization

Basic Elements of Mathematical Optimization Problems

What is Mathematical Optimization?

Mathematical optimization is a mathematical approach to finding the "best" result from a set of given options under specific constraints. Its purpose is to discover a solution (a set of values for decision variables) that maximizes or minimizes an evaluation metric called the objective function in various real-world problems such as business decisions, engineering design, and resource allocation.

For example, optimization of delivery routes in logistics, risk-return optimization in financial portfolios, production schedule optimization in manufacturing, and power generation planning optimization in the energy sector are just a few applications. Mathematical optimization is a powerful tool for finding the best strategy within limited resources across many fields.

To tackle mathematical optimization, you first need to understand its basic components.

Basic Elements of Mathematical Optimization

  • Decision Variables:
    Variables that represent the choices we can control or need to decide in the optimization process. Finding the values of these variables is the goal of optimization.
  • Objective Function:
    A mathematical expression using decision variables that represents the goal we want to achieve through optimization. This could be maximization (e.g., profit, value, efficiency) or minimization (e.g., cost, time, risk).
  • Constraints:
    Mathematical or logical expressions that represent conditions or limitations that the decision variables must satisfy. These conditions determine the range of possible values for the decision variables.

Accurately identifying and mathematically expressing these elements (formulation) is the first step in solving a mathematical optimization problem.

The following table shows examples of objective functions, constraints, and decision variables in real-world applications of mathematical optimization.

Application Objective Function Constraints Decision Variables
Delivery Route Optimization Minimize total travel distance or time
  • Deliver to all customers
  • Vehicle capacity limits
  • Adherence to delivery time windows
 Route for each vehicle (visit order)
Investment Portfolio Optimization Maximize expected return or minimize risk
  • Budget constraint (total investment)
  • Risk tolerance
  • Asset class allocation limits
 Investment proportion for each asset
Production Planning Optimization Maximize total profit or minimize production cost
  • Production capacity limits
  • Raw material inventory constraints
  • Need to meet demand
  • Minimum lot sizes
 Production quantity and timing for each product
Staff Scheduling Minimize labor costs or maximize employee satisfaction
  • Ensuring required staffing levels
  • Meeting skill requirements
  • Compliance with labor regulations
  • Considering employee preferences
 Shift assignments for each employee
Power Grid Optimization Minimize generation costs or CO2 emissions
  • Meeting electricity demand
  • Generator capacity limits
  • Transmission network constraints
  • Renewable energy ratio
 Output level for each power plant, power flow
Job Shop Scheduling Minimize makespan (time to complete all jobs)
  • Assign each job to one machine
  • Total processing time is the sum of job times
  • Makespan is the maximum processing time across all machines
 Binary variables indicating which job is assigned to which machine

Formulation Example: Knapsack Problem

To understand the basic concepts of mathematical optimization, let's look at the formulation process using the simple "Knapsack Problem" as an example.

Problem Setting

You have a knapsack with limited capacity (e.g., weight). In front of you are multiple items, each with different values and weights. You want to select items to maximize the total value while not exceeding the knapsack's capacity.

To get a concrete image, try the following demo. Click on each item.
As you select more items, the total value of items in the knapsack increases, but if you select too many, you'll exceed the knapsack's capacity.
Try to select items to maximize the total value without exceeding the knapsack's capacity.
What total value did you achieve?
Try the Demo

Knapsack Problem Demo

Instructions

Experience an interactive demo of the Knapsack Problem. Select items to maximize the total value of items in your knapsack.

Knapsack Problem Demo

Knapsack Capacity (Maximum Weight): 15 kg

Select items (click to select/deselect):

Item A

Weight: 4 kg

Value: 8

Item B

Weight: 6 kg

Value: 13

Item C

Weight: 5 kg

Value: 10

Item D

Weight: 7 kg

Value: 15

Item E

Weight: 3 kg

Value: 6

Current State:

Total Weight: 0 kg

Total Value: 0

Status:

The formulation of this problem involves the following steps:

Formulation

The Knapsack Problem can be formulated as follows:

  • Decision Variables: Decide whether to put each item $i$ in the knapsack. Since this is a binary choice (put in or don't put in), we use binary variables $x_i$.
    • $x_i = 1$ (if item $i$ is put in the knapsack)
    • $x_i = 0$ (if item $i$ is not put in the knapsack)
  • Objective Function: Maximize the total value of items in the knapsack.
    \[\max \sum_{i=1}^{n} v_i \cdot x_i\]

    where $v_i$ is the value of item $i$

  • Constraints: The total weight of items in the knapsack must not exceed the knapsack's capacity W.
    \[\sum_{i=1}^{n} w_i \cdot x_i \leq W\]

    where $w_i$ is the weight of item $i$ and $W$ is the capacity of the knapsack

    The problem is formulated as deciding the values of $x_i$ (which items to select) such that this constraint is satisfied.

Next: Approach to Mathematical Optimization