Research Trends in Combinatorial Optimization

We revisit classical systems of linear inequalities associated with location problems and with the

p

-median problem. We present an overview of the cases for which these linear systems define integral polytopes. We also give polynomial time algorithms to recognize these cases.

A major goal of polyhedral combinatorics is to find classes of essential, i.e. facet inducing, inequalities which describe a combinatorially defined polyhedron

P

. In general this is a difficult task. We consider the case in which we have knowledge of facets for a face

F

of

P

, and present a general technique for exploiting the close relationship between such polyhedra in order to obtain facets for

P

from facets of

F

. We demonstrate the usefulness of this technique by applying it in three instances where this relationship holds, namely the linear ordering polytope and the acyclic subgraph polytope, the asymmetric travelling salesman polytope and the monotone asymmetric travelling salesman polytope, and the symmetric travelling salesman polytope and the two-connected spanning subgraph polytope. In the last case we obtain a class of facet inducing inequalities for the two-connected spanning subgraph polytope by our procedure. This technique has also been applied by Boyd and Hao (

1993

) to show a class of inequalities is facet inducing for the two edge connected spanning subgraph polytope, by Leung and Lee (

1994

) to show a class of inequalities is facet inducing for the acyclic subgraph polytope and by Bauer (

1997

) to show several classes of inequalities are facet inducing for the circuit polytope.

The above technique requires that we demonstrate validity of an inequality. We discuss the problem of proving an inequality is valid for the integer hull of a polyhedron, and show that this problem is in NP for classes of polyhedra having bounded Chvátal–Gomory rank. This has the following consequence. Suppose we have an integer programming formulation of the members of an NP-complete class of problems with the property that we can, in polynomial time, show the validity of our defining inequalities. Then there will be problems in the class for which a linear system sufficient to define the integer hull will necessarily contain an inequality of arbitrarily large Chvátal–Gomory rank unless NP = co-NP.

Two classical examples of antimatroids arise from double shellings of partially ordered sets and from simplicial shellings of triangulated graphs. The corresponding convex geometries have Carathéodory number two and admit a natural description in terms of the ternary relation of betweenness in the underlying structure. We characterize a nested pair of classes of betweenness which generate convex geometries of Carathéodory number two. The corresponding antimatroids include all antimatroids arising from double shellings of partially oredred sets and all antimatroids arising from simplicial shellings of triangulated graphs.

We present a class of instances of the existence of a second object of a specified type, in fact, of an even number of objects of a specified type, which generalizes the existence of an equilibrium for bimatrix games. The proof is an abstract generalization of the Lemke–Howson algorithm for finding an equilibrium of a bimatrix game.

We present a new algorithm for the problem of determining the intersection of a half-line

$\Delta_{u}=\{x\in \mathbb{R}^{N}\:|\:x=\lambda u\;\mathrm {for}\;\lambda \geq 0\}$

with a polymatroid. We then propose a second algorithm which generalizes the first algorithm and solves a parametric linear program. We prove that these two algorithms are strongly polynomial and that their running time is

O

(

n

8

+

γ

n

7

) where

γ

is the time for an oracle call. The second algorithm gives a polynomial algorithm to solve the submodular function minimization problem and to compute simultaneously the strength of a network with complexity bound

O

(

n

8

+

γ

n

7

).

In this survey we present recent advances on problems that can be described as the construction of graphs or hypergraphs that cover certain set functions with supermodular or related properties. These include a wide range of network design and connectivity augmentation and orientation problems, as well as some results on colourings and matchings.

In the first part of the paper we survey results that follow from the totally dual integral (TDI) property of various systems defined by supermodular-type set functions. One of the aims of the survey is to emphasize the importance of relaxing the supermodularity property to include a wider range of set functions. We show how these relaxations lead to a unified understanding of different types of applications.

The second part is devoted to results that, according to our current knowledge, cannot be explained using total dual integrality. We would like to demonstrate that an extensive theory independent of total dual integrality has been developed in the last 15 years, centered around various connectivity augmentation problems.

Our survey concentrates on the theoretical foundations, and does not include every detail on applications, since the majority of these applications are described in detail in another survey paper by the first author (Frank

2006

). The comprehensive book “Combinatorial Optimization: Polyhedra and Efficiency” by Schrijver (

2003

) is also a rich resource of results related to submodular functions.

It should be noted that sub- and supermodularity have several applications in areas not discussed in this paper. In particular, we should mention the book “Submodular Functions and Optimization” by Fujishige (

2005

) and the book “Discrete Convex Analysis” by Murota (

2003

). The former explains the foundations of the theory of submodular functions and describes the methods of submodular analysis, while the latter presents a unified framework for nonlinear discrete optimization by extending submodular function theory using ideas from continuous optimization. Our survey focuses on topics not discussed in detail in those books.

The theory of principal partitions of discrete systems such as graphs, matrices, matroids, and submodular systems have been developed since 1967. In the early stage of the developments during 1967–75 the principal partition was considered as a decomposition of a discrete system into its components together with a partially ordered structure of the set of the components. It then turned out that such a decomposition with a partial order on it arises from the submodularity structure pertinent to the system and it has been realized that the principal partitions are closely related to resource allocation problems with submodular structures, which are kind of dual problems.

