Minimal value move optimization minimizes the price of transferring move by way of a community of nodes and edges. Nodes embrace sources (provide) and sinks (demand), with completely different prices and capability limits. The intention is to search out the least pricey method to transfer quantity from sources to sinks whereas adhering to all capability limitations.
Functions
Functions of minimal value move optimization are huge and assorted, spanning a number of industries and sectors. This method is essential in logistics and provide chain administration, the place it’s used to attenuate transportation prices whereas making certain well timed supply of products. In telecommunications, it helps in optimizing the routing of knowledge by way of networks to cut back latency and enhance bandwidth utilization. The power sector leverages minimal value move optimization to effectively distribute electrical energy by way of energy grids, lowering losses and operational prices. City planning and infrastructure improvement additionally profit from this optimization approach, because it assists in designing environment friendly public transportation methods and water distribution networks.
Instance
Beneath is an easy move optimization instance:
The picture above illustrates a minimal value move optimization drawback with six nodes and eight edges. Nodes A and B function sources, every with a provide of fifty items, whereas nodes E and F act as sinks, every with a requirement of 40 items. Each edge has a most capability of 25 items, with variable prices indicated within the picture. The target of the optimization is to allocate move on every edge to maneuver the required items from nodes A and B to nodes E and F, respecting the sting capacities on the lowest attainable value.
Node F can solely obtain provide from node B. There are two paths: immediately or by way of node D. The direct path has a value of two, whereas the oblique path by way of D has a mixed value of three. Thus, 25 items (the utmost edge capability) are moved immediately from B to F. The remaining 15 items are routed by way of B -D-F to fulfill the demand.
At the moment, 40 out of fifty items have been transferred from node B, leaving a remaining provide of 10 items that may be moved to node E. The out there pathways for supplying node E embrace: A-E and B-E with a value of three, A-C-E with a value of 4, and B-C-E with a value of 5. Consequently, 25 items are transported from A-E (restricted by the sting capability) and 10 items from B-E (restricted by the remaining provide at node B). To satisfy the demand of 40 items at node E, a further 5 items 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 value 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 accommodates determination variables which might be steady, which means they will have any worth so long as all constraints are fulfilled. Resolution variables are on this case the move variables x(u, v) of all edges.
The target perform describes how the prices which might be presupposed to be minimized are calculated. On this case it’s outlined because the move multiplied with the variable value summed up over all edges:
Constraints are circumstances that have to be glad for the answer to be legitimate, making certain 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 return 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 damaging).
MILP
Moreover, to the continual variables of the LP formulation, the MILP formulation additionally accommodates 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 mounted prices for utilizing nodes or edges. On this article I present how one can add mounted prices. You will need to observe that including discrete determination variables makes it way more tough to search out an optimum answer, therefore this formulation ought to solely be used if a LP formulation will not be attainable.
The target perform is outlined as:
With three phrases: variable value of all edges, mounted value of all edges, and glued value of all nodes.
The utmost move that may be allotted to an edge depends upon 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 drawback.
Implementation
On this part I clarify how one can implement a MILP optimization in Python. You’ll find the code on this repo.
Libraries
To construct the move community, I used NetworkX which is a superb library (https://networkx.org/) for working with graphs. There are a lot of attention-grabbing articles that reveal 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 vital side when constructing an optimization is to guarantee that the enter is appropriately outlined. Even one small error could make the issue infeasible or can result in an surprising answer. To keep away from this, I used Pydantic to validate the consumer enter and lift any points on the earliest attainable stage. This article provides a straightforward to grasp introduction to Pydantic.
To remodel the outlined community right into a mathematical optimization drawback I used PuLP. Which permits to outline all variables and constraint in an intuitive manner. This library additionally has the benefit that it could actually use many various solvers in a easy pug-and-play trend. This article offers good introduction to this library.
Defining nodes and edges
The code under 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:
identify: str - identify 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
kind: str - kind of node
x: float - x-coordinate of node
y: float - y-coordinate of node
fixed_cost: float - value of choosing node
"""
identify: str
demand: Elective[float] = 0.0
provide: Elective[float] = 0.0
capability: Elective[float] = float('inf')
kind: 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
"""
# test that demand is non-negative
if self.demand < 0 or self.demand == float('inf'): increase ValueError('demand have to be non-negative and finite')
# test that offer is non-negative
if self.provide < 0: increase ValueError('provide have to be non-negative')
# test that capability is non-negative
if self.capability < 0: increase ValueError('capability have to be non-negative')
# test 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 way of the Node class which is inherited from Pydantic’s BaseModel. This allows an computerized validation that ensures that every one properties are outlined with the proper datatype each time a brand new object is created. On this case solely the identify is a required enter, all different properties are elective, if they aren’t supplied the desired 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 methodology 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 value and glued value should not damaging. Moreover, it additionally doesn’t permit infinite demand as this could result in an infeasible optimization drawback.
These checks look trivial, nevertheless their important profit is that they may set off an error on the earliest attainable stage when an enter is inaccurate. Thus, they forestall making a optimization mannequin that’s incorrect. Exploring why a mannequin can’t be solved can be way more time consuming as there are numerous components that will must be analyzed, whereas such “trivial” enter error will not be the primary side to research.
Edges are applied 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 way of edge
variable_cost: float - value per unit move by way of edge
fixed_cost: float - value 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
"""
# test that node names are completely different
if self.origin.identify == self.vacation spot.identify: increase ValueError('origin and vacation spot names have to be completely different')
# test that capability is non-negative
if self.capability < 0: increase ValueError('capability have to be non-negative')
# test that variable_cost is non-negative
if self.variable_cost < 0: increase ValueError('variable_cost have to be non-negative')
# test 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 value and glued value might 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 identify and the vacation spot node identify are completely different.
Initialization of flowgraph object
To outline the flowgraph and optimize the move I created a brand new class referred to 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 offers:
from networkx import DiGraph
from pulp import LpProblem, LpVariable, LpMinimize, LpStatus
class FlowGraph(DiGraph):
"""
class to outline and resolve minimal value move issues
"""
def __init__(self, nodes=[], edges=[]):
"""
initialize FlowGraph object
:param nodes: record of nodes
:param edges: record 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
"""
# test 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.identify, demand=node.demand, provide=node.provide, capability=node.capability, kind=node.kind,
fixed_cost=node.fixed_cost, x=node.x, y=node.y)
def add_edge(self, edge):
"""
add edge to graph
@param edge: Edge object
"""
# test if edge is an Edge object
if not isinstance(edge, Edge): increase ValueError('edge have to be an Edge object')
# test if nodes exist
if not edge.origin.identify in tremendous().nodes: self.add_node(edge.origin)
if not edge.vacation spot.identify in tremendous().nodes: self.add_node(edge.vacation spot)
# add edge to graph
tremendous().add_edge(edge.origin.identify, edge.vacation spot.identify, capability=edge.capability,
variable_cost=edge.variable_cost, fixed_cost=edge.fixed_cost)
FlowGraph is initialized by offering a listing of nodes and edges. Step one is to initialize the dad or mum class as an empty graph. Subsequent, nodes and edges are added by way of the strategies add_node and add_edge. These strategies first test if the supplied component is a Node or Edge object. If this isn’t the case an error will likely be raised. This ensures that every one components added to the graph have handed the validation of the earlier part. Subsequent, the values of those objects are added to the Digraph object. Observe that the Digraph class additionally makes use of add_node and add_edge strategies to take action. By utilizing the identical methodology identify I’m overwriting these strategies to make sure that each time a brand new component is added to the graph it have to be added by way of the FlowGraph strategies which validate the item kind. Thus, it’s not attainable to construct a graph with any component that has not handed the validation exams.
Initializing the optimization drawback
The tactic under converts the community into an optimization mannequin, solves it, and retrieves the optimized values.
def min_cost_flow(self, verbose=True):
"""
run minimal value 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 drawback
self.prob = LpProblem("FlowGraph.min_cost_flow", LpMinimize)
# assign determination variables
self._assign_decision_variables()
# assign goal perform
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()
# resolve LP drawback
self.prob.resolve()
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 answer 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 drawback — which means it’s supposed to attenuate the worth of the target perform. Within the following strains all determination variables are initialized, the target perform in addition to all constraints are outlined. These strategies will likely be defined within the following sections.
Subsequent, the issue is solved, on this step the optimum worth of all determination variables is set. Following the standing of the optimization is retrieved. When the standing is “Optimum” an optimum answer may very well be discovered different statuses are “Infeasible” (it’s not attainable to meet all constraints), “Unbounded” (the target perform can have an arbitrary low values), and “Undefined” which means the issue definition will not be full. In case no optimum answer 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 determination variables
All determination variables are initialized within the methodology under:
def _assign_variable_values(self, opt_found):
"""
assign determination variable values if optimum answer discovered, in any other case set to None
@param opt_found: bool - if optimum answer was discovered
"""
# assign edge values
for _, _, edge in tremendous().edges.knowledge():
# initialize values
edge['flow'] = None
edge['selected'] = None
# test if optimum answer discovered
if opt_found and edge['flow_var'] will not be None:
edge['flow'] = edge['flow_var'].varValue
if edge['selection_var'] will not be None:
edge['selected'] = edge['selection_var'].varValue
# assign node values
for _, node in tremendous().nodes.knowledge():
# initialize values
node['selected'] = None
if opt_found:
# test if node has choice variable
if node['selection_var'] will not be None:
node['selected'] = node['selection_var'].varValue
First it iterates by way of all edges and assigns steady determination variables if the sting capability is bigger than 0. Moreover, if mounted prices of the sting are better than 0 a binary determination variable is outlined as nicely. Subsequent, it iterates by way of all nodes and assigns binary determination variables to nodes with mounted prices. The entire variety of steady and binary determination variables is counted and printed on the finish of the tactic.
Defining goal
In any case determination variables have been initialized the target perform might be outlined:
def _assign_objective_function(self):
"""
outline goal perform
"""
goal = 0
# add edge prices
for _, _, edge in tremendous().edges.knowledge():
if edge['selection_var'] will not be None: goal += edge['selection_var'] * edge['fixed_cost']
if edge['flow_var'] will not be 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'] will not be None: goal += node['selection_var'] * node['fixed_cost']
self.prob += goal, 'Goal',
The target is initialized as 0. Then for every edge mounted 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 mounted prices are added to the target as nicely. On the finish of the tactic the target is added to the LP object.
Defining constraints
All constraints are outlined within the methodology under:
def _assign_constraints(self):
"""
outline constraints
"""
# rely of contraints
constr_count = 0
# add capability constraints for edges with mounted 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'] will not be 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]
# test if origin node has a range variable
if origin_node['selection_var'] will not be 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'] will not be None: in_flow += edge['flow_var']
out_flow = 0
for _, _, edge in tremendous().out_edges(node_name, knowledge=True):
if edge['flow_var'] will not be 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
# test what kind 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 complete demand and provide
total_demand += node['demand']
total_supply += node['supply']
if self.verbose:
print(f"Constraints: {constr_count}")
print(f"Complete provide: {total_supply}, Complete 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 isn’t any capability limitation (capability is ready 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. A further constraint is added in case the sting’s origin node has a range variable. This constraint implies that move can solely come out of this node if the choice variable is ready to 1.
Following, the move conservation constraints for all nodes are outlined. To take action the entire in and outflow of the node is calculated. Getting all in and outgoing edges can simply be executed through the use of the in_edges and out_edges strategies of the DiGraph class. If the node has a capability limitation the utmost outflow will likely be constraint by that worth. For the move conservation it’s essential to test 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 better or equal the distinction between demand and provide whereas within the latter case in and outflow have to be equal.
The entire variety of constraints is counted and printed on the finish of the tactic.
Retrieving optimized values
After operating the optimization, the optimized variable values might be retrieved with the next methodology:
def _assign_variable_values(self, opt_found):
"""
assign determination variable values if optimum answer discovered, in any other case set to None
@param opt_found: bool - if optimum answer was discovered
"""
# assign edge values
for _, _, edge in tremendous().edges.knowledge():
# initialize values
edge['flow'] = None
edge['selected'] = None
# test if optimum answer discovered
if opt_found and edge['flow_var'] will not be None:
edge['flow'] = edge['flow_var'].varValue
if edge['selection_var'] will not be None:
edge['selected'] = edge['selection_var'].varValue
# assign node values
for _, node in tremendous().nodes.knowledge():
# initialize values
node['selected'] = None
if opt_found:
# test if node has choice variable
if node['selection_var'] will not be None:
node['selected'] = node['selection_var'].varValue
This methodology iterates by way of all edges and nodes, checks if determination variables have been assigned and provides the choice variable worth by way of varValue to the respective edge or node.
Demo
To reveal how one can 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 need to move by way of one distribution heart till they are often delivered to the markets.
Node properties have been outlined:
Ranges imply that uniformly distributed random numbers have been generated to assign these properties. Since Factories and DCs have mounted prices the optimization additionally must resolve which of those entities must be chosen.
Edges are generated between all Factories and DCs, in addition to all DCs and Markets. The variable value 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 under 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 facility in factories:
for dc in dcs:
distance = ((manufacturing facility.x - dc.x)**2 + (manufacturing facility.y - dc.y)**2)**0.5
edges.append(Edge(origin=manufacturing facility, 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
Complete provide: 1400.0, Complete demand: 909.0
Mannequin creation time: 0.00 s
Optimum answer discovered: 1334.88 in 0.23 sThe issue consists of 68 steady variables that are the perimeters’ move variables and 6 binary determination variables that are the choice variables of the Factories and DCs. There are 161 constraints in complete 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 following line exhibits that the entire provide is 1400 which is larger than the entire demand of 909 (if the demand was larger than the availability the issue can be infeasible). Since it is a small optimization drawback, the time to outline the optimization mannequin was lower than 0.01 seconds. The final line exhibits that an optimum answer with an goal worth of 1335 may very well be present in 0.23 seconds.
Moreover, to the code I described on this put up I additionally added two strategies that visualize the optimized answer. 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 measurement is relative to the entire quantity that’s flowing by way of. The sting colour refers to its utilization (move over capability). Dashed strains present edges with out move allocation.
Within the optimum answer each Factories have been chosen which is inevitable as the utmost provide of 1 Manufacturing facility is 700 and the entire demand is 909. Nonetheless, solely 3 of the 4 DCs are used (DC 0 has not been chosen).
Typically 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 facility 0 additionally provides DC 3 though Manufacturing facility 1 is nearer. That is because of the capability constraints of the perimeters which solely permit to maneuver at most 350 items per edge. Nonetheless, the closest Markets to DC 3 have a barely larger demand, therefore Manufacturing facility 0 is transferring further items to DC 3 to fulfill that demand. Though Market 9 is closest to DC 3 it’s provided by DC 2. It is because DC 3 would require a further provide from Manufacturing facility 0 to provide this market and because the complete distance from Manufacturing facility 0 over DC 3 is longer than the space from Manufacturing facility 0 by way of DC 2, Market 9 is provided by way of the latter route.
One other method to visualize the outcomes is by way of a Sankey diagram which focuses on visualizing the flows of the perimeters:
The colours signify the perimeters’ utilizations with lowest utilizations in inexperienced altering to yellow and crimson for the best utilizations. This diagram exhibits very nicely how a lot move goes by way of every node and edge. It highlights the move from Manufacturing facility 0 to DC 3 and likewise that Market 13 is provided by DC 2 and DC 1.
Abstract
Minimal value move optimizations could be a very useful software 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 must be executed in a method to have as few discrete (e.g. binary) determination variables as mandatory as these make it considerably tougher to search out an optimum answer. 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 various use circumstances. Graph and move diagrams are very useful to grasp the answer discovered by the optimizer.
If not in any other case said all photographs have been created by the writer.
