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.     

Extended formulations for the A-cut problem

LetG=(V, E) be an undirected graph andA⊆V. We consider the problem of finding a minimum cost set of edges whose deletion separates every pair of nodes inA. We consider two extended formulations using both node and edge variables. An edge variable formulation has previously been considered for this problem (Chopra and Rao (1991), Cunningham (1991)). We show that the LP-relaxations of the extended formulations are stronger than the LP-relaxation of the edge variable formulation (even with an extra class of valid inequalities added). This is interesting because, while the LP-relaxations of the extended formulations can be solved in polynomial time, the LP-relaxation of the edge variable formulation cannot. We also give a class of valid inequalities for one of the extended formulations. Computational results using the extended formulations are performed.     

Ramsey theory and integrality gap for the independent set problem

We discuss the effectiveness of integer programming for solving large instances of the independent set problem. Typical LP formulations, even strengthened by clique inequalities, yield poor bounds for this problem. We show that a strong bound can be obtained by the use of the so-called rank inequalities, which generalize the clique inequalities. For some problems the clique inequalities imply the rank inequalities, and then a strong bound is guaranteed already by the simpler formulation.     

A note on capacity models for network design

In network design problems,capacity constraints are modeled in three different ways depending on the application: directed, bidirected and undirected. In the literature, polyhedral investigations for strengthening mixed-integer formulations are done separately for each model. In this note, we examine the relationship between these models to provide a unifying approach and show that one can indeed translate valid inequalities from one to the others.     

Polynomial size IP formulations of knapsack may require exponentially large coefficients

A desirable property of integer formulations is to consist of few inequalities having small coefficients. We show that these targets are conflicting by proving the existence of knapsack sets that need exponentially many inequalities or exponentially large coefficients in any integer formulation. Moreover, we show that there exist undirected graphs such that (in a natural model) every integer formulation of stable sets requires exponentially large coefficients if the number of non-trivial inequalities is bounded by a constant.     

The b-hull of an integer program

Given a linear integer program: max{cx:Ax=b, x≥0 and integer},A rational, it is known that it can be solved in theory for all values of c, either by testing a finite number of solutions for optimality, or by adding a finite number of valid inequalities, each generated from a superadditive function, and solving the resulting linear program.The main result of this paper is to show that (analogously) the integer program can be solved for all values of b, either by testing a finite number of solutions for feasibility and optimality, or by adding a finite number of valid inequalities, each generated from a superadditive function, and solving the resulting linear program.     

Self-adaptive methods for mixed quasi-variational inequalities

It is well known that the variational inequalities involving the nonlinear term φ are equivalent to the fixed-point problems and the resolvent equations. In this paper, we use these alternative equivalent formulations to suggest and analyze some new self-adaptive iterative methods for solving mixed quasi-variational inequalities. Our results can be viewed as significant extensions of the previously known results for mixed quasi-variational inequalities. An example is given to illustrate the efficiency of the proposed method.     

Strong valid inequalities for fluence map optimization problem under dose-volume restrictions

Fluence map optimization problems are commonly solved in intensity modulated radiation therapy (IMRT) planning. We show that, when subject to dose-volume restrictions, these problems are NP-hard and that the linear programming relaxation of their natural mixed integer programming formulation can be arbitrarily weak. We then derive strong valid inequalities for fluence map optimization problems under dose-volume restrictions using disjunctive programming theory and show that strengthening mixed integer programming formulations with these valid inequalities has significant computational benefits.     

Enhancing discretized formulations: the knapsack reformulation and the star reformulation

Discretized formulations have proved to be useful for modeling combinatorial optimizations. The main focus of this work is on how to strengthen the linear programming relaxation of a given discretized formulation. More precisely, we will study and strengthen subproblems that arise in these formulations. In one case we will focus on the so-called knapsack reformulation which is based on viewing these models as the intersection of two polyhedra, one of them being a specialized knapsack problem. We will show that strong inequalities used in previous works are a special case of inequalities implied by the knapsack formulation. In the second case we will analyze a star-like subproblem and will provide an extended formulation for this problem as well as a set of inequalities on the original space, implied by the inequalities of the extended formulation. We will use a generalization of the Degree Constrained Spanning Tree problem as a setting for this study. In the present work, besides contextualizing these enhancements in terms of discretized models presented in previous works, we also compare and combine together them, for the first time.     