The aim of this paper is to give an overview of the developments in the theory of principal partitions and some recent extensions with special emphasis on its relation to associated resource allocation problems in order to make it better known to researchers in combinatorial optimization.

We present an example for a new approach which seems applicable to every graph theoretical concept defined by local conditions and regular graphs of large girth. It combines a random outer procedure processing the graph in rounds with a virtually arbitrary algorithm solving local instances within each round and combines the local solutions to a global one. The local uniformity of the considered instances and the randomness of the outer procedure make the asymptotic analysis possible. Here we apply this approach to the simplest yet fundamental example of a locally defined graph theoretical concept: independent sets in graphs.

For an integer

d

≥3 let

α

(

d

) be the supremum over all

α

with the property that for every

ε

>0 there exists some

g

(

ε

) such that every

d

-regular graph of order

n

and girth at least

g

(

ε

) has an independent set of cardinality at least (

α

−

ε

)

n

.

Considerably extending the work of Lauer and Wormald (Large independent sets in regular graphs of large girth, J. Comb. Theory, Ser. B

97

, 999–1009, 2007) and improving results due to Shearer (A note on the independence number of triangle-free graphs, II, J. Comb. Theory, Ser. B

53

, 300–307, 1991) and Lauer and Wormald, we present the best known lower bounds for

α

(

d

) for all

d

≥3.

Many real-world problems require graphs of such large size that polynomial time algorithms are too costly as soon as their runtime is superlinear. Examples include problems in VLSI-design or problems in bioinformatics. For such problems the question arises: What is the best solution that can be obtained in linear time? We survey linear time approximation algorithms for some classical problems from combinatorial optimization, e.g. matchings and branchings.

This paper presents a survey of the unbounded knapsack problem. We focus on the techniques for obtaining the optimal solutions, particularly those using the periodic structure of the optimal solutions when the knapsack weight-carrying capacity

b

is sufficiently large. In addition to reviewing existing algorithms on the subject, the paper also includes two new algorithms, one for finding the onset of the optimal periodic solutions in time

O

(

nw

1

), where

w

1

is the weight of the best item, i.e. the item with the highest value-to-weight ratio, and a second one for finding the optimal solutions when the capacity

b

is below the critical value where the optimal periodic solution begins. The second algorithm has a worst-case time complexity of

O

(

nw

1

v

1

), where

v

1

is the value of the best item.

This paper describes recent developments in discrete convex analysis. Particular emphasis is laid on natural introduction of the classes of L-convex and M-convex functions in discrete and continuous variables. Expansion of the application areas is demonstrated by recent connections to submodular function maximization, finite metric space, eigenvalues of Hermitian matrices, discrete fixed point theorem, and matching games.

We provide a tableau of 189 entries and some annotations presenting the computational complexity of integer multiflow feasibility problems; 21 entries remain open. The tableau is followed by an introduction to the field, providing more problems, reproving some results with new insights, simple proofs, or slight sharpenings motivated by the tableau, paying particular attention to planar (di)graphs with terminals on the boundary. Last, the key-theorems and key-problems of the tableau are listed.

In this paper we survey results related to homomorphism dualities for graphs, and more generally, for finite structures. This is related to some of the classical combinatorial problems, such as colorings of graphs and hypergraphs, and also to recently intensively studied Constraint Satisfaction Problems. On the other side dualities are related to the descriptive complexity and First Order definability as well as to universal graphs. And in yet another context they can be expressed as properties of the homomorphism order of structures. In the contemporary context homomorphism dualities are a complex area and it is our aim to describe some of the main ideas only. However we introduce the four conceptually different proofs of the existence of duals thus indicating the versatility of this notion. Particularly we describe setting of restricted dualities and the role of bounded expansion classes.

A dominating set of vertices

S

of a graph

G

is connected if the subgraph

G

[

S

] is connected. Let

γ

c

(

G

) denote the size of any smallest connected dominating set in

G

. Graph

G

is

k

-

γ

-connected-vertex-critical (abbreviated “

k

cvc”) if

$\gamma_{c}(G)=\nobreak k$

, but if any vertex

v

is deleted from

G

, then

γ

c

(

G

−

v

)≤

k

−1.

This concept of vertex criticality stands in contrast to the concept of criticality with respect to edge addition in which a graph

G

is defined to be

k

-connected-critical if the connected domination number of

G

is

k

, but if any edge is added to

G

, the connected domination number falls to

k

−1.

It is well-known that the only 1cvc graph is

K

1

and the 2cvc graphs are obtained from the even complete graphs

K

2

n

, with

n

≥2, by deleting a perfect matching. In this paper we survey some recent results for the case when

γ

c

=3. In Sect. 14.2 we present some recently derived basic properties of 3cvc graphs, especially with respect to connectivity, and then present three new infinite families of 3cvc graphs. In Sect. 14.3, we present some new matching results for 3cvc graphs.

