Overview of linear programming and examples of algorithms and implementations

Linear programming overview

Linear Programming (LP) is a mathematical method for solving the problem of optimising (maximising or minimising) a linear function, which is applied to many optimisation problems and will be widely used, especially in resource allocation, scheduling and transport planning.

A linear programming problem consists of three components

1. objective function: the goal that one wants to optimise (maximise or minimise). Usually, the objective function is expressed as a linear combination of several variables.
\[
\text{maximize/minimize } Z = c_1x_1 + c_2x_2 + \dots + c_nx_n
\] where \( c_i \) is the coefficient of each variable \( x_i \).

2. constraints: conditions that restrict the solution of the objective function. These are also expressed in linear form and specified as equality or inequality.
\[
a_{11}x_1 + a_{12}x_2 + \dots + a_{1n}x_n \leq b_1
\] \[
a_{21}x_1 + a_{22}x_2 + \dots + a_{2n}x_n \geq b_2
\] Etc.

3. non-negative constraints: usually all variables are assumed to be non-negative (greater than or equal to 0).
\[
x_i \geq 0 \quad (i = 1, 2, \dots, n)
\]

Typical methods for solving linear programming include.

• Simplex method: a method for searching for a vertex solution to a linear programming problem. It approaches the optimal solution by moving the vertices of the polyhedron defined by the constraints.
• Interior point method: a method that approaches the optimal solution by using points within the constraints. Often faster than the simplex method and suitable for large-scale problems.

The advantages of linear programming are its efficient computation, its ability to deal with large problems, and its ability to efficiently find a solution using the simplex or interior point method when an optimal solution always exists. A limitation is that not all problems can be expressed in linear form, and when there are non-linear conditions, linear programming alone cannot cope and non-linear programming and integer programming are required.

Application examples

Linear programming is an effective approach to the problem of optimal resource allocation under constraints. Examples of its application in various fields are discussed below.

1. transport problems

• Summary: To optimise how goods are allocated from a factory to several warehouses or from a warehouse to several retail outlets in order to minimise transport costs.
• Example: if a company has several warehouses across the country and the costs of delivery from each warehouse to retail outlets are different, linear programming can be used to plan transport so that delivery costs are minimised.

2. production planning

• Summary: optimises the combination of production quantities when manufacturing multiple products using limited resources (e.g. time, labour, raw materials).
• Example: suppose a factory produces different commodities A and B. If the production of commodity A and commodity B requires a certain amount of time and raw materials respectively, and each commodity generates different profits, linear programming can be used to determine the allocation of production quantities that maximises profits.

3. portfolio optimisation

• Summary: The problem of allocating assets to maximise returns while reducing risk in an investment portfolio.
• Example: if an investor is considering investing in several assets such as stocks, bonds and real estate, a portfolio that maximises returns can be constructed using linear programming, taking into account the return and risk of each asset, as well as the overall budget and risk tolerance.

4. the diet problem

• Summary: The problem of determining which and how much food should be consumed to minimise food costs while meeting specific nutritional values (calories, protein, vitamins, etc.).
• Example: if a person wants to reduce daily food costs while consuming a specific nutritional value, a meal plan that minimises costs can be derived using linear programming, taking into account the nutritional value and price of foods.

5. human resource scheduling

• Summary: The problem of optimising the work shifts of a company’s employees to meet the required working hours and workforce, while reducing costs.
• Example: if nurses are needed 24 hours a day in a hospital or similar, planning can be done to ensure that work assignments are optimised, taking into account the number of personnel per shift, working hours and leave requirements.

6. optimising energy supply

• Summary: The problem of optimising the availability and supply of power plants and renewable energy facilities to minimise costs and carbon emissions.
• Example: if several power plants have different costs and energy outputs, linear programming can be used to determine which and how to operate which plants according to demand, minimising overall costs and environmental impact.

7. marketing budget allocation

• Summary: The problem of allocating a limited marketing budget to different media (e.g. TV, web, SNS) to achieve maximum reach or sales.
• Example: if each medium has different advertising costs and reach rates, the budget can be allocated to maximise the impact on a specific target market. Linear programming is used to determine the optimum budget allocation for each medium to increase marketing effectiveness.

8. inventory management in manufacturing

• Summary: The problem of optimising the management of product inventories to meet demand while minimising inventory costs.
• Example: the optimum production and stock levels that minimise costs can be obtained by combining manufacturing scheduling and inventory management, taking into account product demand forecasts and storage space limitations.

9. blending problem

• Summary: problem of determining blending proportions to meet quality criteria while minimising costs when combining several raw materials to produce a product.
• Example: finding a combination of raw materials in the production of feed and foodstuffs that meets nutritional criteria while minimising costs by adjusting the blending ratio.

10. network flow (Network Flow Optimisation)

• Summary: the problem of optimising the amount of flow between points in a network to reduce costs or maximise flow.
• Examples: in logistics networks, this applies to optimising the paths that supply goods from warehouses to retail outlets, or to determining how data can flow efficiently in an internet communications network.

11. financial planning

• Summary: the problem of balancing investment and expenditure to maximise corporate value.
• Examples: forecasting cash flows, optimising the use of funds and developing financial strategies to maximise profits.

All of these examples address the problem of maximising profit and efficiency while reducing costs and risks using linear programming. Linear programming is used in many fields because it is very suitable for modelling problems mathematically and finding optimal solutions.

implementation example

