Deriving compact extended formulations via LP-based separation techniques

The best formulations for some combinatorial optimization problems are integer linear programming models with an exponential number of rows and/or columns, which are solved incrementally by generating missing rows and columns only when needed. As an alternative to row generation, some exponential formulations can be rewritten in a compact extended form, which have only a polynomial number of constraints and a polynomial, although larger, number of variables. As an alternative to column generation, there are compact extended formulations for the dual problems, which lead to compact equivalent primal formulations, again with only a polynomial number of constraints and variables. In this this paper we introduce a tool to derive compact extended formulations and survey many combinatorial optimization problems for which it can be applied. The tool is based on the possibility of formulating the separation procedure by an LP model. It can be seen as one further method to generate compact extended formulations besides other tools of geometric and combinatorial nature present in the literature.     

Primal separation for 0/1 polytopes

 The 0/1 primal separation problem is: Given an extreme point xˉ of a 0/1 polytope P and some point x ^*, find an inequality which is tight at xˉ, violated by x ^* and valid for P or assert that no such inequality exists. It is known that this separation variant can be reduced to the standard separation problem for P. We show that 0/1 optimization and 0/1 primal separation are polynomial time equivalent. This implies that the problems 0/1 optimization, 0/1 standard separation, 0/1 augmentation, and 0/1 primal separation are polynomial time equivalent. Then we provide polynomial time primal separation procedures for matching, stable set, maximum cut, and maximum bipartite graph problems, giving evidence that these algorithms are conceptually simpler and easier to implement than their corresponding counterparts for standard separation. In particular, for perfect matching we present an algorithm for primal separation that rests only on simple max-flow computations. In contrast, the known standard separation method relies on an explicit minimum odd cut algorithm. Consequently, we obtain a very simple proof that a maximum weight perfect matching of a graph can be computed in polynomial time. Received: August 20, 2001 / Accepted: April 2002 Published online: December 9, 2002 RID="⋆" ID="⋆" This research was developed while the author was on leave at the Istituto di Analisi dei Sistemi ed Informatica, Viale Manzoni 30, 00185 Roma, supported by the project TMR-DONET nr. ERB FMRX-CT98-0202 of the European Union. Mathematics Subject Classification (2000): 90C10, 90C60, 90C57     

The inverse optimal value problem

This paper considers the following inverse optimization problem: given a linear program, a desired optimal objective value, and a set of feasible cost vectors, determine a cost vector such that the corresponding optimal objective value of the linear program is closest to the desired value. The above problem, referred here as the inverse optimal value problem, is significantly different from standard inverse optimization problems that involve determining a cost vector for a linear program such that a pre-specified solution vector is optimal. In this paper, we show that the inverse optimal value problem is NP-hard in general. We identify conditions under which the problem reduces to a concave maximization or a concave minimization problem. We provide sufficient conditions under which the associated concave minimization problem and, correspondingly, the inverse optimal value problem is polynomially solvable. For the case when the set of feasible cost vectors is polyhedral, we describe an algorithm for the inverse optimal value problem based on solving linear and bilinear programming problems. Some preliminary computational experience is reported.Mathematics Subject Classification (1999):49N45, 90C05, 90C25, 90C26, 90C31, 90C60Acknowledgement This research has been supported in part by the National Science Foundation under CAREER Award DMII-0133943. The authors thank two anonymous reviewers for valuable comments.     

An accelerated central cutting plane algorithm for linear semi-infinite programming

An algorithm for linear semi-infinite programming is presented which accelerates the convergence of the central cutting plane algorithm first proposed in [4]. Compared with other algorithms, the algorithm in [4] has the advantage of being applicable under mild conditions and of providing feasible solutions. However its convergence has been shown to be rather slow in practical instances. The algorithm proposed in this paper introduces a simple acceleration scheme which gives faster convergence, as confirmed by several examples, as well as an interval of prefixed length containing the optimum value. It is also shown that the algorithm provides a solution of the dual problem and that it can be used for convex semi-infinite programming too.Mathematics Subject Classification (1991): 90C05, 90C34, 65K05, 90C51Acknowledgments. The author whishes to thank the three anonymous referees and an associate editor for many useful comments and valuable suggestions.     

