Overview of mixed integer optimization and its algorithm and implementation in python

Mixed-Integer Optimization

Libraries and platforms used for mixed integer optimization problems

Various libraries and platforms exist for solving mixed integer optimization problems. These tools can be commercial or open source, and it is important to select the right one depending on the size of the problem and requirements. Below we describe some of the most commonly used mixed integer optimization libraries and platforms.

• IBM CPLEX: A commercial optimization solver from IBM that can solve mixed integer optimization problems quickly and efficiently, and works with major programming languages such as Python and Java.
• Gurobi: A commercial optimization solver with advanced optimization algorithms, available in languages such as Python, C++, Java, .
• SCIP: An open-source optimization solver with performance comparable to commercial solvers, developed in C++ and made available to other languages via an API.
• COIN-OR: An open-source optimization solver project, several solvers are provided as part of COIN-OR. An example is CBC (COIN-OR Branch and Cut).
• PuLP: An open-source Python library that works with commercial solvers such as CPLEX and Gurobi to solve mixed integer optimization problems. It is characterized by its ability to define problems with simple syntax.
• Pyomo: An open-source Python modeling language that integrates with CPLEX, Gurobi, and other solvers to solve optimization problems.
• AMPL: A commercial optimization software and widely used advanced modeling language, AMPL can be integrated with CPLEX, Gurobi, and other solvers.

In addition to these, there are various other mixed integer optimization solvers such as Xpress, GLPK, etc. Each solver has different characteristics depending on the size of the problem, constraints, and nature of the objective function.

These libraries and platforms support the definition of mathematical models, analysis of problems, and execution of optimization algorithms to help solve mixed integer optimization problems. Commercial solvers offer advanced algorithms and performance, but there are also many open-source solvers and libraries that are an option when flexibility and customization are important.

On the application of mixed integer optimization problems

Mixed integer optimization problems have been applied to a variety of problems in various industries and business domains. Typical applications are described below.

• Manufacturing Scheduling: In the manufacturing industry, production planning and scheduling of manufacturing processes are important. Mixed integer optimization problems are used to determine the optimal schedule for production lines to meet machine utilization and product delivery dates. Specific objectives include maximizing production volume, minimizing manufacturing costs, or minimizing delivery delays, while constraints include manufacturing line capacity, resource constraints, and delivery date requirements.
• Logistics optimization: In optimizing transportation routes and plans, mixed integer optimization problems are applied to optimize vehicle routes, appropriate means of transportation, and warehouse locations. Specific objectives include minimizing total transportation costs, minimizing transportation time, minimizing arrival delays to customers, etc. Constraints include transportation capacity limits, warehouse capacity, time windows (range of arrival times to customers), constrained resources, etc.
• Power System Planning: Optimizing power supply is important for renewable energy deployment, grid optimization, and power demand management. Mixed integer optimization problems are used to improve the efficiency of power supply. Specific objectives include minimizing power supply costs, maximizing renewable energy deployment, and minimizing transmission losses, while constraints include upper and lower power supply limits, grid capacity constraints, power demand constraints, and renewable energy constraints.
• Inventory Optimization: In retail and manufacturing, mixed integer optimization problems are applied to optimize inventory levels to reduce inventory costs and simultaneously meet customer demand quickly. Specific objectives include minimizing inventory costs, minimizing inventory shortages, and minimizing inventory disposal. Constraints include maximum inventory capacity, minimum inventory requirements, product supply and demand balance, storage costs, and order delivery time.
• Project Scheduling: In project management, mixed integer optimization problems are used to optimize resource allocation, task scheduling, and project duration reduction. Specific objectives include minimizing project duration, minimizing resource usage, minimizing delays, etc. Constraints include pre- and post-task relationships (dependencies), resource constraints, and work time constraints.
• Network Design: Mixed integer optimization is used for problems that optimize the choice of connections and routes between different locations, such as the design of communication networks and optimization of transportation networks. Specific objectives include maximizing bandwidth in communication networks, minimizing transportation costs in transportation networks, and maximizing network reliability, while constraints include link capacity constraints, communication node placement constraints, and transportation route constraints.
• Portfolio Optimization: The portfolio optimization problem is the problem of determining the allocation of assets to be invested by an investor. There are various constraints on the allocation of assets, and mixed integer optimization is used to find the optimal portfolio that takes these constraints into account. Specific objectives include minimizing portfolio risk (variance and standard deviation) and maximizing expected returns. Constraints include ensuring that the total amount invested does not exceed an upper limit, that the proportion of assets falls within a certain range, and that excessive bias toward certain industries or regions is avoided.

