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

An elementary blending problem

We are given: a set of materials (scraps) and their unit cost, a set of elements and their minimum quantity required in the blend, the composition of each material in terms of elements.

The problem asks to determine which/how many materials (variable x) must be used to make a blend satisfying the chemical requirements (one for each element) at minimum cost.

Xi is the quantity of material I to use in the blend. is the selling price of pure material!

Dual problem

The objective function maximized the total revenue, given the request of each metal.

The constraints ensure that selling prices are competitive. As an example, to buy something equivalent to material A, the selling price cannot be greater than the cost of material A.

Complementary slackness $( ) − = 0# # #

From the solution of one problem, we can find the solution for the other problem.

Network flows

Definitions

• N is a finite set of nodes.
• A is a finite set of arcs, each consisting in a pair of nodes, and a relationship between two nodes.
• G (N, A) is a graph.

Assumptions

• An arc (I, j) is a pair of nodes from N.
• It can be ordered or not.
• When it is ordered, (I, j) is different from (j, i), while when it is not ordered (I, j) is the same as (j, i).
• Formally, when arcs are ordered, the graph is called di-graph (directed graph), but we simply call it graph.
• W.l.o.g A does not contain nor loops (arc of the form (I, j)) neither parallel arcs (two or more arcs identified by same pairs of nodes).

The shortest path problem

We want to find the path with the minimum cost given:

• A directed graph G= (N, A) with node set N and arc set A.
• Two special nodes: the origin s to the destination t.
• Cost associated with arc (i, j) in A#!.
• No upper capacity on arcs.

The problem asks to find a min cost path from s to t.

Incidence matrix of the graph E

• Rows represent nodes.
• Columns represent arcs.

Given a directed graph G= (N, A), assuming there are no loops or parallel arcs, E has |N| rows, |A| columns and its elements are defined as follow:

The mathematical function -x is the vector of variables (one item for each arc).

-E is the incidence matrix.

-c is the cost vector.

-b is the balance vector with

The structure of the problem

The incidence matrix E cannot have a rank greater than |N-1| (summing up all the rows we obtain the null vector). The rank is exactly |N|-1 if and only if the graph is connected. Any square submatrix of E has determinant in {0, 1, -1}. Any square non-singular matrix has an integer inverse matrix. If the balance vector is integer, each basic solution is integer.

Does the path change if 100 vehicles have to travel it? If we have two different paths with same cost we can use both, for example, 50 vehicles on a path and 50 vehicles on the other.

Example

The American Car Association (ACA) provides various services, including road route planning. Given a road network (to be constructed with appropriate level of abstraction) one wants to find a path from a source (Birmingham, node 1) to a destination (Virginia Beach, node 11) that is the “best” with respect to the user’s chosen utility function: minimum travel, maximum scenic rate.

= = = = 1, Travelling time solution: 0 otherwise%& &' '( %)%%

Driving time= 11.5 and scenic rate=15.

Scenic rate solution: driving time=15.9 and scenic rate=35.

What happens if we compute the most scenic path with a driving time not greater than 14?

Grafico da aggiungere

When the shortest path problem is well defined?

The graph must be connected. It may contain cycles (loops) such as B-D-C, but the cost of cycle must be >=0.

In this example the shortest path problem is well defined, it is s-A-C-t, it has a cost equal to 11. The presence of cycle with positive cost does not invalidate the correctness of the LP formulation. In this example the shortest path is not unique. The paths s-A-C-t, s-A-C-B-D-C-t, s-A-C-B-D-C-B-D-C-t, … have the same optimal cost equal to 11.

But, if the cost of cycle is <0?

In the paths s-A-C-t, s-A-C-B-D-C-B-D-C-t, … the cost decreases to a not finite negative value. Each time the cycle is run the cost decrease by one unit. The LP model detects this situation correctly stating that the LP problem is unbounded from below. The problem isn’t well formulated.

In this example, the shortest path exists, it is s-A-C-t with a cost equal to 11, but the LP model does not detect it. In the LP, the optimal solution does not exist since travelling along the path s-A-C-t and running the cycle C-D-B for ever let the objective function unbounded from below.

Putting capacity of arcs fixes the problem?

