# TD04 - Dynamic programming

Implementation in Python of exercise 2 of TD 4. It consists in solving the Ski Rental problem using three different algorithms.

Each code you need to complete is followed by tests to verify that it is correct.

Exercise plan:

- Greedy algorithm
- Dynamic programming
- Maximum flow minimum cost [advanced]

## Greedy algorithm

Complete the code below to implement a greedy algorithm greedy_map which allocates skis using the following method:

- we seek for the couple (ski, customer) having the smallest absolute difference,
- we allocate this pair of skis to that customer
- we start again with remaining skis and customers.
- the algorithm stops when all customers have their assigned skis.

Inputs :

- Skis : a dictionary of available skis' sizes. A ski size can be added several times in the list if several pairs of this size are available. There will be as many occurrences as available pairs. An example of an entry of the dictionary is 's1' : 155.
- Customers : a dictionary of customers' heights, an example of an entry of the dictionary is 'c1' : 150. We suppose there are enough skis for all customers.

output :

- mapping : the expected output is a python dictionary of the form {'c1':'s1', 'c2':'s3', ...} that describes which ski pair was given to each custommer

####### Inputs example ########## skis = {'s1':170, 's2':180, 's3':170, 's4':155, 's5':175, 's6':175, 's7':160, 's8':190} # available skis customers = {'c1':186, 'c2':173, 'c3':150, 'c4':200} # skiers heights def greedy_map(skis, customers): # better work on copies S = skis.copy() C = customers.copy() mapping = {} ############### TODO : complete code ##################### return mapping ####### Testing ######### # to compute the cost of a mapping (i.e. the sum of size differences) def mapping_cost(skis, customers, mapping): return sum([abs(customers[c] - skis[mapping[c]]) for c in customers]) greedy_mapping = greedy_map(skis, customers) greedy_cost = mapping_cost(skis, customers, greedy_mapping) print("GREEDY -- mapping:", greedy_mapping, "cost:", greedy_cost) assert greedy_cost == 31

## Dynamic programming

We have n pairs of skis for m customers. We note {$Sol[i, j]$} the cost of the optimal solution (i.e. the sum of size differences) for the {$i$} first pairs of skis and the {$j$} first customers. We want to apply the dynamic programming approach to find the cost of the optimal solution {$Sol[n, m]$}. We will implement the recursive formula stated in the TD.

Complete the code below and test it on the same inputs. It should improve the previously computed greedy mapping.

We need first to order the skis and customers is the ascending order of their sizes and then index them starting from 1.

import numpy as np def dyn_sol(skis, customers): ####### Inputs ########## n = len(skis) # n pairs of ski m = len(customers) # m customers # sort and index the skis and customers depending on their size # the trick "['_'] +" is to start indexing from 1 (not 0) # S[i] gives the key of the i-th ski in the ascending order of their sizes # C[j] gives the key of the j-th customer in the ascending order of their sizes S = ['_'] + sorted(list(skis.keys()), key = lambda s: skis[s]) C = ['_'] + sorted(list(customers.keys()), key = lambda c: customers[c]) ####### Output ########## # init the table Sol = np.empty([n+1,m+1], dtype = object) ############### TODO : complete code ##################### return Sol, S, C ####### Testing ######### dyn_table, _ , _ = dyn_sol(skis, customers) dyn_cost = dyn_table[-1][-1] # the cost is the last cell of the table assert dyn_cost == 23 print("Dynamic programming -- cost:", dyn_cost) # greedy is far from optimal skis2 = {'s1':170, 's2':140} customers2 = {'c1':160, 'c2':200} greedy_cost2 = mapping_cost(skis2, customers2, greedy_map(skis2, customers2)) dyn_cost2 = dyn_sol(skis2, customers2)[0][-1][-1] assert greedy_cost2 == 70 assert dyn_cost2 == 50

### Retrieve the solution

Now that we computed the table {$Sol$}, we need to retrieve the corresponding **optimal** mapping. Complete the code below to retrieve the dyn_mapping from Sol.

def dyn_map(dyn_solution): Sol, S, C = dyn_solution mapping = {} ############### TODO : complete code ##################### return mapping ####### Testing ######### dyn_mapping = dyn_map(dyn_sol(skis, customers)) print("Dynamic programming -- mapping:", dyn_mapping) assert mapping_cost(skis, customers, dyn_mapping) == dyn_cost dyn_mapping2 = dyn_map(dyn_sol(skis2, customers2)) assert dyn_mapping2 == {'c2': 's1', 'c1': 's2'}

## Maximum flow -- Minimum cost [advanced]

There is a polynomial algorithm to solve the maximum flow minimum cost problem. This algorithm is not trivial to code. However, it is already implemented in the Python networkx library. To use it, we must transform our data inputs to a suitable graph.

If you didn't install the Python module networkx in a previous TD-practice, depending on your distribution/OS, you may use the Anaconda GUI or try this command: pip3 --user install "networkx>=2.2"

To create a graph, add nodes, add edges and compute the flow, use the following primitives:

import networkx as nx # creates an empty graph G = nx.DiGraph() # adds a node in the G graph identified by a label G.add_node('label') # adds an arc between the nodes having labels u and v and assigns the capacity and the cost of that edge. G.add_edge(u, v, weight=x, capacity=y) # computes the max flow min cost on G from node of label s to node of label t flow = nx.algorithms.max_flow_min_cost(G, s, t) # to retrieve/explore the flow. It is an adjacency structure (a dictionary of dictionaries) print(flow[u][v])

To solve the problem:

- Create a graph corresponding to the ski rental instance,
- compute the flow,
- retrieve the corresponding mapping and,
- verify that you compute optimal solutions

import networkx as nx def flow_map (skis, customers): ############### TODO : complete code ##################### return mapping flow_mapping = flow_map(skis, customers) flow_cost = mapping_cost(skis, customers, flow_mapping) print("Flow max Cost min -- mapping:", flow_mapping, "cost:", flow_cost) assert dyn_cost == flow_cost assert mapping_cost(skis2, customers2, flow_map(skis2, customers2)) == 50