Example implementation of mixed integer optimization using Python

As an example of a mixed integer optimization implementation using Python, we describe an example using PuLP.

PuLP is an open source solver that can solve mixed integer optimization problems written in Python.

The following is an example of a mixed integer optimization problem using PuLP. To use PuLP, it is necessary to install PuLP beforehand by pip install pulp, etc.

from pulp import *

# Define the maximization problem
problem = LpProblem('example', LpMaximize)

# Define Variables
x = LpVariable('x', lowBound=0, cat='Integer')
y = LpVariable('y', lowBound=0, cat='Integer')

# Define the objective function
problem += 5*x + 3*y

# Define constraints
problem += x + y <= 10
problem += x <= 4

# Solving Mixed Integer Optimization Problems
status = problem.solve()

# Output results
print(f'status: {LpStatus[status]}')
print(f'x: {value(x)}, y: {value(y)}, obj: {value(problem.objective)}')

The code defines a maximization problem using PuLP, defining variables x, y, objective function, and constraints. Finally, the mixed integer optimization problem is solved by calling the solve() function of PuLP. The solution to this problem is x=4, y=6, and the value of the objective function = 32.

Example python implementation of scheduling optimization via a mixed integer optimization problem

This section describes an example implementation in Python of optimization of manufacturing scheduling by a mixed integer optimization problem. Here, we take the job store scheduling problem as a sample. The job store scheduling problem is a general manufacturing scheduling problem in which multiple jobs are processed by multiple machines and the problem is to find the optimal schedule to complete all jobs.

The following is a simple implementation of solving the job store scheduling problem using PuLP.

import pulp

# Number of jobs and machines
num_jobs = 3
num_machines = 3

# Job processing time
processing_times = [
    [2, 3, 2],  # Job 1 processing time
    [1, 2, 1],  # Job 2 processing time
    [4, 2, 3]   # Job 3 processing time
]

# PuLP Problem Definition
prob = pulp.LpProblem("Job_Shop_Scheduling", pulp.LpMinimize)

# Variable Definition
# Variable x[i][j][k] is a binary variable that is 1 when job i is processed kth on machine j
x = [[[pulp.LpVariable(f"x_{i}_{j}_{k}", cat=pulp.LpBinary) for k in range(num_machines)] for j in range(num_machines)] for i in range(num_jobs)]

# objective function
prob += pulp.lpSum(x[i][j][k] * (k + processing_times[i][j]) for i in range(num_jobs) for j in range(num_machines) for k in range(num_machines))

# constraint
# Constrain each job not to run simultaneously on different machines
for i in range(num_jobs):
    for j in range(num_machines):
        prob += pulp.lpSum(x[i][j][k] for k in range(num_machines)) == 1

# Constrain each machine not to run more than one job at a time
for j in range(num_machines):
    for k in range(num_machines):
        prob += pulp.lpSum(x[i][j][k] for i in range(num_jobs)) <= 1

# Constrain each job to be executed on the next machine after it has been processed on the previous machine
for i in range(num_jobs):
    for j in range(num_machines - 1):
        prob += pulp.lpSum((k + processing_times[i][j]) * x[i][j][k] for k in range(num_machines)) <= pulp.lpSum(k * x[i][j+1][k] for k in range(num_machines))

# seeking a solution
prob.solve()

# Result display
print("Optimal Schedule:")
for i in range(num_jobs):
    for j in range(num_machines):
        for k in range(num_machines):
            if x[i][j][k].varValue == 1:
                print(f"Job{i+1} machine{j+1}{processing_times[i][j]}From time to{processing_times[i][j]+k}Process over time.")

In this example, a sample job store scheduling problem is optimized using PuLP.

Example implementation in python of logistics optimization using a mixed integer optimization problem

A simple example of a Python implementation of logistics optimization using a mixed integer optimization problem is shown. In logistics optimization, transportation routes and delivery schedules are optimized to minimize costs and improve efficiency. The following example shows how a simple transportation problem can be solved using PuLP.

import pulp

