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:

1. we seek for the couple (ski, customer) having the smallest absolute difference,
2. we allocate this pair of skis to that customer
3. we start again with remaining skis and customers.
4. 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.

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.

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:

1. Create a graph corresponding to the ski rental instance,
2. compute the flow,
3. retrieve the corresponding mapping and,
4. 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