Research Institute for Mathematical Sciences

Date

June 24 (Thursday), 2010, 13:30--15:00

Room

RIMS, Room 006

Speaker

A. Ridha Mahjoub (Université Paris Dauphine)

Abstract

The introduction of fiber optic technology in telecommunication has increased the need of designing survivable networks. Survivable networks must satisfy some connectivity requirements. That is, networks are still functional after the failure of certain links. More precisely, we are given a graph G=(V,E) with costs on the edges. For each node v there is a nonnegative integer r(v), called connectivity type of v, that represents the importance of communication from and to node v. The survivable conditions require that between every pair of nodes (s,t) there are at least min{r(s),r(t)} edge-disjoint paths. The survivable network design problem is to determine a subgraph of G that minimizes the total cost subject to the survivable conditions.

In this talk we will discuss some variants of this problem. First we consider the 2-edge connected subgraph problem, the case where r(v)=2 for every node. We characterize the graphs for which the linear relaxation of the problem is integral, and present some algorithmic consequences of that characterization. In particular we show that the so-called F-partition inequalities can, in some cases, be separated in polynomial time. Then we consider the problem when r(v)=1 or 2 for every node v. This case is of particular interest to the telecommunication industry. We present a class of inequalities, also called partition inequalities, valid for the problem in this case. And we show that the separation problem for these inequalities reduces to the minimization of a submodular function, and can then be solved in polynomial time. We finally discuss some computational issues of these inequalities and present some extensions when length constraints are considered in the network.

Title

On the Integrality Gap of the Multi-Survivable Network Design Problem

Date

April 8 (Thursday), 2010, 15:00--16:00

Room

RIMS, Room 110

Speaker

Sylvia Boyd (University of Ottawa)

Abstract

Given a complete graph G on n nodes with non-negative node connectivity requirements r_i for every node i and non-negative edge costs, we consider the problem of finding a minimum cost connected subgraph of G that has at least min(r_i,r_j) edge-disjoint paths between every pair of distinct nodes i and j. In the case where multiple copies of an edge are allowed in the solution, this is known as the multi-survivable network design problem (multi-SNDP). We establish an upper bound on the integrality gap for the linear programming relaxation of multi-SNDP. We also present an approximation algorithm for multi-SNDP with this bound as a performance guarantee. We show that these results are improvements over the best known bounds for certain special cases of the problem. We also find the exact value of the integrality gap for small values of n for the special case of the problem where r_i is 2 for all nodes i.

Title

On packing and covering problems with underlying submodular structure

Date

May 28 (Thu), 10:00--

Room

RIMS Annex (Research Building No.4), Room 307

Speaker

Britta Peis (Technical University of Berlin)

Abstract

Optimizing a linear function over a linear inequality system specified by a binary matrix A and a ``rank'' function r can be interpreted as a packing or covering problem. While finding optimal integral solutions of such problems is NP-hard in general, several efficient algorithms have been found for special instances. An important role is played by packing and covering problems which can be solved in a greedy way.
In the talk I will present a greedy-type algorithm for a very general class of packing and covering problems in which the row set family corresponding to the binary matrix A can be partially ordered in a ``nice'' way: it forms a sub- [super-]modular consecutive lattice on which r is super-[sub-]modular and monotone increasing. Our model fits into the framework of Hoffman and Schwartz' lattice polyhedra and covers optimization problems such as finding shortest paths or min-cost arborescences in a digraph, an optimal basis of a polymatroid, or a maximum flow in a planar graph. Moreover, it has interesting applications in cooperative game theory.
Additionally, I will present iterative rounding algorithms for finding an optimal integral vector in a lattice polyhedron satisfying certain ``degree bounds``.
Our results generalize or even improve several results on optimization problems with degree bounds like the degree bounded min-cost spanning tree or arborescence problem.
The content of the talk is based on joint work with Ulrich Faigle, Nikhil Bansal and Viswanath Nagarajan.

Title

Modelling and solving integer programming problems: capacitated clustered vehicle routing and sorting of rolling stock

Date

May 7 (Thursday), 13:30--

Room

RIMS Annex (Research Building No.4), Room 307

Speaker

Uwe Zimmermann
(Institute of Mathematical Optimization, Braunschweig, Germany)

Abstract

In recent years, the main line of research of my working group aims at modeling and solving hard (mixed) integer programming problems from differing areas of application. In this talk, I will discuss models, algorithms and results for capacitated clustered vehicle routing (CCVR) in waste management and for sorting of rolling stock (SRS). Vehicle routing is a well established area of research. Here, I will present some preliminary models and results on a new ongoing project of the working group. SRS is a new and growing research area which I preliminary surveyed in this seminar in 2007. Here, I will present an updated, compact survey and discuss some old and new unsolved problems. All results represent joint work of my working group at Braunschweig.