# Data on transportation routes and costs
# Transportation routes are shown in dictionary form (factory, warehouse)
routes = {
    ('Factory1', 'Warehouse1'): 10,
    ('Factory1', 'Warehouse2'): 20,
    ('Factory2', 'Warehouse1'): 15,
    ('Factory2', 'Warehouse2'): 25,
}

# PuLP Problem Definition
prob = pulp.LpProblem("Transportation_Problem", pulp.LpMinimize)

# Variable Definition
# Variable x[i][j] represents the amount of transportation when using transportation route (i, j)
x = {(i, j): pulp.LpVariable(f"x_{i}_{j}", lowBound=0, cat=pulp.LpInteger) for i, j in routes}

# objective function
prob += pulp.lpSum(routes[i, j] * x[i, j] for i, j in routes)

# constraint
# Constraints on the quantity supplied from the factory equal to the demand
demand = {
    'Warehouse1': 15,
    'Warehouse2': 20,
}
for j in demand:
    prob += pulp.lpSum(x[i, j] for i, _ in routes if j == _[1]) == demand[j]

# Constraints on the amount of transportation to the warehouse equal to the supply
supply = {
    'Factory1': 25,
    'Factory2': 30,
}
for i in supply:
    prob += pulp.lpSum(x[i, j] for _, j in routes if i == _[0]) == supply[i]

# seeking a solution
prob.solve()

# View Results
print("Optimal transportation planning:")
for i, j in routes:
    print(f"Using the transport routes ({i}, {j}) {x[i, j].varValue} Unit transportation.")

In this example, a simple transportation problem is optimized using PuLP. To apply it to a real task, it is necessary to define the constraints and objective function appropriately for the logistics optimization problem. Logistics optimization is often a complex problem, and it is assumed that more constraints and variables will be included when applied to realistic problems. In such cases, more detailed modeling is required, but the problem can be solved efficiently by utilizing PuLP and other optimization libraries.

Example implementation in python of power system programming optimization by mixed integer optimization problem

Power system planning optimization is a very complex problem, with many constraints and variables in a real power system. The example below shows one with three power plants (thermal, wind, and solar), each of which optimizes its output to minimize cost when meeting demand.

import pulp

# demand
demand = 100

# Information on power plants (generation costs and maximum output)
plants = {
    'Thermal': {'cost': 50, 'max_output': 80},
    'Wind': {'cost': 20, 'max_output': 60},
    'Solar': {'cost': 30, 'max_output': 40},
}

# Problem Definition for PuLP
prob = pulp.LpProblem("Power_System_Optimization", pulp.LpMinimize)

# Variable Definition
# Variable x[plant] is a variable representing the output of the power plant
x = {plant: pulp.LpVariable(f"x_{plant}", lowBound=0, upBound=plants[plant]['max_output'], cat=pulp.LpContinuous) for plant in plants}

# objective function
prob += pulp.lpSum(plants[plant]['cost'] * x[plant] for plant in plants)

# constraint
# Constraints on meeting demand
prob += pulp.lpSum(x[plant] for plant in plants) >= demand

# seeking a solution
prob.solve()

# View Results
print("Optimal power plant output:")
for plant in plants:
    print(f"{plant}: {x[plant].varValue} MW")

In this example, the output of three power plants (thermal, wind, and solar) is optimized to find the minimum cost of meeting the power demand. In actual power system planning optimization, many more constraints (e.g., instantaneous power balance, transmission capacity constraints, environmental constraints, etc.) are required. Commercial optimization solvers are also available for complex power system planning optimization, and commercial solvers may have more advanced algorithms and faster computational capabilities to handle larger and more complex problems.

Example implementation in python of inventory optimization via a mixed integer optimization problem

Inventory optimization is the problem of optimizing inventory levels and will seek to balance supply and demand. Proper management of inventory is expected to reduce costs and improve service levels. Here, as a simple example of inventory optimization, a single period inventory optimization of one product is implemented using PuLP.

import pulp

# Demand and initial inventory
demand = 30
initial_inventory = 10

# Product manufacturing and inventory holding costs
production_cost = 5
holding_cost = 2

# Problem Definition for PuLP
prob = pulp.LpProblem("Inventory_Optimization", pulp.LpMinimize)

# Variable Definition
# Variable x is a variable representing the amount of production and inventory
x = pulp.LpVariable("x", lowBound=0, cat=pulp.LpInteger)
inventory = pulp.LpVariable("inventory", lowBound=0, cat=pulp.LpContinuous)