The γ-connected assignment problem

Given a graph and costs of assigning to each vertex one of k different colors, we want to find a minimum cost assignment such that no color q induces a subgraph with more than a given number (γ_q) of connected components. This problem arose in the context of contiguity-constrained clustering, but also has a number of other possible applications. We show the problem to be NP-hard. Nevertheless, we derive a dynamic programming algorithm that proves the case where the underlying graph is a tree to be solvable in polynomial time. Next, we propose mixed-integer programming formulations for this problem that lead to branch-and-cut and branch-and-price algorithms. Finally, we introduce a new class of valid inequalities to obtain an enhanced branch-and-cut. Extensive computational experiments are reported.     

On fractional Poincaré inequalities

We show that fractional (p, p)-Poincaré inequalities and even fractional Sobolev-Poincaré inequalities hold for bounded John domains, and especially for bounded Lipschitz domains. We also prove sharp fractional (1,p)-Poincaré inequalities for s-John domains.     

A computational comparison of flow formulations for the capacitated location-routing problem

In this paper we present a computational comparison of four different flow formulations for the capacitated location-routing problem. We introduce three new flow formulations for the problem, namely a two-index two-commodity flow formulation, a three-index vehicle-flow formulation and a three-index two-commodity flow formulation. We also consider an existing two-index vehicle-flow formulation and extend it by considering new families of valid inequalities and separation algorithms. We introduce new branch-and-cut algorithms for each of the formulations and compare them on a wide number of instances. Our results show that compact formulations can produce tight gaps and solve many instances quickly, whereas three-index formulations scale better in terms of computing time.     

Checking solvability of systems of interval linear equations and inequalities via mixed integer programming

This paper deals with the problems of checking strong solvability and feasibility of linear interval equations, checking weak solvability of linear interval equations and inequalities, and finding control solutions of linear interval equations. These problems are known to be NP$\mathit{NP}$-hard. We use some recently developed characterizations in combination with classical arguments to show that these problems can be equivalently stated as optimization tasks and provide the corresponding linear mixed 0–1 programming formulations.     

Multiple machine continuous setup lotsizing with sequence-dependent setups

We address the short-term production planning and scheduling problem coming from the glass container industry. A furnace melts the glass that is distributed to a set of parallel molding machines. Both furnace and machine idleness are not allowed. The resulting multi-machine multi-item continuous setup lotsizing problem with a common resource has sequence-dependent setup times and costs. Production losses are penalized in the objective function since we deal with a capital intensive industry. We present two mixed integer programming formulations for this problem, which are reduced to a network flow type problem. The two formulations are improved by adding valid inequalities that lead to good lower bounds. We rely on a Lagrangian decomposition based heuristic for generating good feasible solutions. We report computational experiments for randomly generated instances and for real-life data on the aforementioned problem, as well as on a discrete lotsizing and scheduling version.     

The Degree Preserving Spanning Tree Problem: Valid Inequalities and Branch-and-cut method

Given a connected undirected graph G, the Degree Preserving Spanning Tree Problem (DPSTP) consists in finding a spanning tree T of G that maximizes the number of vertices that have the same degree in T and in G. In this paper, we introduce Integer Programming formulations, valid inequalities and a Branch-and-cut algorithm for the DPSTP. Reinforced with new valid inequalities, the upper bounds provided by the formulation behind our Branch-and-cut method dominate previous DPSTP bounds in the literature.     

Strengthened clique-family inequalities for the stable set polytope

The stable set polytope is a fundamental object in combinatorial optimization. Among the many valid inequalities that are known for it, the clique-family inequalities play an important role. Pêcher and Wagler showed that the clique-family inequalities can be strengthened under certain conditions. We show that they can be strengthened even further, using a surprisingly simple mixed-integer rounding argument.     

Norm inequalities in operator ideals

In this paper we introduce a new technique for proving norm inequalities in operator ideals with a unitarily invariant norm. Among the well-known inequalities which can be proved with this technique are the Löwner-Heinz inequality, inequalities relating various operator means and the Corach-Porta-Recht inequality. We prove two general inequalities and from them we derive several inequalities by specialization, many of them new. We also show how some inequalities, known to be valid for matrices or bounded operators, can be extended with this technique to normed ideals in C^∗-algebras, in particular to the noncommutative Lp-spaces of a semi-finite von Neumann algebra.