888411 OPERATIONS RESEARCH FOR DIGITAL INNOVATION NETWORK OPTIMIZATION MODELS LECTURER DR. SARONSAD SOKANTIKA 9TH FEB 2021 PROTOTYPE EXAMPLE: SEERVADA PARK 4 Problems Find shortest-path from entrance O to station T (The shortest-path problem) PROTOTYPE EXAMPLE: SEERVADA PARK 4 Problems Install Telephone Line to connect all stations (The minimum spanning tree problem) PROTOTYPE EXAMPLE: SEERVADA PARK 4 Problems Tram ride from entrance O to station T is limited by the number of tram trips can be made on each roads per day, due to the ecological reasons. How to route the various trips to maximize the number of trips per day (the maximum flow problem) You want to find a shortest path to patrol each station in this park and comeback to the starting point. PROTOTYPE EXAMPLE: SEERVADA PARK 4 Problems (the traveling salesman problem (allow repeated visits)) THE TERMINOLOGY OF NETWORKS Node or Vertex Arc or Edge THE TERMINOLOGY OF NETWORKS Directed Arc/Edge THE TERMINOLOGY OF NETWORKS Undirected Arc or Link Directed network: have only directed arc Undirected network: have only undirected arc THE TERMINOLOGY OF NETWORKS A path between two node is a sequence of distinct arc connecting these nodes. Example: one of the path connecting node O and T is OB-BD-DT (O→B→ D→ T) THE TERMINOLOGY OF NETWORKS A directed path from node i to node j is a sequence of connecting arcs whose direction (if any) toward node j. An undirected path from node i to node j is a sequence of connecting arcs whose direction (if any) can be toward or away from node j. THE TERMINOLOGY OF NETWORKS Consider a path B → C→ A→ D from B to D. is it directed or undirected path THE TERMINOLOGY OF NETWORKS A path that begin and end at the same node is called cycle. If it care about direction, we called it directed cycle. If it is not, we called it undirected cycle. Could you give some example THE TERMINOLOGY OF NETWORKS Two node are connected if there exist an undirected path between them. A connected network is a network where every pair of nodes is connected THE TERMINOLOGY OF NETWORKS A network G is a subnetwork of network H if each node/arc of G is a node/arc of H. THE TERMINOLOGY OF NETWORKS A spanning tree of a connected network H is a connected subnetwork that contain each node of H and has no undirected cycle. Noted: If H has n node, then every spanning tree of H has n-1 arcs THE TERMINOLOGY OF NETWORKS: Flows Arc capacity: the maximum amount of flow that can be carried on a directed Supply node: flow out of the node exceed flow into the node. Demand node: flow into the node exceed flow out of the node. Transshipment node : flow into the node equal to flow out of the node THE TERMINOLOGY OF NETWORKS: Flows Net Flow of a node is equal to flow out of the node minus flow into the node. EXAMPLE OF NETWORKS IN THE REAL WORLD THE SHORTEST-PATH PROBLEM Find shortest-path from entrance O to station T The shortest-path problem is a special type of linear programming problem Let formulate and solve in excel! THE SHORTEST-PATH PROBLEM Three Major Categories of Applications Minimize the total distance traveled Minimize the total cost of a sequence of activities Minimize the total time of a sequence of activities THE MINIMUM SPANNING TREE PROBLEM You wish to design th
e network by inserting enough links to satisfy the requirement that there be a path between every pair of nodes. That is, you want to find a minimum spanning tree. THE MINIMUM SPANNING TREE PROBLEM To solve this problem, we use a greedy algorithm as follows: Select any node arbitrarily to be a starting node, say node S. Let’s called any node connected node if it connect with node S. Otherwise, called it unconnected node. Identify the unconnected node that is closest to a connected node, then connect these two node. Break the tie arbitrary. Repeat this process until each node is connected node. THE MINIMUM SPANNING TREE PROBLEM Choose node O as a starting node. Connect it with the closest unconnected node. THE MINIMUM SPANNING TREE PROBLEM Find closest unconnected node. Connect it with the closest unconnected node. THE MINIMUM SPANNING TREE PROBLEM Find closest unconnected node. Connect it with the closest unconnected node. THE MINIMUM SPANNING TREE PROBLEM Find closest unconnected node. Connect it with the closest unconnected node. THE MINIMUM SPANNING TREE PROBLEM Find closest unconnected node. Connect it with the closest unconnected node. THE MINIMUM SPANNING TREE PROBLEM Find closest unconnected node. Connect it with the closest unconnected node. Since each node is connected to the starting node, we stop the process THE MINIMUM SPANNING TREE PROBLEM This greedy algorithm has iterative nature. Even though MST problems can be formulated by using linear programming, the number of constraint is huge (exponential with respect to number of nodes). THE MAXIMUM FLOW PROBLEM Tram ride from entrance O to station T is limited by the number of tram trips can be made on each roads per day, due to the ecological reasons. How to route the various trips to maximize the number of trips per day THE MAXIMUM FLOW PROBLEM Cut value of a cut is the sum of the arc capacities of the arcs (in the direction from the source to the sink) of the cut. This cut has cut value equal to 14. THE MAXIMUM FLOW PROBLEM The Max-Flow Min-Cut Theorem For any network with the single source and sink, the maximum feasible flow from the source to the sink equals the minimum cut value of cuts that separate the source and the sink. THE MAXIMUM FLOW PROBLEM If you write an algorithm based on The Max-Flow Min-Cut Theorem, it will have an iterative nature. We can formulate this problem by using linear programming. Let’s see it in excel! THE TRAVELING SALESMAN PROBLEM (allow repeated visits) You want to find a shortest path to patrol each station in this park and comeback to the starting point. THE TRAVELING SALESMAN PROBLEM (allow repeated visits) We can formulate this problem as an Integer programming. Here, we will formulate this problem as a nonlinear non-smooth programming. Let’s see in the excel. THE MINIMUM COST FLOW PROBLEM THE MINIMUM COST FLOW PROBLEM THE MINIMUM COST FLOW PROBLEM Here are some subproblem of minimum cost flow problem The transportation problem The assignment problem The transshipment problem The shortest-path problem The maximum flow problem THE MINIMUM COST FLOW PROBLEM THE MINIMUM COST FLOW PROBLEM THE MINIMUM COST FLOW PROBLEM Let’s formulate and solve this example in the excel. Thank You for Your Attention!