Minimal price move optimization minimizes the price of transferring move by means of a community of nodes and edges. Nodes embody sources (provide) and sinks (demand), with totally different prices and capability limits. The goal is to seek out the least expensive option to transfer quantity from sources to sinks whereas adhering to all capability limitations.
Purposes
Purposes of minimal price move optimization are huge and assorted, spanning a number of industries and sectors. This strategy is essential in logistics and provide chain administration, the place it’s used to reduce transportation prices whereas guaranteeing well timed supply of products. In telecommunications, it helps in optimizing the routing of information by means of networks to cut back latency and enhance bandwidth utilization. The power sector leverages minimal price move optimization to effectively distribute electrical energy by means of energy grids, lowering losses and operational prices. City planning and infrastructure growth additionally profit from this optimization approach, because it assists in designing environment friendly public transportation programs and water distribution networks.
Instance
Beneath is an easy move optimization instance:
The picture above illustrates a minimal price move optimization downside with six nodes and eight edges. Nodes A and B function sources, every with a provide of fifty models, whereas nodes E and F act as sinks, every with a requirement of 40 models. Each edge has a most capability of 25 models, with variable prices indicated within the picture. The target of the optimization is to allocate move on every edge to maneuver the required models from nodes A and B to nodes E and F, respecting the sting capacities on the lowest potential price.
Node F can solely obtain provide from node B. There are two paths: instantly or by means of node D. The direct path has a price of two, whereas the oblique path by way of D has a mixed price of three. Thus, 25 models (the utmost edge capability) are moved instantly from B to F. The remaining 15 models are routed by way of B -D-F to fulfill the demand.
Presently, 40 out of fifty models have been transferred from node B, leaving a remaining provide of 10 models that may be moved to node E. The out there pathways for supplying node E embody: A-E and B-E with a price of three, A-C-E with a price of 4, and B-C-E with a price of 5. Consequently, 25 models are transported from A-E (restricted by the sting capability) and 10 models from B-E (restricted by the remaining provide at node B). To fulfill the demand of 40 models at node E, a further 5 models are moved by way of A-C-E, leading to no move being allotted to the B-C pathway.
Mathematical formulation
I introduce two mathematical formulations of minimal price move optimization:
1. LP (linear program) with steady variables solely
2. MILP (combined integer linear program) with steady and discrete variables
I’m utilizing following definitions:
LP formulation
This formulation solely incorporates choice variables which might be steady, which means they’ll have any worth so long as all constraints are fulfilled. Determination variables are on this case the move variables x(u, v) of all edges.
The target operate describes how the prices which might be imagined to be minimized are calculated. On this case it’s outlined because the move multiplied with the variable price summed up over all edges:
Constraints are circumstances that have to be happy for the answer to be legitimate, guaranteeing that the move doesn’t exceed capability limitations.
First, all flows have to be non-negative and never exceed to edge capacities:
Circulation conservation constraints make sure that the identical quantity of move that goes right into a node has to come back out of the node. These constraints are utilized to all nodes which might be neither sources nor sinks:
For supply and sink nodes the distinction of out move and in move is smaller or equal the availability of the node:
If v is a supply the distinction of outflow minus influx should not exceed the availability s(v). In case v is a sink node we don’t permit that greater than -s(v) can move into the node than out of the node (for sinks s(v) is unfavourable).
MILP
Moreover, to the continual variables of the LP formulation, the MILP formulation additionally incorporates discreate variables that may solely have particular values. Discrete variables permit to limit the variety of used nodes or edges to sure values. It can be used to introduce fastened prices for utilizing nodes or edges. On this article I present easy methods to add fastened prices. You will need to be aware that including discrete choice variables makes it rather more tough to seek out an optimum resolution, therefore this formulation ought to solely be used if a LP formulation isn’t potential.
The target operate is outlined as:
With three phrases: variable price of all edges, fastened price of all edges, and stuck price of all nodes.
The utmost move that may be allotted to an edge is determined by the sting’s capability, the sting choice variable, and the origin node choice variable:
This equation ensures that move can solely be assigned to edges if the sting choice variable and the origin node choice variable are 1.
The move conservation constraints are equal to the LP downside.
Implementation
On this part I clarify easy methods to implement a MILP optimization in Python. You could find the code on this repo.
Libraries
To construct the move community, I used NetworkX which is a wonderful library (https://networkx.org/) for working with graphs. There are numerous fascinating articles that display how highly effective and straightforward to make use of NetworkX is to work with graphs, i.a. customizing NetworkX Graphs, NetworkX: Code Demo for Manipulating Subgraphs, Social Community Evaluation with NetworkX: A Light Introduction.
One essential facet when constructing an optimization is to make it possible for the enter is appropriately outlined. Even one small error could make the issue infeasible or can result in an surprising resolution. To keep away from this, I used Pydantic to validate the person enter and lift any points on the earliest potential stage. This article provides a straightforward to know introduction to Pydantic.
To remodel the outlined community right into a mathematical optimization downside I used PuLP. Which permits to outline all variables and constraint in an intuitive means. This library additionally has the benefit that it may use many alternative solvers in a easy pug-and-play vogue. This article gives good introduction to this library.
Defining nodes and edges
The code beneath exhibits how nodes are outlined:
from pydantic import BaseModel, model_validator
from typing import Elective
# node and edge definitions
class Node(BaseModel, frozen=True):
"""
class of community node with attributes:
title: str - title of node
demand: float - demand of node (if node is sink)
provide: float - provide of node (if node is supply)
capability: float - most move out of node
sort: str - sort of node
x: float - x-coordinate of node
y: float - y-coordinate of node
fixed_cost: float - price of choosing node
"""
title: str
demand: Elective[float] = 0.0
provide: Elective[float] = 0.0
capability: Elective[float] = float('inf')
sort: Elective[str] = None
x: Elective[float] = 0.0
y: Elective[float] = 0.0
fixed_cost: Elective[float] = 0.0
@model_validator(mode="after")
def validate(self):
"""
validate if node definition are right
"""
# examine that demand is non-negative
if self.demand < 0 or self.demand == float('inf'): increase ValueError('demand have to be non-negative and finite')
# examine that offer is non-negative
if self.provide < 0: increase ValueError('provide have to be non-negative')
# examine that capability is non-negative
if self.capability < 0: increase ValueError('capability have to be non-negative')
# examine that fixed_cost is non-negative
if self.fixed_cost < 0: increase ValueError('fixed_cost have to be non-negative')
return selfNodes are outlined by means of the Node class which is inherited from Pydantic’s BaseModel. This permits an automated validation that ensures that each one properties are outlined with the right datatype each time a brand new object is created. On this case solely the title is a required enter, all different properties are optionally available, if they don’t seem to be supplied the required default worth is assigned to them. By setting the “frozen” parameter to True I made all properties immutable, which means they can’t be modified after the item has been initialized.
The validate technique is executed after the item has been initialized and applies extra checks to make sure the supplied values are as anticipated. Particularly it checks that demand, provide, capability, variable price and stuck price will not be unfavourable. Moreover, it additionally doesn’t permit infinite demand as this could result in an infeasible optimization downside.
These checks look trivial, nevertheless their essential profit is that they are going to set off an error on the earliest potential stage when an enter is wrong. Thus, they stop making a optimization mannequin that’s incorrect. Exploring why a mannequin can’t be solved can be rather more time consuming as there are a lot of elements that will have to be analyzed, whereas such “trivial” enter error will not be the primary facet to analyze.
Edges are carried out as follows:
class Edge(BaseModel, frozen=True):
"""
class of edge between two nodes with attributes:
origin: 'Node' - origin node of edge
vacation spot: 'Node' - vacation spot node of edge
capability: float - most move by means of edge
variable_cost: float - price per unit move by means of edge
fixed_cost: float - price of choosing edge
"""
origin: Node
vacation spot: Node
capability: Elective[float] = float('inf')
variable_cost: Elective[float] = 0.0
fixed_cost: Elective[float] = 0.0@model_validator(mode="after")
def validate(self):
"""
validate of edge definition is right
"""
# examine that node names are totally different
if self.origin.title == self.vacation spot.title: increase ValueError('origin and vacation spot names have to be totally different')
# examine that capability is non-negative
if self.capability < 0: increase ValueError('capability have to be non-negative')
# examine that variable_cost is non-negative
if self.variable_cost < 0: increase ValueError('variable_cost have to be non-negative')
# examine that fixed_cost is non-negative
if self.fixed_cost < 0: increase ValueError('fixed_cost have to be non-negative')
return self
The required inputs are an origin node and a vacation spot node object. Moreover, capability, variable price and stuck price may be supplied. The default worth for capability is infinity which implies if no capability worth is supplied it’s assumed the sting doesn’t have a capability limitation. The validation ensures that the supplied values are non-negative and that origin node title and the vacation spot node title are totally different.
Initialization of flowgraph object
To outline the flowgraph and optimize the move I created a brand new class known as FlowGraph that’s inherited from NetworkX’s DiGraph class. By doing this I can add my very own strategies which might be particular to the move optimization and on the identical time use all strategies DiGraph gives:
from networkx import DiGraph
from pulp import LpProblem, LpVariable, LpMinimize, LpStatus
class FlowGraph(DiGraph):
"""
class to outline and clear up minimal price move issues
"""
def __init__(self, nodes=[], edges=[]):
"""
initialize FlowGraph object
:param nodes: listing of nodes
:param edges: listing of edges
"""
# initialialize digraph
tremendous().__init__(None)
# add nodes and edges
for node in nodes: self.add_node(node)
for edge in edges: self.add_edge(edge)
def add_node(self, node):
"""
add node to graph
:param node: Node object
"""
# examine if node is a Node object
if not isinstance(node, Node): increase ValueError('node have to be a Node object')
# add node to graph
tremendous().add_node(node.title, demand=node.demand, provide=node.provide, capability=node.capability, sort=node.sort,
fixed_cost=node.fixed_cost, x=node.x, y=node.y)
def add_edge(self, edge):
"""
add edge to graph
@param edge: Edge object
"""
# examine if edge is an Edge object
if not isinstance(edge, Edge): increase ValueError('edge have to be an Edge object')
# examine if nodes exist
if not edge.origin.title in tremendous().nodes: self.add_node(edge.origin)
if not edge.vacation spot.title in tremendous().nodes: self.add_node(edge.vacation spot)
# add edge to graph
tremendous().add_edge(edge.origin.title, edge.vacation spot.title, capability=edge.capability,
variable_cost=edge.variable_cost, fixed_cost=edge.fixed_cost)
FlowGraph is initialized by offering an inventory of nodes and edges. Step one is to initialize the father or mother class as an empty graph. Subsequent, nodes and edges are added by way of the strategies add_node and add_edge. These strategies first examine if the supplied aspect is a Node or Edge object. If this isn’t the case an error will probably be raised. This ensures that each one parts added to the graph have handed the validation of the earlier part. Subsequent, the values of those objects are added to the Digraph object. Be aware that the Digraph class additionally makes use of add_node and add_edge strategies to take action. Through the use of the identical technique title I’m overwriting these strategies to make sure that each time a brand new aspect is added to the graph it have to be added by means of the FlowGraph strategies which validate the item sort. Thus, it isn’t potential to construct a graph with any aspect that has not handed the validation exams.
Initializing the optimization downside
The strategy beneath converts the community into an optimization mannequin, solves it, and retrieves the optimized values.
def min_cost_flow(self, verbose=True):
"""
run minimal price move optimization
@param verbose: bool - print optimization standing (default: True)
@return: standing of optimization
"""
self.verbose = verbose
# get most move
self.max_flow = sum(node['demand'] for _, node in tremendous().nodes.knowledge() if node['demand'] > 0)
start_time = time.time()
# create LP downside
self.prob = LpProblem("FlowGraph.min_cost_flow", LpMinimize)
# assign choice variables
self._assign_decision_variables()
# assign goal operate
self._assign_objective_function()
# assign constraints
self._assign_constraints()
if self.verbose: print(f"Mannequin creation time: {time.time() - start_time:.2f} s")
start_time = time.time()
# clear up LP downside
self.prob.clear up()
solve_time = time.time() - start_time
# get standing
standing = LpStatus[self.prob.status]
if verbose:
# print optimization standing
if standing == 'Optimum':
# get goal worth
goal = self.prob.goal.worth()
print(f"Optimum resolution discovered: {goal:.2f} in {solve_time:.2f} s")
else:
print(f"Optimization standing: {standing} in {solve_time:.2f} s")
# assign variable values
self._assign_variable_values(standing=='Optimum')
return standingPulp’s LpProblem is initialized, the fixed LpMinimize defines it as a minimization downside — which means it’s supposed to reduce the worth of the target operate. Within the following traces all choice variables are initialized, the target operate in addition to all constraints are outlined. These strategies will probably be defined within the following sections.
Subsequent, the issue is solved, on this step the optimum worth of all choice variables is decided. Following the standing of the optimization is retrieved. When the standing is “Optimum” an optimum resolution may very well be discovered different statuses are “Infeasible” (it isn’t potential to satisfy all constraints), “Unbounded” (the target operate can have an arbitrary low values), and “Undefined” which means the issue definition isn’t full. In case no optimum resolution was discovered the issue definition must be reviewed.
Lastly, the optimized values of all variables are retrieved and assigned to the respective nodes and edges.
Defining choice variables
All choice variables are initialized within the technique beneath:
def _assign_variable_values(self, opt_found):
"""
assign choice variable values if optimum resolution discovered, in any other case set to None
@param opt_found: bool - if optimum resolution was discovered
"""
# assign edge values
for _, _, edge in tremendous().edges.knowledge():
# initialize values
edge['flow'] = None
edge['selected'] = None
# examine if optimum resolution discovered
if opt_found and edge['flow_var'] isn't None:
edge['flow'] = edge['flow_var'].varValue
if edge['selection_var'] isn't None:
edge['selected'] = edge['selection_var'].varValue
# assign node values
for _, node in tremendous().nodes.knowledge():
# initialize values
node['selected'] = None
if opt_found:
# examine if node has choice variable
if node['selection_var'] isn't None:
node['selected'] = node['selection_var'].varValue
First it iterates by means of all edges and assigns steady choice variables if the sting capability is larger than 0. Moreover, if fastened prices of the sting are higher than 0 a binary choice variable is outlined as effectively. Subsequent, it iterates by means of all nodes and assigns binary choice variables to nodes with fastened prices. The whole variety of steady and binary choice variables is counted and printed on the finish of the tactic.
Defining goal
In any case choice variables have been initialized the target operate may be outlined:
def _assign_objective_function(self):
"""
outline goal operate
"""
goal = 0
# add edge prices
for _, _, edge in tremendous().edges.knowledge():
if edge['selection_var'] isn't None: goal += edge['selection_var'] * edge['fixed_cost']
if edge['flow_var'] isn't None: goal += edge['flow_var'] * edge['variable_cost']
# add node prices
for _, node in tremendous().nodes.knowledge():
# add node choice prices
if node['selection_var'] isn't None: goal += node['selection_var'] * node['fixed_cost']
self.prob += goal, 'Goal',
The target is initialized as 0. Then for every edge fastened prices are added if the sting has a range variable, and variable prices are added if the sting has a move variable. For all nodes with choice variables fastened prices are added to the target as effectively. On the finish of the tactic the target is added to the LP object.
Defining constraints
All constraints are outlined within the technique beneath:
def _assign_constraints(self):
"""
outline constraints
"""
# rely of contraints
constr_count = 0
# add capability constraints for edges with fastened prices
for origin_name, destination_name, edge in tremendous().edges.knowledge():
# get capability
capability = edge['capacity'] if edge['capacity'] < float('inf') else self.max_flow
rhs = capability
if edge['selection_var'] isn't None: rhs *= edge['selection_var']
self.prob += edge['flow_var'] <= rhs, f"capacity_{origin_name}-{destination_name}",
constr_count += 1
# get origin node
origin_node = tremendous().nodes[origin_name]
# examine if origin node has a range variable
if origin_node['selection_var'] isn't None:
rhs = capability * origin_node['selection_var']
self.prob += (edge['flow_var'] <= rhs, f"node_selection_{origin_name}-{destination_name}",)
constr_count += 1
total_demand = total_supply = 0
# add move conservation constraints
for node_name, node in tremendous().nodes.knowledge():
# combination out and in flows
in_flow = 0
for _, _, edge in tremendous().in_edges(node_name, knowledge=True):
if edge['flow_var'] isn't None: in_flow += edge['flow_var']
out_flow = 0
for _, _, edge in tremendous().out_edges(node_name, knowledge=True):
if edge['flow_var'] isn't None: out_flow += edge['flow_var']
# add node capability contraint
if node['capacity'] < float('inf'):
self.prob += out_flow <= node['capacity'], f"node_capacity_{node_name}",
constr_count += 1
# examine what sort of node it's
if node['demand'] == node['supply']:
# transshipment node: in_flow = out_flow
self.prob += in_flow == out_flow, f"flow_balance_{node_name}",
else:
# in_flow - out_flow >= demand - provide
rhs = node['demand'] - node['supply']
self.prob += in_flow - out_flow >= rhs, f"flow_balance_{node_name}",
constr_count += 1
# replace whole demand and provide
total_demand += node['demand']
total_supply += node['supply']
if self.verbose:
print(f"Constraints: {constr_count}")
print(f"Whole provide: {total_supply}, Whole demand: {total_demand}")First, capability constraints are outlined for every edge. If the sting has a range variable the capability is multiplied with this variable. In case there is no such thing as a capability limitation (capability is about to infinity) however there’s a choice variable, the choice variable is multiplied with the utmost move that has been calculated by aggregating the demand of all nodes. An extra constraint is added in case the sting’s origin node has a range variable. This constraint signifies that move can solely come out of this node if the choice variable is about to 1.
Following, the move conservation constraints for all nodes are outlined. To take action the overall in and outflow of the node is calculated. Getting all in and outgoing edges can simply be completed by utilizing the in_edges and out_edges strategies of the DiGraph class. If the node has a capability limitation the utmost outflow will probably be constraint by that worth. For the move conservation it’s essential to examine if the node is both a supply or sink node or a transshipment node (demand equals provide). Within the first case the distinction between influx and outflow have to be higher or equal the distinction between demand and provide whereas within the latter case in and outflow have to be equal.
The whole variety of constraints is counted and printed on the finish of the tactic.
Retrieving optimized values
After operating the optimization, the optimized variable values may be retrieved with the next technique:
def _assign_variable_values(self, opt_found):
"""
assign choice variable values if optimum resolution discovered, in any other case set to None
@param opt_found: bool - if optimum resolution was discovered
"""
# assign edge values
for _, _, edge in tremendous().edges.knowledge():
# initialize values
edge['flow'] = None
edge['selected'] = None
# examine if optimum resolution discovered
if opt_found and edge['flow_var'] isn't None:
edge['flow'] = edge['flow_var'].varValue
if edge['selection_var'] isn't None:
edge['selected'] = edge['selection_var'].varValue
# assign node values
for _, node in tremendous().nodes.knowledge():
# initialize values
node['selected'] = None
if opt_found:
# examine if node has choice variable
if node['selection_var'] isn't None:
node['selected'] = node['selection_var'].varValue
This technique iterates by means of all edges and nodes, checks if choice variables have been assigned and provides the choice variable worth by way of varValue to the respective edge or node.
Demo
To display easy methods to apply the move optimization I created a provide chain community consisting of two factories, 4 distribution facilities (DC), and 15 markets. All items produced by the factories must move by means of one distribution heart till they are often delivered to the markets.
Node properties had been outlined:
Ranges imply that uniformly distributed random numbers had been generated to assign these properties. Since Factories and DCs have fastened prices the optimization additionally must determine which of those entities ought to be chosen.
Edges are generated between all Factories and DCs, in addition to all DCs and Markets. The variable price of edges is calculated because the Euclidian distance between origin and vacation spot node. Capacities of edges from Factories to DCs are set to 350 whereas from DCs to Markets are set to 100.
The code beneath exhibits how the community is outlined and the way the optimization is run:
# Outline nodes
factories = [Node(name=f'Factory {i}', supply=700, type="Factory", fixed_cost=100, x=random.uniform(0, 2),
y=random.uniform(0, 1)) for i in range(2)]
dcs = [Node(name=f'DC {i}', fixed_cost=25, capacity=500, type="DC", x=random.uniform(0, 2),
y=random.uniform(0, 1)) for i in range(4)]
markets = [Node(name=f'Market {i}', demand=random.randint(1, 100), type="Market", x=random.uniform(0, 2),
y=random.uniform(0, 1)) for i in range(15)]
# Outline edges
edges = []
# Factories to DCs
for manufacturing unit in factories:
for dc in dcs:
distance = ((manufacturing unit.x - dc.x)**2 + (manufacturing unit.y - dc.y)**2)**0.5
edges.append(Edge(origin=manufacturing unit, vacation spot=dc, capability=350, variable_cost=distance))
# DCs to Markets
for dc in dcs:
for market in markets:
distance = ((dc.x - market.x)**2 + (dc.y - market.y)**2)**0.5
edges.append(Edge(origin=dc, vacation spot=market, capability=100, variable_cost=distance))
# Create FlowGraph
G = FlowGraph(edges=edges)
G.min_cost_flow()The output of move optimization is as follows:
Variable varieties: 68 steady, 6 binary
Constraints: 161
Whole provide: 1400.0, Whole demand: 909.0
Mannequin creation time: 0.00 s
Optimum resolution discovered: 1334.88 in 0.23 sThe issue consists of 68 steady variables that are the sides’ move variables and 6 binary choice variables that are the choice variables of the Factories and DCs. There are 161 constraints in whole which include edge and node capability constraints, node choice constraints (edges can solely have move if the origin node is chosen), and move conservation constraints. The subsequent line exhibits that the overall provide is 1400 which is increased than the overall demand of 909 (if the demand was increased than the availability the issue can be infeasible). Since it is a small optimization downside, the time to outline the optimization mannequin was lower than 0.01 seconds. The final line exhibits that an optimum resolution with an goal worth of 1335 may very well be present in 0.23 seconds.
Moreover, to the code I described on this publish I additionally added two strategies that visualize the optimized resolution. The code of those strategies can be discovered within the repo.
All nodes are situated by their respective x and y coordinates. The node and edge dimension is relative to the overall quantity that’s flowing by means of. The sting shade refers to its utilization (move over capability). Dashed traces present edges with out move allocation.
Within the optimum resolution each Factories had been chosen which is inevitable as the utmost provide of 1 Manufacturing unit is 700 and the overall demand is 909. Nonetheless, solely 3 of the 4 DCs are used (DC 0 has not been chosen).
Basically the plot exhibits the Factories are supplying the closest DCs and DCs the closest Markets. Nonetheless, there are a couple of exceptions to this statement: Manufacturing unit 0 additionally provides DC 3 though Manufacturing unit 1 is nearer. That is because of the capability constraints of the sides which solely permit to maneuver at most 350 models per edge. Nonetheless, the closest Markets to DC 3 have a barely increased demand, therefore Manufacturing unit 0 is transferring further models to DC 3 to fulfill that demand. Though Market 9 is closest to DC 3 it’s equipped by DC 2. It’s because DC 3 would require a further provide from Manufacturing unit 0 to provide this market and for the reason that whole distance from Manufacturing unit 0 over DC 3 is longer than the space from Manufacturing unit 0 by means of DC 2, Market 9 is equipped by way of the latter route.
One other option to visualize the outcomes is by way of a Sankey diagram which focuses on visualizing the flows of the sides:
The colours signify the sides’ utilizations with lowest utilizations in inexperienced altering to yellow and pink for the very best utilizations. This diagram exhibits very effectively how a lot move goes by means of every node and edge. It highlights the move from Manufacturing unit 0 to DC 3 and in addition that Market 13 is equipped by DC 2 and DC 1.
Abstract
Minimal price move optimizations generally is a very useful device in lots of domains like logistics, transportation, telecommunication, power sector and plenty of extra. To use this optimization it is very important translate a bodily system right into a mathematical graph consisting of nodes and edges. This ought to be completed in a option to have as few discrete (e.g. binary) choice variables as vital as these make it considerably harder to seek out an optimum resolution. By combining Python’s NetworkX, Pulp and Pydantic libraries I constructed an move optimization class that’s intuitive to initialize and on the identical time follows a generalized formulation which permits to use it in many alternative use circumstances. Graph and move diagrams are very useful to know the answer discovered by the optimizer.
If not in any other case said all photographs had been created by the creator.