Polyhedral results for two-connected networks with bounded rings

We study the polyhedron associated with a network design problem which consists in determining at minimum cost a two-connected network such that the shortest cycle to which each edge belongs (a “ring”) does not exceed a given length K.?We present here a new formulation of the problem and derive facet results for different classes of valid inequalities. We study the separation problems associated to these inequalities and their integration in a Branch-and-Cut algorithm, and provide extensive computational results. Received: September 1999 / Accepted: February 2002?Published online May 8, 2002     

Two-edge connected spanning subgraphs and polyhedra

This paper studies the problem of finding a two-edge connected spanning subgraph of minimum weight. This problem is closely related to the widely studied traveling salesman problem and has applications to the design of reliable communication and transportation networks. We discuss the polytope associated with the solutions to this problem. We show that when the graph is series-parallel, the polytope is completely described by the trivial constraints and the so-called cut constraints. We also give some classes of facet defining inequalities of this polytope when the graph is general.Research supported in part by the Natural Sciences and Engineering Research Council of Canada and CP Rail and the German Research Association (Deutsche Forschungsgemeinschaft SFR 303).     

Metrics with finite sets of primitive extensions

In this paper, we give a complete characterization for the class of rational finite metrics with the property that the set () of primitive extensions of is finite. Here, for a metric on a setT, a positive extensionm of to a setV T is calledprimitive if none of the convex combinations of other extensions of toV is less than or equal tom. Our main theorem asserts that the following the properties are equivalent: (i) () is finite; (ii) Up to an integer factor, is a submetric of the path metric d ^H of a graphH with |(d ^H )=1; (iii) A certain bipartite graph associated with contains neither isometrick-cycles withk6 nor induced subgraphsK _3,3 ^– . We then show that () is finite if and only if the dimension of the tight span of is at most two. We also present other results, discuss applications to multicommodity flows, and raise open problems.This research was supported by grant 97-01-00115 from the Russian Foundation of Basic Research and a grant from the Sonderforschungsbereich 343, Bielefeld Universität, Bielefeld, Germany.     

A network flow-based method to solve performance cost and makespan open-shop scheduling problems with time-windows

This paper deals with several bicriteria open-shop scheduling problems where jobs are pre-emptable and their corresponding time-windows must be strictly respected. The criteria are a performance cost and the makespan. Network flow approaches are used in a lexmin procedure with a bounded makespan and the considered bicriteria problems are solved. Finally, the computational complexity of the algorithm and a numerical example are reported.     

Free multiflows in bidirected and skew-symmetric graphs

A graph (digraph) G=(V,E) with a set T⊆V of terminals is called inner Eulerian if each nonterminal node v has even degree (resp. the numbers of edges entering and leaving v are equal). Cherkassky and Lovász, independently, showed that the maximum number of pairwise edge-disjoint T-paths in an inner Eulerian graph G is equal to , where λ(s) is the minimum number of edges whose removal disconnects s and T-{s}. A similar relation for inner Eulerian digraphs was established by Lomonosov. Considering undirected and directed networks with “inner Eulerian” edge capacities, Ibaraki, Karzanov, and Nagamochi showed that the problem of finding a maximum integer multiflow (where partial flows connect arbitrary pairs of distinct terminals) is reduced to O(logT) maximum flow computations and to a number of flow decompositions.In this paper we extend the above max-min relation to inner Eulerian bidirected graphs and inner Eulerian skew-symmetric graphs and develop an algorithm of complexity for the corresponding capacitated cases. In particular, this improves the best known bound for digraphs. Our algorithm uses a fast procedure for decomposing a flow with O(1) sources and sinks in a digraph into the sum of one-source-one-sink flows.     

A stabilized column generation scheme for the traveling salesman subtour problem

Given an undirected graph with edge costs and both revenues and weights on the vertices, the traveling salesman subtour problem is to find a subtour that includes a depot vertex, satisfies a knapsack constraint on the vertex weights, and that minimizes edge costs minus vertex revenues along the subtour.We propose a decomposition scheme for this problem. It is inspired by the classic side-constrained 1-tree formulation of the traveling salesman problem, and uses stabilized column generation for the solution of the linear programming relaxation. Further, this decomposition procedure is combined with the addition of variable upper bound (VUB) constraints, which improves the linear programming bound. Furthermore, we present a heuristic procedure for finding feasible subtours from solutions to the column generation problems. An extensive experimental analysis of the behavior of the computational scheme is presented.     