Much progress has been made in recent years in solving certain classes of production planning problems using mixed integer programming. One of the major challenges is how to make this expertise available and relatively easy to use for the non-specialist and the practitioner. Here we describe a modeling approach and tool LS-LIB.

LS-LIB is a library of primitives to declare procedures/subroutines/global constraints in a high-level modeling language that we believe offers an interesting partial answer to this challenge. LS-LIB provides routines for problem reformulation, cut generation, and heuristic solution of instances. The user must provide an initial formulation of his problem in the chosen modeling language MOSEL. Then using knowledge of the problem the user must first classify each product or sku according to a simple three field scheme: [production type, capacity type, variant]. Then it is a simple matter to use the global constraints of LS-LIB by adding a few lines to the initial modeling language formulation to get a tightened formulation and/or call the appropriate cut generation routines. The heuristic procedures are called in a similar fashion. The result is a tool that allows researchers and end-users to improve the solution time and quality of a variety of production planning problems within minutes. The library incorporates much of the modeling knowledge concerning lot-sizing problems derived over the last twenty years, and is also easy to maintain and extend.

We illustrate the use of LS-LIB on an intractable two-level problem, and a difficult multi-level problem.

The Distinct Element Method (DEM) is a popular tool to perform granular media simulations. The two key elements this requires are an adequate model for inter-particulate contact forces and an efficient contact detection method. Originally, this method was designed to handle spherical-shaped grains that allow for efficient contact detection and simple yet realistic contact force models. Here we show that both properties carry over to grains of a much more general shape called spheropolyhedra (Minkowski sums of spheres and polyhedra). We also present some computational experience and results with the new model.

In this paper we study particular submodular functions that we call “graphic”. A graphic submodular function is defined on the edge set

E

of a graph

G

=(

V

,

E

) and is equal to the sum of the rank-function of

G

and of a linear function on

E

. Several polynomial algorithms are known that can be used to minimize graphic submodular functions and some were adapted to an equivalent problem called “Optimal Attack” by Cunningham. We collect eight different algorithms for this problem, including a recent one (initially developed for solving a problem for physics): it consists of |

V

|−1 steps, where the

i

-th step requires the solution of a network flow problem on a subgraph (with slight modifications) induced by at most

i

vertices of the given graph (

i

=2,…,|

V

|). This is a fully combinatorial algorithm for this problem: contrary to its predecessors, neither the algorithm nor its proof of validity use directly linear programming or keep any kind of dual solution. The approach is direct and conceptually simple, with the same worst case asymptotic complexity as the previous ones. Motivated by applications, we also show how this combinatorial approach to graphic submodular function minimization provides efficient solution methods for several problems of combinatorial optimization and physics.

Matroids are applied in electric engineering for over 30 years. These applications motivated the investigation of some new, pure matroidal questions. Such results are surveyed for readers with mathematical (rather than engineering) background.

An integral part of combinatorial optimization and computational complexity consists of establishing relationships between different problems or different versions of the same problem. In this chapter, we bring together known and new, previously published and unpublished results, which establish that 15 problems related to optimizing a linear function over a 0/1-polytope are polynomial-time equivalent. This list of problems includes optimization and augmentation, testing optimality and primal separation, sensitivity analysis and inverse optimization, as well as several others.

In recent years, several new models for network flows have been analyzed, inspired by emerging telecommunication technologies. These include models of

resilient flow

, motivated by the introduction of high capacity optical links,

coloured flow

, motivated by Wavelength-Division-Multiplexed optical networks,

unsplittable flow

motivated by SONET networks, and

confluent flow

motivated by next-hop routing in internet protocol (IP) networks. In each model, the introduction of new side-constraints means that a max-flow min-cut theorem does not necessarily hold, even in the setting where all demands are destined to a common node (sink) in the network. In such cases, one may seek bounds on the “flow-cut gap” for the model. Such approximate max-flow min-cut theorems are a useful measure for bounding the impact of new technology on congestion in networks whose traffic flows obey these side constraints.

We give an introduction into the fascinating area of flows over time—also called “dynamic flows” in the literature. Starting from the early work of Ford and Fulkerson on maximum flows over time, we cover many exciting results that have been obtained over the last fifty years. One purpose of this chapter is to serve as a possible basis for teaching network flows over time in an advanced course on combinatorial optimization.

A. Frank (Augmenting graphs to meet edge-connectivity requirements, SIAM J. Discrete Math.

5

(1), 22–53, 1992) developed a method to solve edge-connectivity augmentation problems. His paper has stimulated further research in a number of directions, including many interesting generalizations.

This paper surveys the current State of the Art on the edge-connectivity augmentation problem. Recent extensions of the problem are presented for undirected graphs, hypergraphs and more generally for set functions. Shortened proofs are provided for some of the results. A list of open problems is also presented.

I shall discuss some of the more well known counting problems associated with graphs and matroids. Except in special cases all these problems have no exact counting algorithm which runs in polynomial time unless there is a remarkable collapse of some existing classes. Hence the focus is on obtaining fast algorithms which give good approximations. The problems studied include counting forests, trees and colourings of graphs and bases of matroids.