Appunti Optimization and data science for management (primo parziale, parte 2)

Upton's production and inventory plan

• Upton's controller estimates that the cost of carrying a unit in any given month is approximately equal to 1.5% of the unit production cost in the same month (stocking costs).
• Upton estimates the number of units carried in inventory each month by averaging the beginning and ending inventory for each month (stock estimate). And we pay the stocking cost looking at this value: average between these 2 values, the inventory at the beginning and at the end of each month.
• There are 2,750 units currently in inventory (initial stock level).
• Upton wants to identify the production and inventory plan for the next six months that will meet the expected demand each month while minimizing production and inventory costs.

Flow conservation constraints

Flow conservation constraints + − = + 1

Stock balance à # # # # ( )

The stock with which I start the next month is equal to the stock with which I started #-%( ), ( ), ( ). this month plus what I produced minus what I sold # # #

A multiperiod production problem: the mathematical model

First constraint: what you have at the beginning of i+1 is equal to what you have at the beginning of the previous period + what you produce – demand.

Extension of this problem: consider a multicommodity problem, so you deal with multiple products instead of only one.

Multiperiod cash flow model (parameters in blue and variables in red).

Braess’ paradox

Braess’ paradox: a super user introduces a new way to reach 4, so now we have 3 possible paths.

The best option is when we find an equilibrium among all the possible paths that led to the destination.

Until now we consider linear cost, but this is not the case quite often in reality because it is more common to see that the cost depends on the amount of flow that you send in the graph.

Discrete (or combinatorial) optimization

The building blocks:

• Shortest and longest path
• Minimum cost flow
• Maximum flow
• Matching and assignment
• Spanning tree

And their integration into complex problems:

• Traveling salesmen problem
• Vehicle routing problem
• Network design problem

Integrate the blocks to create more complex problems.

Matching

Arcs are not directed here; a subgraph is a set of arcs where every node involved has a degree equal to 0 or 1.

If we add the red arc, we lose the match.

A matching is a subgraph in which every node has a degree (number of incident arcs) equal to 0 or to 1. No couple of arcs touch the same node.

What kind of graph?

The complexity of the problem depends on the structure of the underlying graph. We can have:

1. A bipartite graph: the algorithms specialize the general minimum cost flow algorithms.
2. A non-bipartite graph: ad-hoc algorithms are required and the resulting problems are more challenging to solve.

Typical matching problems

The difference is between the maximum cardinality (you are looking for the maximum number of arcs in the matching graph) and the minimum cost (select the proper number of arcs that respecting the match in order to minimize the cost).

Bipartite graph:

1. Maximum cardinality matching problem
2. Minimum cost assignment (perfect matching) problem
3. Bottleneck assignment problem
4. Stable matching

Non-bipartite graph:

Maximum cardinality matching problem – some sketch of the algorithmic idea.

Bipartite graph: personnel assignment

In the assignment of duties to new hires: the cardinality here is the same between the two group of nodes, to each worker is assigned to one shift.

In the selection of best team swimmers, the cardinality is different, this relies on our specific application.

Assignment of shifts to workers

For every worker you have a preference that the worker gives to the assignment.

Which is the best way of matching workers and shifts to minimize the total score of the assignment?

• The total score is 10, optimal value.
• In red the optimal solution is provided.

Which is the best way of matching workers and shifts to minimize the total score of the assignment? The variable is and they are a binary variable, so the value related to this variable is 1 if we #! assign the shift and 0 otherwise.

P set of staff, S set of shifts, preference of assigning I belong to P to j belong to S. #! ∗ - Min sum among all the possible I and j of #! #! = 1

• Summatory wrt j belong to S of for each I belong to P #! = 1
• Summatory wrt I belong to P of for each j belong to S #!
• Belong to {0, 1} for each I and j (domain definition). #!

Optimizing travel fares

Optimizing travel fares: we try to build a matching problem starting from the previous problem.

We can leave from London or Florence.

A feasible solution here is obtained by matching every node with only one of the other group.

We start from the most convenient arc, so from the green ones and since between the last arcs we have more than 21 days, we obtain 2 green arcs. Now we move to the yellow arc and the red one if necessary.

If you start in a greedy way but at the end you enter in a node that is already connected you don’t obtain a feasible solution.

Optimal solution: it’s not so far from the greedy solution we find before, the difference is small here.

Assignment: object tracking

• Estimate speed and direction of movement of n moving objects.
• 2 consecutive pictures for each object.
• Matching object position in the 2 pictures.

Assume 2 pictures with n objects each. 5! 5{( , )}

The coordinates of item j in frame f are known! The problem is the following: which object in frame A matches which in frame B? It’s a matching problem with costs.

Notation used

Assumptions:

• Assumption 1: w.l.o.g. we can assume |O|=|D| (use dummy nodes if this is not the case).
• Assumption 2: the graph is not directed. We don’t have any type of orientation in the graph.

⊆ Definition 1: a matching is a subset of arcs that have no nodes in common.

We do not have in common in a matching. When we have a matching with maximum cardinality (perfect), so where each node is associated with an arc, we speak about assignment.

The cardinality here is the same, respecting the 1 assumption.

st ∈ Definition 2: given a matching M, node is exposed with respect to (w.r.t.) M when no arc in M touches node i. A node is exposed wrt a match if no arc touches that node.

Definition 3: M is a perfect matching (assignment) when no node I in N is exposed.

No exposed node = perfect matching = assignment.

Maximum cardinality matching problem and maximum flow

Among all the possible matches we want to find one with highest cardinality. Maximum flow problem can be used in this case to find this match.

If we have 3, so the amount of flow sent through the graph (represent the cardinality of the 2 group of nodes), we obtain matching. We have an implicitly capacity on each arc. The 2 dummy nodes serve to us in order to build a circular problem like we saw in the maximum flow problem. Then the path we obtain represent exactly the match with the highest cardinality.

You obtain a perfect match only if the maximum flow problem you send an amount of flow equal to the cardinality of the nodes.

How to transform the network

Node set: add dummy super-origin and super-destination nodes N = O U D U {s, t} à

Arc set à

• Direct each arc (I, j) in the original network from I to j, no capacity on these arcs.
• Add arcs (s, i) for each i in O with capacity equal to one.
• Add arcs (i, t) for each i in D with capacity equal to one.
• Add dummy arc (t, s).

Solve a maximum flow problem from s to t on the transformed network. Flow on arc (t, s) represents the (maximum) cardinality of the matching.

The algorithm and the computational complexity

The maximum cardinality matching problem can be solved by means of a maximum flow algorithm.

The peculiar structure of the resulting graph (when arcs have a unitary capacity the graph is called a simple graph) allows for an efficient spec