One-Dimensional Cutting Stock Problem with a Given Number of Setups: A Hybrid Approach of Metaheuristics and Linear Programming

One-dimensional cutting stock problem (1D-CSP) is one of the representative combinatorial optimization problems, which arises in many industrial applications. Since the setup costs for switching different cutting patterns become more dominant in recent cutting industry, we consider a variant of 1D-CSP, called the pattern restricted problem (PRP), to minimize the number of stock rolls while constraining the number of different cutting patterns within a bound given by users. For this problem, we propose a local search algorithm that alternately uses two types of local search processes with the 1-add neighborhood and the shift neighborhood, respectively. To improve the performance of local search, we incorporate it with linear programming (LP) techniques, to reduce the number of solutions in each neighborhood. A sensitivity analysis technique is introduced to solve a large number of associated LP problems quickly. Through computational experiments, we observe that the new algorithm obtains solutions of better quality than those obtained by other existing approaches.     

Bounds on the Chvátal Rank of Polytopes in the 0/1-Cube*

Gomorys and Chvátals cutting-plane procedure proves recursively the validity of linear inequalities for the integer hull of a given polyhedron. The Chvátal rank of the polyhedron is the number of rounds needed to obtain all valid inequalities. It is well known that the Chvátal rank can be arbitrarily large, even if the polyhedron is bounded, if it is 2-dimensional, and if its integer hull is a 0/1-polytope.We show that the Chvátal rank of polyhedra featured in common relaxations of many combinatorial optimization problems is rather small; in fact, we prove that the rank of every polytope contained in the n-dimensional 0/1-cube is at most n ² (1+log n). Moreover, we also demonstrate that the rank of any polytope in the 0/1-cube whose integer hull is defined by inequalities with constant coefficients is O(n).Finally, we provide a family of polytopes contained in the 0/1-cube whose Chvátal rank is at least (1 + ) n, for some > 0.* An extended abstract of this paper appeared in the Proceedings of the 7th International Conference on Integer Programming and Combinatorial Optimization [20].     

Fast Cycle Canceling Algorithms for Minimum Cost Submodular Flow*

This paper presents two fast cycle canceling algorithms for the submodular ow problem. The rst uses an assignment problem whose optimal solution identies most negative node-disjoint cycles in an auxiliary network. Canceling these cycles lexicographically makes it possible to obtain an optimal submodular ow in O(n ⁴ h log(nC)) time, which almost matches the current fastest weakly polynomial time for submodular flow (where n is the number of nodes, h is the time for computing an exchange capacity, and C is the maximum absolute value of arc costs). The second algorithm generalizes Goldbergs cycle canceling algorithm for min cost flow to submodular flow to also get a running time of O(n ⁴ h log(nC)).. We show how to modify these algorithms to make them strongly polynomial, with running times of O(n ⁶ h log n), which matches the fastest strongly polynomial time bound for submodular flow. We also show how to extend both algorithms to solve submodular flow with separable convex objectives. * An extended abstract of a preliminary version of part of this paper appeared in [22]. Research supported in part by a Grant-in-Aid of the Ministry of Education, Science, Sports and Culture of Japan. Research supported by an NSERC Operating Grant. Part of this research was done during a sabbatical leave at Cornell SORIE.§ Research supported in part by a Grant-in-Aid of the Ministry of Education, Science, Sports and Culture of Japan.     

Imperfect and Nonideal Clutters: A Common Approach

We prove three theorems. First, Lovászs theorem about minimal imperfect clutters, including also Padbergs corollaries. Second, Lehmans result on minimal nonideal clutters. Third, a common generalization of these two. The endeavor of working out a common denominator for Lovászs and Lehmans theorems leads, besides the common generalization, to a better understanding and simple polyhedral proofs of both.* Visiting of the French Ministry of Research and Technology, laboratoire LEIBNIZ, Grenoble, November 1995—April 1996.     

Online scheduling with reassignment

This paper studies online scheduling problems with reassignment on two identical machines. We can reassign some jobs under certain rules after all the jobs have been assigned. Three different versions are studied and optimal algorithms are proposed.     

THE FFD ALGORITHM FOR THE BIN PACKING PROBLEM WITH KERNEL ITEMS

The FFD algorithm is one of the most famous algorithms for the classical bin packing problem. In this paper,some versions of the FFD algorithm are considered in several bin packing problems. Especially,two of them applied to the bin packing problem with kernel items are analyzed. Tight worst-case performance ratios are obtained.     