≤ 1) Adding capacity constraints on arcs ( does not fix the issue. In the LP, the optimal solution is not a path: it is given by the path s-A-t plus the cycle B-D-C-B, and it has an optimal cost equal to 3+(-7) =-4.

Indeed, the shortest path exists, it’s s-B-D-t and its cost is -1.

The shortest path problem – a class of algorithms

Given a graph G= (N, A) with n nodes (|N|=n), consider the shortest path problem from a source node s to all others: how much memory is needed to store the n-1 shortest paths?

n(n-1) is an upper bound on the required memory. Can we do better? Yes.

The optimality property of sub paths does hold.

I want to find n-1 shortest path. How much memory I need? For every node which is in the shortest path. So, I don’t have to store every shortest path. The tree represents every shortest path.

Grafico

Special cases

• The case of cyclic network: Topological ordering of graph nodes (for each arc (i, j) in A, i<j). Dynamic programming algorithm: considering nodes in increasing order and checking the optimality condition for the arcs existing that node. Do you remember the optimality conditions?
• The case of nonnegative costs and Dijkstra’s algorithm.

Optimality condition from the LP

Primal problem Dual problem.

In dual we have a constraint for each arc.

Is the dual variable.

The dual feasibility is the optimality condition in Dijkstra’s algorithm.

The general case

We can define two classes of algorithms - label setting - label correcting.

Both of them are iterative algorithms, and at each iteration they assign distance labels d(i) to the nodes (i) in network that represent upper bounds on the minimum path length from s to i.

Example

GRAFICO

We have to find shortest path from s to i. We need to fix label d(i) to the optimal value this is the end of the algorithm.

They differ in the way they manage labels:

• Label setting: at each iteration, at least the label of one node becomes “permanent” (optimal label). This impose a limit at number of iterations, once every node is labelled the algorithm end, so n interactions=n nodes. This is very efficient.
• Label correcting: for all the nodes, the labels stay “temporary” until the algorithm stops. At termination, all the labels become “permanent” at the same time. It’s more difficult to find an upper bound to the number of iterations. The other algorithm is more efficient but have some limitations, we cannot use it for every situation.

(PREDECESSOR FUNCTION?)

Example

Grafico

*(#)-. !"./0$ () + ≤ ()

Two alternative paths if we update the label because this path is better. #!

The shortest path tree with root sM is an upper bound very high cost. ,

If at the end of the algorithm the label of a node is still it means that this node is () = ; disconnected from the network (at the beginning we initialize the label therefore, if).a smaller cost were found, the node’s label would no longer be.

List

List is a data structure, how to implement it?

• Dijkstra’s algorithm when the costs are nonnegative and at each iteration the node in LIST with minimum label is selected. This is the optimal value this is the shortest path for the node.
• Dynamic programming when the graph is acyclic and nodes are selected from LIST in topological order when LIST= stack (LIFO – last in first out), is very efficient in practice, improvements propagations, worst computational complexity.
• With LIST=queue (FIFO – first in first out), best theoretical complexity.

LIST=DEQUEUE, the first time a node is inserted, it is inserted at the end; if it is inserted again, insert at the beginning (It is inserted at the beginning suppongo).

Cycle with negative cost

Cycle with negative cost = | |

Assume that (#,!)∈3 #!() ≥ −( − 1)

Then (lower bound on the label of each node).

When the above condition is violated, a negative cost cycle has been detected: following the predecessor of the involved nodes we are able to identify the cycle.

When LC+FIFO, the algorithm scans the arc list n times and at iteration k it determines the shortest paths given by at most k arcs. It is then sufficient to check that a node is not inserted more than n times. If this happens, we are in the presence of a negative cost cycle.

Until we are on a path the label can’t be lower of lower bound, when you enter in a negative cycle (problem) cost goes to −∞.

All-pairs shortest path problem

We can adjust costs to have a more efficient algorithm.

* = + () − () reduced cost of (i, j) #! #! * (),

The cost of cycle w in terms of reduced costs, is the same as the cost in terms of the original costs, C(P), plus the difference between the labels of origin-destination, i.e. * () = () + () − () with this you don’t care the form of the of the graph. It doesn’t