# objective function
prob += production_cost * x + holding_cost * inventory

# constraint
# Constraints on meeting demand
prob += inventory + x == demand + initial_inventory

# seeking a solution
prob.solve()

# View Results
print("Optimal production volume:", x.varValue)
print("Optimal inventory levels:", inventory.varValue)

In this example, a simple inventory optimization problem is solved using PuLP, but in actual inventory optimization problems, more products, periods, and multiple constraints may be considered, and it is common to incorporate factors such as demand forecasts and inventory constraints.

Example implementation in python of network design optimization via mixed integer optimization problem

As an example of network design optimization with mixed integer optimization problems, we implement a network design problem involving integer variables using PuLP. Here we consider the problem of selecting links on a given network and connecting all nodes at minimum cost.

import pulp

# Network information (node and link costs)
nodes = ['A', 'B', 'C', 'D', 'E']
links = [('A', 'B', 10), ('A', 'C', 5), ('B', 'C', 2), ('B', 'D', 4), ('C', 'D', 8), ('C', 'E', 3), ('D', 'E', 6)]

# Problem Definition for PuLP
prob = pulp.LpProblem("Network_Design_Optimization", pulp.LpMinimize)

# Variable Definition
# Variable x[e] is a binary variable indicating whether to use link e
x = {e: pulp.LpVariable(f"x_{e[0]}_{e[1]}", cat=pulp.LpBinary) for e in links}

# objective function
prob += pulp.lpSum(e[2] * x[e] for e in links)

# constraint
# Constraints to which all nodes are connected
for node in nodes:
    prob += pulp.lpSum(x[e] for e in links if node in e) >= 1

# seeking a solution
prob.solve()

# View Results
print("Optimal Link:")
for e in links:
    if x[e].varValue == 1:
        print(f"{e[0]} -> {e[1]}")

In this example, the problem of selecting links on a given network to connect all nodes at minimum cost is solved using PuLP. Actual network design problems may involve many more constraints and variables.

Example implementation in python of portfolio optimization by mixed integer optimization problem

Portfolio optimization refers to the problem of minimizing risk or maximizing return by investing an appropriate proportion of a given set of assets. Here, as a simple portfolio optimization example, we will implement a portfolio consisting of two assets using PuLP.

import pulp

# Information on assets (rate of return and risk)
assets = {
    'Asset1': {'return': 0.05, 'risk': 0.1},
    'Asset2': {'return': 0.08, 'risk': 0.15},
}

# Problem Definition for PuLP
prob = pulp.LpProblem("Portfolio_Optimization", pulp.LpMaximize)

# Variable Definition
# Variable x[asset] is a variable that represents the percentage of assets
x = {asset: pulp.LpVariable(f"x_{asset}", lowBound=0, upBound=1, cat=pulp.LpContinuous) for asset in assets}

# objective function
expected_return = pulp.lpSum(assets[asset]['return'] * x[asset] for asset in assets)
prob += expected_return

# constraint
# Constraint that the sum of the percentages of the portfolio is 1 (invest 100%)
prob += pulp.lpSum(x[asset] for asset in assets) == 1

# Risk constraints (comment this out if minimizing risk)
target_risk = 0.12
portfolio_risk = pulp.lpSum(assets[asset]['risk'] * x[asset] for asset in assets)
prob += portfolio_risk <= target_risk

# seeking a solution
prob.solve()

# View Results
print("Optimal Portfolio Percentage:")
for asset in assets:
    print(f"{asset}: {x[asset].varValue:.2f}")

print("expected return:", pulp.value(prob.objective))
print("Portfolio Risk:", pulp.value(portfolio_risk))

In this example, a portfolio consisting of two assets is optimized using PuLP. In actual portfolio optimization, more assets, constraints, and risk responses may be considered, and factors such as risk responses can be added to create an optimization model suitable for actual portfolio management.

Reference Information and Reference Books

For more information on mathematical optimization, see “Automata and State Transitions/Petri Nets and Automated Programming” and “Theory, Mathematics, and Algorithms for Artificial Intelligence Technology. Please refer to those as well.

Reference book is “Introduction to Mathematical optimozation“

“Mathematical Optimization Techniques“

“Mathematical Optimization for Efficient and Robust Energy Networks“

“Mathematical Optimization Terminology: A Comprehensive Glossary of Terms “