## セミナー -- Discrete Optimization Seminar

**
**

Title

**
Survivable Network Design Problems And Polyhedra
**

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).

Date

February 10 (Tue)& 17 (Tue), 2009, 15:00-16:00

Room

RIMS, Room 206

Speaker

Gleb Koshevoy

(Central Institute of Economics and Mathematics, Moscow)

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.

* Mathematical Programming

* Transportation and Logistics

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.