| [home] - [up] |
Abstract: A grid is a graph whose vertex set is the cartesian product S_1 x S_2 x ... S_n of finite sets, and whose edges consist of all pairs of vertices that differ in exactly one coordinate. The graph of the n-dimensional cube is an important special case.
A unique sink orientation (USO) of the grid is an orientation of the edges with the property that every nonempty subgrid has a unique sink.
USOs on grids naturally arise from linear programs on products of simplices, and from (generalized) linear complementarity problems. There is also an interesting connection to oriented matroids.
In the talk, I want to explain these connections and discuss algorithmic issues motivated by them. The main question always is: how fast can we find the global sink?
Colloquium - 16:00
Abstract: The Heterogeneous Fleet Vehicle Routing Problem (HFVRP), also known as the Fleet Size and Mix Vehicle Routing Problem, is defined as follows. Let G=(V,E) be an undirected graph where V={v_0, v_1,..., v_n} is the vertex set and E is the set of edges. Vertex v_0 represents a depot, where vehicles of different types are based, and the remaining vertices correspond to customers. Each customer has a given positive demand. A vehicle of a certain type has a given capacity, and associated with using the vehicle is a fixed cost and a cost which depends on the edges traversed by the vehicle. The number of vehicles of each type is assumed to be unlimited. The HFVRP consists of designing a set of vehicle routes, each starting and ending at the depot, and such that each customer is visited exactly once, the total demand of each route does not exceed the capacity of the vehicle assigned to it, and the total cost is minimized.
We survey some earlier work for this problem. Then a new mathematical formulation for the HFVRP is introduced, and a set of valid inequalities are suggested.