As an example of a simple implementation of linear programming, we describe code in Python, which has a library called ‘SciPy’ for solving linear programming problems. Below is code for solving a typical linear programming problem using SciPy.

Problem: consider the following problem.

• Objective function: maximise Z=3x+2y.
• Constraints:
  x+y≤4
  x≤2
  y≤3x,y≥0

Example implementation using SciPy:

1. First, import the SciPy library.
2. Define the objective function and constraints using the linprog function.

from scipy.optimize import linprog

# objective function coefficient
# In SciPy, the maximisation problem is solved as a minimisation problem, so the coefficients are negative.
c = [-3, -2]  # maximize 3x + 2y converts to minimize -3x - 2y

# Coefficient matrix and right-hand side vector of constraints
A = [[1, 1],  # x + y <= 4
     [1, 0],  # x <= 2
     [0, 1]]  # y <= 3
b = [4, 2, 3]

# Range of variables (0 and above)
x_bounds = (0, None)
y_bounds = (0, None)

# Finding solutions to linear programming
result = linprog(c, A_ub=A, b_ub=b, bounds=[x_bounds, y_bounds], method="highs")

# Display of results
if result.success:
    print("optimal solution:")
    print("x =", result.x[0])
    print("y =", result.x[1])
    print("max value Z =", -result.fun)  # The objective function value was also set to a negative value, so it is reverted.
else:
    print("No optimal solution found.")

Code description:

1. Objective function definition:
   • SciPy’s linprog minimises by default, so the coefficients of the objective function are set to negative to solve as a ‘minimisation problem’.
2. Constraints:
   • Constraints are defined in A_ub and b_ub, where A_ub is the coefficient matrix and b_ub is the right-hand side value.
   • All constraint conditions need to be entered in the form of ‘small and equal’, so the above conditions are adapted to that form.
3. Variable range:
   • The range of each variable is specified by bounds. Here, x and y are specified as being greater than or equal to 0.
4. Result display:
   • If result.success is True, it indicates that an optimal solution has been found. The variable values of the optimal solution and the maximum value of the objective function are displayed.

Execution results: the following output is obtained when this programme is executed.

optimal solution:
x = 2.0
y = 2.0
greatest value Z = 10.0

In this example, when x=2 and y=2, the maximum value of the objective function Z=3x+2y is 10.

Challenges and countermeasures

Several challenges exist in the implementation and application of linear programming. Each of these challenges and measures to address them are described below.

1. when the objective function and constraints are not linear:
– Challenge: linear programming is an approach that can only be applied when the objective function and constraints are linear. However, real problems often involve non-linear relationships.
– Solution: consider methods for approximate linearisation of non-linear objective functions and constraints (linearisation techniques). For example, linear programming may be applied by approximating a non-linear function with a combination of several linear functions. It may also be useful to consider other techniques such as non-linear programming (NLP) and integer programming (MILP).

2. existence of integer constraints:
– Challenge: Many real-world problems require solutions to be integer values (e.g. number of products, number of people, etc.). However, standard linear programming deals only with continuous variables, so the solution cannot be an integer value.
– Solution: integer programming (IP) and mixed integer linear programming (MILP) can be used to impose integer constraints on variables. Libraries such as `PuLP` and `OR-Tools` in Python also support integer programming.

3. computational cost in complex problems:
– Challenge: As the number of constraints and variables increases, the computational complexity increases and it takes a lot of time to obtain a solution. In particular, the computational cost becomes very high for large-scale problems.
– Solution: the computational cost can be reduced by simplifying the problem or by using divide-and-conquer methods or heuristics (approximate solution methods). It is also possible to reduce the computational burden by analysing the data in advance and reducing unnecessary variables and constraints. A further approach is to utilise parallel processing and cloud computing to increase computational speed.

4. multi-objective optimisation problems:
– Challenge: In real-world problems, multiple objectives (e.g. minimising costs and maximising profits) need to be considered simultaneously, but ordinary linear programming methods can only handle a single objective function.
– Solution: an effective approach to multi-objective optimisation is to consider the weighted sum method or the Pareto optimum method. In the weighted sum method, each objective is weighted and combined into a single objective function, while in the Pareto optimum method, all objectives are considered simultaneously and a compromise solution (Pareto solution) is found. With `SciPy` and `Pyomo`, it is possible to tackle multi-objective optimisation problems.

5. accuracy and reliability of parameters:
– Challenge: In linear programming models, it is assumed that parameters such as cost and resources are given accurately, but in reality these parameters are often subject to uncertainty.
– Solution: In order to account for parameter uncertainty, robust optimisation and stochastic optimisation methods are introduced. In robust optimisation, a solution is found that does not degrade performance even if the parameters vary, while in stochastic optimisation, the solution is found by considering the probability distribution.

6. gap with actual operation:
– Challenge: The computationally optimal solution may not be suitable for actual operation. For example, it may take time to change the production line, or human factors may prevent it from being implemented as planned.
– Solution: adding constraints that take into account feasibility in the field or using simulation together can make the application in the field more realistic. It is also important to continuously improve the model by running a PDCA (Plan-Do-Check-Act) cycle, in which the model is revised through feedback after execution and reflected in the next plan.

reference book

Describes reference books on linear programming.

1. Fundamentals of Optimization: Methods, Minimum Principles, and Applications for Making Things Better

2. Computational Optimization: Success in Practice

3. Operations Research: An Introduction

4. Introduction to Linear Optimization

5.Introduction to Mathematical Optimization