The asymmetric travelling salesman problem and a reformulation of the Miller–Tucker–Zemlin constraints

In this paper we compare the linear programming (LP) relaxations of several old and new formulations for the asymmetric travelling salesman problem (ATSP). The main result of this paper is the derivation of a compact formulation whose LP relaxation is characterized by a set of circuit inequalities given by Grotschel and Padberg (In: Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A., Shmoys, D.B. (Eds.), The Travelling Salesman Problem: A Guided Tour of Combinatorial Optimization. Wiley, New York, 1985). The new compact model is an improved and disaggregated version of a well-known model for the ATSP based on the subtour elimination constraints (Miller et al., Journal of ACM 7 (1960) 326–329). The circuit inequalities are weaker than the subtour elimination constraints given by Dantzig et al. However, each one of these circuit inequalities can be lifted into several different facet defining inequalities which are not dominated by the subtour elimination inequalities. We show that some of the inequalities involved in the previously mentioned compact formulation can be lifted in such a way that, by projection, we obtain a small subset of the so-called D_k^← and D_k^→ inequalities. This shows that the LP relaxation of our strongest model is not dominated by the LP relaxation of the model presented by Dantzig et al. (Operations Research 2 (1954) 393–410). The new models motivate a new classification of formulations for the ATSP.     

LP formulations of the shortest path tree problem

Based on a pair of primal-dual LP formulations of the shortest path tree problem, the first algorithmic approach to reoptimizing the shortest paths subject to changes in the edge weights was proposed by S. Pallottino and M.G. Scutellá in 2003. We shall here focus solely on their introductory sections, propose some simplifications of the models considered, and finally relate the resulting models to the presentation of single-source shortest path problems in textbooks treating this subject with but limited or no reference to LP.Received: April 2004, Revised: August 2004, MSC classification: 90C05, 90C35, 90B10 Dedicated to the memory of Stefano Pallottino     

Duality gaps in nonconvex stochastic optimization

We consider multistage stochastic optimization models containing nonconvex constraints, e.g., due to logical or integrality requirements. We study three variants of Lagrangian relaxations and of the corresponding decomposition schemes, namely, scenario, nodal and geographical decomposition. Based on convex equivalents for the Lagrangian duals, we compare the duality gaps for these decomposition schemes. The first main result states that scenario decomposition provides a smaller or equal duality gap than nodal decomposition. The second group of results concerns large stochastic optimization models with loosely coupled components. The results provide conditions implying relations between the duality gaps of geographical decomposition and the duality gaps for scenario and nodal decomposition, respectively.Mathematics Subject Classification (1991): 90C15Acknowledgments. This work was supported by the Priority Programme Online Optimization of Large Scale Systems of the Deutsche Forschungsgemeinschaft. The authors wish to thank Andrzej Ruszczyski (Rutgers University) for helpful discussions.     

Solving semidefinite-quadratic-linear programs using SDPT3

 This paper discusses computational experiments with linear optimization problems involving semidefinite, quadratic, and linear cone constraints (SQLPs). Many test problems of this type are solved using a new release of SDPT3, a Matlab implementation of infeasible primal-dual path-following algorithms. The software developed by the authors uses Mehrotra-type predictor-corrector variants of interior-point methods and two types of search directions: the HKM and NT directions. A discussion of implementation details is provided and computational results on problems from the SDPLIB and DIMACS Challenge collections are reported. Received: March 19, 2001 / Accepted: January 18, 2002 Published online: October 9, 2002 Mathematics Subject Classification (2000): 90C05, 90C22     

On semi-invariant probability measures on semigroups