Title

Pl\"ucker environments, wiring, and tiling diagrams

Date

March 24 (Tue), 2009, 13:30-15:00

Room

RIMS, Room 206

Speaker

Gleb Koshevoy
(Central Institute of Economics and Mathematics, Moscow)

Abstract

For the ordered set $[n]$ of $n$ elements, we consider the class ${\cal B}_n$ of bases $B$ of tropical Pl\"ucker functions on $2^{[n]}$ such that $B$ can be obtained by a series of mutations (flips) from the basis formed by the intervals in $[n]$ . We show that these bases are representable by special wiring diagrams and by certain arrangements generalizing rhombus tilings on the $n$-zonogon.
Based on the generalized tiling representation, we then prove that each weakly separated set-system in $2^{[n]}$ having maximum possible size belongs to ${\cal B}_n$, thus answering affirmatively a conjecture due to Leclerc and Zelevinsky (an interest in studying weakly separated collections is inspired, in particular, by the problem of characterizing all families of quasicommuting quantum flag minors, which in turn comes from exploration of Lusztig's canonical bases).

Title

Feb 10 :Tropical Plücker functions and TP-polymatroids
Feb 17 :Bases of Tropical Plücker functions and crystal structures on MV-polytopes

Abstract

February 10
$M^{\natural}$-concave functions due to Murota (or polymatroidal discrete concave functions in the classification due to Danilov and Koshevoy) can be defined in local terms (going back to Dress and Wenzel). There are two sorts of such local conditions: 2-dimensional, submodularity and skew-submodularity, and 3-dimensional, octahedron conditions.
We consider an extension of the class of such function, having forgot all 2-dimensional conditions.
Tropical Plücker functions form a subclass of such an extension defining by a specialization of the octahedron conditions.
Such functions are of importance in combinatorics (octahedron recursion) and physics (discrete Hirota equation).
Such functions are defined on an interesting subclass of polymatroids, which we call TP-polymatroids.
Due to the octahedron recursion, we can propagate such functions from one set to a large one, moreover, given a TP-polymatroid, such functions form a polyhedral cone. For truncated boxes we describe bases of such a cone.
We will also describe bases which allow to propagate 2-dimensional conditions of submodularity and skew-submodularity, and thus we will obtain bases for TP-discrete concave functions on truncated boxes.


February 17
An interesting class of polymatroids can be associated to submodular TP-functions defined on a Boolean cube. We show that such class of polymatroids coincides with the class of MV-polytopes (Anderson, Kamnitzer) which is obtained by another construction in the frame of representation theory: MV-polytopes are images of the moment map of MV-cycles (of A-type) in affine Grassmanians. We describe the crystal structure on the class of such polytopes in terms of bases of TP-functions.
Because complexity of TP-polymatroids is n^2 (in dimension n), we suggest a question of finding an algorithm for minimization of a submodular TP-function in a linear time.

Title

Partitioning of labeled sequences, graph coloring and the sorting of rolling stock problem: a survey

Date

August 28, 2007, 13:30--15:00

Room

RIMS, Room 206

Speaker

Uwe T. Zimmermann
(Institute of Mathematical Optimization, TU Braunschweig)

Abstract

Managing rolling stock on rails requires, in particular, effective sorting of rail cars and trains. These practical problems motivate the study of a surprisingly large class of related sorting problems, many of which can be modeled as partitioning of labeled sequences into suitable subsequences. Alternative formulations lead to coloring problems in graphs or hypergraphs, network design models and mixed integer programming models. Depending on the complexity of the model, the presentation covers exact, approximation or online algorithms. The survey includes joint work with colleagues for several years.

Title

The sorting of rolling stock problem: selected topics and open problems

Date

August 21, 2007, 13:30--15:00

Room

RIMS, Room 206

Speaker

Uwe T. Zimmermann
(Institute of Mathematical Optimization, TU Braunschweig)

Abstract

The sorting of rolling stock problem [SRS] comprises a large class of special sorting problems; some of them turn out to be easily solvable, but most of them are NP-hard optimization problems. After some motivating, introductory examples for [SRS], we will discuss results for selected mathematical optimization models and present some of the more or less open problems.

Title

Greedy Systems

Date

March 6 (Tue), 2007, 14:00--16:00

Room

RIMS, Room 206

Speaker

Ulrich Faigle
(Mathematisches Institut, Zentrum fuer Angewandte Informatik, Universitaet zu Koeln)

Abstract

In the context of greedoids, Goetschel and Goecke have exhibited combinatorial structures that are more general than matroids and yet allow the optimization of non-negative (resp. unrestricted) linear objective functions by greedy algorithms. Shenmaier recently extended Goetschel's results to systems of integral vectors and separable discrete concave objective functions. The first part of the talk presents a comprehensive model for the optimization of objective functions that are compatible with a partial order on the ground set and characterizes greedy systems within this model by a general strong exchange property. This model contains Goetschel, Goecke and Shenmaier as special cases. The talk will also point out the relationship of this general model with ordered matroids (of which distributive supermatroids and integral polymatroids are special cases) and submodular functions.

The second part explores algorithmic aspects of lattice polyhedra. Hoffman has introduced the latter model as a powerful tool for proving integrality results for combinatorial linear programs with certain sub- and supermodular constraints. Frank has provided a greedy algorithm for a class of lattice polyhedra with supermodular constraints. Hoffman and Dietrich have recently introduced certain ''pseudolattices'' and given an optimal Monge-type algorithm for the associated lattice polyhedra, which seemingly generalize polymatroids. We now show how Hoffman and Dietrich's model can be understood within the context of polymatroids. Moreover, a greedy algorithm for the maximization of linear functions over certain lattice polyhedra is presented, yielding a submodular analogue of Frank's model.

(The talk is based on joint work with Britta Peis.)

Title

Parametric Min Cuts: How Far, How Fast?

Date

January 23 (Tue), 2007, 15:00--16:00

Room

RIMS, Room 206

Speaker

S. Thomas McCormick (Sauder School of Business, UBC, Vancouver, Canada)

Abstract

The need to solve minimum cut problems when arc capacity is a function of a scalar parameter arises in a surprising number of applications. Carstensen showed that the number of pieces of the min cut value function can be exponential even for linear capacities, and so computing the cut value function is not always easy. Gallo, Grigoriadis, and Tarjan (GGT) showed that for a particular class of parametric graphs, optimal min cuts are nested in the parameter, and so there can be only O(n) pieces in the cut value function. GGT further showed how to compute the entire cut value function in the same time as O(1) calls to the Push-Relabel max flow algorithm. The "nestedness" part of GGT's result is a special case of a general result of Topkis.

We show what Topkis' result looks like when specialized to parametric min cut. We further show how to achieve the same efficiency as GGT in this general case via a fast flow update from one value of the parameter to the next. Then we show some other classes of parametric min cut where we can achieve similar results, but which are not special cases of the Topkis-like result. Finally we consider Milgrom and Shannon's Single Crossing Condition as yet another way to get nested min cuts.

(Joint work with F. Granot*, M. Queyranne*, and F. Tardella**)
* Sauder School of Business, UBC
** Universita La Sapienza (Rome)

Title

The chromatic polynomial of a graph

Date

January 19 (Fri), 2007, 16:00--17:30

Room

RIMS, Room 115

Speaker

Carsten Thomassen (Technical University of Denmark)

Abstract

The chromatic polynomial P(G,k) of a graph G is the number of colorings of G with k available colors. The chromatic polynomial was introduced by Birkhoff in 1912 in order to study the 4-Color Problem. Although the chromatic polynomial has not been very successful for coloring problems, it has been studied for several other reasons, primarily by mathematicians but also by physicists. In this talk, basic properties of the chromatic polynomial will be discussed, including arecent connection to the Hamiltonian cycle (travelling salesman's) problem.

Title

Rank and independence in the 3-dimensional rigidity matroid

Date

November 21 (Tue), 2006, 13:30--14:30

Room

RIMS, Room 206

Speaker

Tibor Jordán (Eötvös University, Budapest)

Abstract

It is a difficult open problem to characterize generic rigidity of graphs in 3 dimensions. We give a short survey of results concerning special families of graphs for which a good characterization of rigidity (or more generally, rank) is known, and for which the number of the degrees of freedom can be computed efficiently. We also discuss old and new conjectures for other special families of graphs.

In particular, we consider a bar-and-joint formulation of the Molecular Conjecture, which was originally posed in 1984 by T-S. Tay and W. Whiteley in terms of body-and-hinge frameworks. This conjecture indicates that determining whether the square of a graph is rigid (or computing its rank) may be tractable by combinatorial methods. (Two vertices u,v are adjacent in the square G^2 of graph G if and only if they are adjacent or they have a common neighbour in G.) We prove that the conjectured formula for the rank of the square of a graph is indeed an upper bound on its rank.

Title

Pin-collinear Body-and-Pin Frameworks and the Molecular Conjecture

Date

November 14 (Tue), 2006, 13:30--14:30

Room

RIMS, Room 206

Speaker

Tibor Jordán (Eötvös University, Budapest)

Abstract

T-S. Tay and W. Whiteley independently proved that a multigraph G can be realized as an infinitesimally rigid body-and-hinge framework in R^d if and only if the graph obtained from G by replacing each edge of G by (d+1)d/2-1 parallel edges has (d+1)d/2 edge-disjoint spanning trees. In 1984 they jointly conjectured that each graph in this family can be realized as an infinitesimally rigid framework with the additional property that the hinges incident to each body lie in a common hyperplane. This conjecture has become known as the Molecular Conjecture because of its implication for the rigidity of molecules in 3-dimensional space. In this talk we sketch our recent solution for the 2-dimensional version of the Molecular Conjecture. The proof relies on a new formula for the maximum rank of a pin-collinear body-and-pin realization of a multigraph as a 2-dimensional bar-and-joint framework as well as on new structural results on graphs containing k edge-disjoint spanning trees.

This result is joint work with Bill Jackson (London).

Title

The Conjugate Gradient Method with Automatic Preconditioning

Date

October 31 (Tue), 2006, 13:30--14:30

Room

RIMS, Room 206

Speaker

Nicholas Harvey (MIT)

Abstract

Solving a linear system is one of the most fundamental computational problems. Unfortunately, the basic algorithm that most of us learn (Gaussian Elimination) is often useless in practice due to slow running time or stability issues. Instead, it is more common to use iterative solvers, the simplest ones being steepest descent and conjugate gradient. The difficulty with iterative solvers is that their performance often depends on the "condition number" of the given system, so it is common to modify the given system by applying a "preconditioner" matrix which reduces the condition number. This raises a key question: given a linear system, how can we find a good preconditioner?

In this work, we develop a variant of conjugate gradient method which *automatically* constructs good preconditioners. The general idea is very simple. We run the conjugate gradient method until it "gets stuck". The fact that it is stuck then implies a way to modify the preconditioner so that the conjugate gradient steps will be "less stuck" in the future.

This talk will be self-contained -- the audience only needs to know basic linear algebra, and how to interpret pictures of algorithms that are stuck.

Joint work with John Dunagan, Microsoft Research.

Title

Exploiting algebraic symmetry in semidefinite programs

Date

October 11 (Wed), 2006, 10:30--11:30

Room

RIMS, Room 115

Speaker

Etienne de Klerk (Associate Professor, Department of Econometrics and Operations Research, Faculty of Economics and Business Administration, Tilburg University)

Abstract

Semidefinite Programming (SDP) may be seen as a generalization of Linear Programming (LP). In particular, one may extend interior point algorithms for LP to SDP, but it has proven much more difficult to exploit structure in the data in the SDP case during computation.

We consider one specific type of structure in SDP data, namely where the data matrices are invariant under the action of a permutation group. Such problems arise in truss topology optimization, particle physics, coding theory, computational geometry, and graph theory.

We will give an overview of existing techniques to exploit this structure in the data.

The basic idea is that we may assume that the optimal solution of the SDP lies in the commutant (centralizer ring) of the permutation group. The centralizer ring allows a more economical representation than the entire feasible set.

We will focus on a recent technique [1] that uses the so-called regular *-representation of the centralizer ring. To illustrate this technique, we will consider three applications:
  * computing lower bounds on the crossing number of complete bipartite graphs;
  * computing the theta function for graphs with `large symmetry groups';
  * truss topology optimization problems where the ground structure of nodes has symmetries.

Reference:
[1] E. de Klerk, D.V. Pasechnik and A. Schrijver. Reduction of symmetric semidefinite programs using the regular *-representation. Mathematical Programming B, to appear.

Title

The Integral Basis Method in Primal Integer Programming based on joint works with Robert Weismantel, Matthias Koeppe, Giovanni Rinaldi, Claudio Gentile and Raymond Hemmecke

Date

February 2 (Thu), 2006, 15:00-16:00

Room

RIMS, Room 009

Speaker

Utz-Uwe Haus (Otto-von-Guericke University of Magdeburg GERMANY, Scientific Assistant)

Abstract

The Integral Basis Method was proposed as a new algorithm for solving mixed-integer linear programming problems a few years ago. It is a primal algorithm working in the simplex tableau, and does not resort to branching or cutting planes. This talk will present the basic algorithm (simplex-like phase I, augmentation and optimality proofs), a specialization to the stable set problem, and give a perspective on current research.