Series-parallel graphs are windy postman perfect

The windy postman problem is the NP-hard problem of finding the minimum cost of a tour traversing all edges of an undirected graph, where the cost of an edge depends on the direction of traversal. Given an undirected graph G, we consider the polyhedron O(G) induced by a linear programming relaxation of the windy postman problem. We say that G is windy postman perfect if O(G) is integral. There exists a polynomial-time algorithm, based on the ellipsoid method, to solve the windy postman problem for the class of windy postman perfect graphs. By considering a family of polyhedra related to O(G), we prove that series-parallel graphs are windy postman perfect, therefore solving a conjecture of Win.     

Optimal allocation of service rates in Jackson network of queues with total finite accommodating space

This paper deals with the solutions of problems of optimal allocation of service rates in Jackson network of queues with total finite accommodating space. The optimal service rates have been found by using geometric programming techniques.Numerical results have also been given in the text.     

Generalized convex relations with applications to optimization and models of economic dynamics

We examine a notion of generalized convex set-valued mapping, extending the notions of a convex relation and a convex process. Under general conditions, we establish duality results for composite set-valued mappings and for convex programming problems involving convex set-valued mappings. We also present applications to the study of economic dynamical systems, by obtaining the characteristics of optimal paths generated by convex processes, and to optimization problems of a certain class of positively homogeneous increasing functions.     

Theoretical and algorithmic results for a class of hierarchical fleet mix problems

In this paper a workforce model is studied from both a theoretical and an algorithmic point of view. In the considered hierarchical model workforce units can be substituted by higher qualified ones; external workforce can also be hired to cover low qualified jobs. An exact recursive solution algorithm is proposed to solve the problems and its efficiency is improved by means of cut conditions and discrete convexity properties. Finally, the results of a computational test are provided.     

Computing Minimal Forecast Horizons:An Integer Programming Approach

In this paper, we use integer programming (IP) to compute minimal forecast horizons for the classical dynamic lot-sizing problem (DLS). As a solution approach for computing forecast horizons, integer programming has been largely ignored by the research community. It is our belief that the modelling and structural advantages of the IP approach coupled with the recent significant developments in computational integer programming make for a strong case for its use in practice. We formulate some well-known sufficient conditions, and necessary and sufficient conditions (characterizations) for forecast horizons as feasibility/optimality questions in 0–1 mixed integer programs. An extensive computational study establishes the effectiveness of the proposed approach.     

Network Design Via Iterative Rounding Of Setpair Relaxations

A typical problem in network design is to find a minimum-cost sub-network H of a given network G such that H satisfies some prespecified connectivity requirements. Our focus is on approximation algorithms for designing networks that satisfy vertex connectivity requirements. Our main tool is a linear programming relaxation of the following setpair formulation due to Frank and Jordan: a setpair consists of two subsets of vertices (of the given network G); each setpair has an integer requirement, and the goal is to find a minimum-cost subset of the edges of G sucht hat each setpair is covered by at least as many edges as its requirement. We introduce the notion of skew bisupermodular functions and use it to prove that the basic solutions of the linear program are characterized by “non-crossing families” of setpairs. This allows us to apply Jain’s iterative rounding method to find approximately optimal integer solutions. We give two applications. (1) In the k-vertex connectivity problem we are given a (directed or undirected) graph G=(V,E) with non-negative edge costs, and the task is to find a minimum-cost spanning subgraph H such that H is k-vertex connected. Let n=|V|, and let ε<1 be a positive number such that k≤(1−ε)n. We give an -approximation algorithm for both problems (directed or undirected), improving on the previous best approximation guarantees for k in the range . (2)We give a 2-approximation algorithm for the element connectivity problem, matching the previous best approximation guarantee due to Fleischer, Jain and Williamson. * Supported in part by NSERC researchgran t OGP0138432. † Supported in part by NSF Career Award CCR-9875024.     

Combinatorial optimization problems in wireless switch design

The purpose of this paper is to illustrate the diversity of combinatorial problems encountered in the design of wireless switching systems. This is done via a representative selection of examples of real problems along with their associated solution methods. It should be emphasized that all the solution methods presented in this paper are successfully operating in the field at the time of writing. To the memory of my beloved father, French Navy Admiral Christian Sirdey, whose life was cut short by cancer on November the 13th, 2006.