Summary Let a regular Borel measure m on a locally compact semigroup S be upper semi-invariant i.e., m(C x)m(C) and m(x C)m(C) for every compact C and x in S. It is shown: (i) Every subsemigroup of S of positive measure contains an idempotent. (ii) S admits an upper semi-invariant probability measure iff S has a kernel K which is a compact group.We should like to thank the referee for pointing out certain redundancies in the theorems. Also we thank Dr. Tze-Chien Sun for some helpful observations.     

On optimizing over lift-and-project closures

The strengthened lift-and-project closure of a mixed integer linear program is the polyhedron obtained by intersecting all strengthened lift-and-project cuts obtained from its initial formulation, or equivalently all mixed integer Gomory cuts read from all tableaux corresponding to feasible and infeasible bases of the LP relaxation. In this paper, we present an algorithm for approximately optimizing over the strengthened lift-and-project closure. The originality of our method is that it relies on a cut generation linear programming problem which is obtained from the original LP relaxation by only modifying the bounds on the variables and constraints. This separation LP can also be seen as dual to the cut generation LP used in disjunctive programming procedures with a particular normalization. We study properties of this separation LP, and discuss how to use it to approximately optimize over the strengthened lift-and-project closure. Finally, we present computational experiments and comparisons with recent related works.     

Karush-Kuhn-Tucker systems: regularity conditions,error bounds and a class of Newton-type methods

 We consider optimality systems of Karush-Kuhn-Tucker (KKT) type, which arise, for example, as primal-dual conditions characterizing solutions of optimization problems or variational inequalities. In particular, we discuss error bounds and Newton-type methods for such systems. An exhaustive comparison of various regularity conditions which arise in this context is given. We obtain a new error bound under an assumption which we show to be strictly weaker than assumptions previously used for KKT systems, such as quasi-regularity or semistability (equivalently, the R ₀-property). Error bounds are useful, among other things, for identifying active constraints and developing efficient local algorithms. We propose a family of local Newton-type algorithms. This family contains some known active-set Newton methods, as well as some new methods. Regularity conditions required for local superlinear convergence compare favorably with convergence conditions of nonsmooth Newton methods and sequential quadratic programming methods. Received: December 10, 2001 / Accepted: July 28, 2002 Published online: February 14, 2003 Key words. KKT system – regularity – error bound – active constraints – Newton method Mathematics Subject Classification (1991): 90C30, 65K05     

Homogenization of integrals with pointwise gradient constraints via the periodic unfolding method

Abstract The pointwise gradient constrained homogenization process, for Neumann and Dirichlet type problems, is analyzed by means of the periodic unfolding method recently introduced in [21]. Classically, the proof of the homogenization formula in presence of pointwise gradient constraints relies on elaborated measure theoretic arguments. The one proposed here is elementary: it is based on weak convergence arguments in L^p spaces, coupled with suitable regularization techniques. Keywords: Homogenization, Gradient constrained problems, Periodic unfolding method Mathematics Subject Classification (2000): 49J45, 35B27, 74Q05     

Persistency of linear programming relaxations for the stable set problem

The Nemhauser–Trotter theorem states that the standard linear programming (LP) formulation for the stable set problem has a remarkable property, also known as (weak) persistency: for every optimal LP solution that assigns integer values to some variables, there exists an optimal integer solution in which these variables retain the same values. While the standard LP is defined by only non-negativity and edge constraints, a variety of other LP formulations have been studied and one may wonder whether any of them has this property as well. We show that any other formulation that satisfies mild conditions cannot have the persistency property on all graphs, unless it is always equal to the stable set polytope.

     

Ultrapowers as sheaves on a category of ultrafilters

In the paper we investigate the topos of sheaves on a category of ultrafilters. The category is described with the help of the Rudin-Keisler ordering of ultrafilters. It is shown that the topos is Boolean and two-valued and that the axiom of choice does not hold in it. We prove that the internal logic in the topos does not coincide with that in any of the ultrapowers. We also show that internal set theory, an axiomatic nonstandard set theory, can be modeled in the topos.Mathematics Subject Classification (2000): Primary 03G30, 03C20, Secondary 03E05, 03E70, 03H05The author would like to thank the Mittag-Leffler Institute for partial suport.     

Greedy primal-dual algorithm for dynamic resource allocation in complex networks

In Stolyar (Queueing Systems 50 (2005) 401–457) a dynamic control strategy, called greedy primal-dual (GPD) algorithm, was introduced for the problem of maximizing queueing network utility subject to stability of the queues, and was proved to be (asymptotically) optimal. (The network utility is a concave function of the average rates at which the network generates several “commodities.”) Underlying the control problem of Stolyar (Queueing Systems 50 (2005) 401–457) is a convex optimization problem subject to a set of linear constraints. In this paper we introduce a generalized GPD algorithm, which applies to the network control problem with additional convex (possibly non-linear) constraints on the average commodity rates. The underlying optimization problem in this case is a convex problem subject to convex constraints. We prove asymptotic optimality of the generalized GPD algorithm. We illustrate key features and applications of the algorithm on simple examples. AMS Subject Classifications: 90B15 · 90C25 · 60K25 · 68M12     

A generalization of the Dual Ellentuck Theorem

 We prove versions of the Dual Ramsey Theorem and the Dual Ellentuck Theorem for families of partitions which are defined in terms of games. Received: 8 July 1999 Published online: 19 December 2002 RID="*" ID="*" The author wishes to thank the Swiss National Science Foundation for supporting him. The authors thank the referee for helpful comments. Mathematics Subject Classification (2000): 03E02, 05D10, 03E35 Key words or phrases: Dual Ramsey Theorem – Dual Ellentuck Theorem – Partitions – Games     

Modules lattice isomorphic to linearly compact modules

We study modules that are lattice isomorphic to linearly compact modules (in the discrete topology). In particular, we establish the equivalence of the following properties of a moduleM: 1)M satisfies the Grothendieck property AB5^* and all its submodules are Goldie finite-dimensional; 2)M is lattice isomorphic to a linearly compact module; 3)M is lattice antiisomorphic to a linearly compact module. We show that a linearly compact module cannot be determined in terms of the lattice of its submodules.Translated fromMatematicheskie Zametki, Vol. 59, No. 2, pp. 174–181, February, 1996.The author wishes to thank A. V. Mikhalev and A. A. Tuganbaev for valuable discussions and remarks.     

Subdifferentiability of the norm and the Banach-Stone theorem for real and complex JB*-triples

We study the points of strong subdifferentiability for the norm of a real JB*-triple. As a consequence we describe weakly compact real JB*-triples and rediscover the Banach-Stone Theorem for complex JB*-triples.Authors Partially supported by I+D MCYT projects no. BFM2002-01529 and BFM2002-01810, and Junta de Andalucía grant FQM 0199Mathematics Subject Classification (2000): 46B04, 46L05, 46L70Revised version: 2 May 2004Acknowledgements. The authors would like to thank A. Rodr{\i}guez Palacios for fruitful comments and discussions during the preparation of this paper and to the referee for his or her interesting suggestions.     

Upper bounds for revenue maximization in a satellite scheduling problem

This paper presents upper bounds for the Satellite Revenue Selection and Schedulingproblem (SRSS). A compact model of this generalized Prize Collecting Traveling Salesman Problem with Time Windows is defined and enriched with valid inequalities based on task interval reasoning. The non-concavity of the objective function to be maximized is also studied. Finally a Russian Dolls approach combines bounds on nested sub-problems. These first upper bounds for the SRSS problem are compared to best known solutions of the benchmark of the optimization challenge organized by the French OR society.Received: June 2003, Revised: January 2004, MSC classification: 90C90