Convex Normalizations in Lift-and-Project Methods for 0–1 Programming

Branch-and-Cut algorithms for general 0–1 mixed integer programs can be successfully implemented by using Lift-and-Project (L&P) methods to generate cuts. L&P cuts are drawn from a cone of valid inequalities that is unbounded and, thus, needs to be truncated, or normalized. We consider general normalizations defined by arbitrary closed convex sets and derive dual problems for generating L&P cuts. This unified theoretical framework generalizes and covers a wide group of already known normalizations. We also give conditions for proving finite convergence of the cutting plane procedure that results from using such general L&P cuts.     

Efficient Regular Polygon Dissections

We study the minimum number g(m,n) (respectively, p(m,n)) of pieces needed to dissect a regular m-gon into a regular n-gon of the same area using glass-cuts (respectively, polygonal cuts). First we study regular polygon-square dissections and show that n/2 -2 g(4,n) (n/2) + o(n) and n/4 g(n,4) (n/2) + o(n) hold for sufficiently large n. We also consider polygonal cuts, i.e., the minimum number p(4,n) of pieces needed to dissect a square into a regular n-gon of the same area using polygonal cuts and show that n/4 p(4,n) (n/2) + o(n) holds for sufficiently large n. We also consider regular polygon-polygon dissections and obtain similar bounds for g(m,n) and p(m,n).     

Cut search methods in integer programming

Cut search is a new approach for solving integer programs based on extending edges of a cone to probe the solution space for sets of hyperplanes that are proxies for solution points in the space. Once all proxy hyperplanes associated with a given point have been intersected by at least one of the extended edges, this point is included in a set of points to be examined for feasibility (algorithmically or by inspection). Thereupon, all edges of the cone are extended an additional distance to create a cut by passing a hyperplane through the endpoints of these extended edges.The flexibility of the cut search procedure permits a variety of strategies for exploring and cutting into the solution space. One useful version arises by taking the proxy hyperplanes to be members of a positive or semipositive coordinate system. Relative to such a system the procedure can be organized to reduce the set of vectors to be examined for feasibility and also to generate deeper cuts at the end of the edge probe.     

A lifting procedure for the asymmetric traveling salesman polytope and a large new class of facets

Given any family of valid inequalities for the asymmetric traveling salesman polytopeP(G) defined on the complete digraphG, we show that all members of are facet defining if the primitive members of (usually a small subclass) are. Based on this result we then introduce a general procedure for identifying new classes of facet inducing inequalities forP(G) by lifting inequalities that are facet inducing forP(G), whereG is some induced subgraph ofG. Unlike traditional lifting, where the lifted coefficients are calculated one by one and their value depends on the lifting sequence, our lifting procedure replaces nodes ofG with cliques ofG and uses closed form expressions for calculating the coefficients of the new arcs, which are sequence-independent. We also introduce a new class of facet inducing inequalities, the class of SD (source-destination) inequalities, which subsumes as special cases most known families of facet defining inequalities.Research supported by Grant DDM-8901495 of the National Science Foundation and Contract N00014-85-K-0198 of the U.S. Office of Naval Research.Research supported by M.U.R.S.T., Italy.     

Analytic Center Cutting-Plane Method with Deep Cuts for Semidefinite Feasibility Problems

An analytic center cutting-plane method with deep cuts for semidefinite feasibility problems is presented. Our objective in these problems is to find a point in a nonempty bounded convex set in the cone of symmetric positive-semidefinite matrices. The cutting plane method achieves this by the following iterative scheme. At each iteration, a query point that is an approximate analytic center of the current working set is chosen. We assume that there exists an oracle which either confirms that or returns a cut A S ^m {YS ^m : AY AY - } , where 0. If , an approximate analytic center of the new working set, defined by adding the new cut to the preceding working set, is then computed via a primal Newton procedure. Assuming that contains a ball with radius > 0, the algorithm obtains eventually a point in , with a worst-case complexity of O ^*(m ³/²) on the total number of cuts generated.     

Strong formulations for mixed integer programming: A survey

We attempt to motivate and survey recent research on the use of strong valid inequalities and reformulation to solve mixed integer programming problems.     

A Polynomial Cutting Surfaces Algorithm for the Convex Feasibility Problem Defined by Self-Concordant Inequalities

Consider a nonempty convex set in ^m which is defined by a finite number of smooth convex inequalities and which admits a self-concordant logarithmic barrier. We study the analytic center based column generation algorithm for the problem of finding a feasible point in this set. At each iteration the algorithm computes an approximate analytic center of the set defined by the inequalities generated in the previous iterations. If this approximate analytic center is a solution, then the algorithm terminates; otherwise either an existing inequality is shifted or a new inequality is added into the system. As the number of iterations increases, the set defined by the generated inequalities shrinks and the algorithm eventually finds a solution of the problem. The algorithm can be thought of as an extension of the classical cutting plane method. The difference is that we use analytic centers and convex cuts instead of arbitrary infeasible points and linear cuts. In contrast to the cutting plane method, the algorithm has a polynomial worst case complexity of O(Nlog 1/) on the total number of cuts to be used, where N is the number of convex inequalities in the original problem and is the maximum common slack of the original inequality system.     

Cone Adaptation Strategies for a Finite and Exact Cutting Plane Algorithm for Concave Minimization

In this paper we are concerned with pure cutting plane algorithms for concave minimization. One of the most common types of cutting planes for performing the cutting operation in such algorithm is the concavity cut. However, it is still unknown whether the finite convergence of a cutting plane algorithm can be enforced by the concavity cut itself or not. Furthermore, computational experiments have shown that concavity cuts tend to become shallower with increasing iteration. To overcome these problems we recently proposed a procedure, called cone adaptation, which deepens concavity cuts in such a way that the resulting cuts have at least a certain depth with 0, where is independent of the respective iteration, which enforces the finite convergence of the cutting plane algorithm. However, a crucial element of our proof that these cuts have a depth of at least was that we had to confine ourselves to -global optimal solutions, where is a prescribed strictly positive constant. In this paper we examine possible ways to ensure the finite convergence of a pure cutting plane algorithm for the case where = 0.     

Some Landau's type inequalities for infinitesimal generators

Summary Lett T(t) be a strongly continuous contraction semigroup on a complex Banach space and letA be its infinitesimal generator. We prove that, forx D(A ³), the following inequalities hold true: Ax³ 243/8 x²A ³ x, A ² x 24 xA ³ x². Ift T(t) is a contraction group (resp. cosine function) we get the analogous but better inequalities with constants 9/8 and 3 (resp. 81/40 and 72/25) instead of 243/8 and 24. We consider also uniformly bounded semigroups, groups and cosine functions.     

Finite checkability for integer rounding properties in combinatorial programming problems

LetA be a nonnegative integral matrix with no zero columns. Theinteger round-up property holds forA if for each nonnegative integral vectorw, the solution value to the integer programming problem min{1 y: yA w, y 0, y integer} is obtained by rounding up to the nearest integer the solution value to the corresponding linear programming problem min{1 y: yA w, y 0}. Theinteger round-down property is similarly defined for a nonnegative integral matrixB with no zero rows by considering max{1 y: yB w, y 0, y integer} and its linear programming correspondent. It is shown that the integer round-up and round-down properties can be checked through a finite process. The method of proof motivates a new and elementary proof of Fulkerson's Pluperfect Graph Theorem.Research partially supported by NSF Grants ENG76-09936 and ENG78-09882.     

The Two-Period Travelling Salesman Problem Applied to Milk Collection in Ireland

We describe a new extension to the Symmetric Travelling Salesman Problem (STSP) in which some nodes are visited inboth of 2 periods and the remaining nodes are visited in either 1 ofthe periods. A number of possible Integer Programming Formulationsare given. Valid cutting plane inequalities are defined for thisproblem which result in an, otherwise prohibitively difficult, modelof 42 nodes becoming easily solvable by a combination of cuts andBranch-and-Bound. Some of the cuts are entered in a pool andonly used when it is automatically verified that they are violated.Other constraints which are generalisations of the subtour and combinequalities for the single period STSP, are identified manuallywhen needed. Full computational details of solution process aregiven.     

Gaussian Version of a Theorem of Milman and Schechtman

Using Gordon's inequalities, we give a short proof of the existence of an embedding T:l2k to ln such that ||T||||T-1|| c k/ln(1+n/k). In the same way, we give a new proof of a theorem of Milman and Schechtman (1995).     

Arithmetic Properties of Summands of Partitions

Let d d, d2 2. We prove that for almost all partitions of an integer the parts are well distributed in residue classes mod d. The limitations of the uniformity of this distribution are also studied.     

Facets for the cut cone I

We study facets of the cut coneC _n , i.e., the cone of dimension 1/2n(n – 1) generated by the cuts of the complete graph onn vertices. Actually, the study of the facets of the cut cone is equivalent in some sense to the study of the facets of the cut polytope. We present several operations on facets and, in particular, a lifting procedure for constructing facets ofC _n+1 from given facets of the lower dimensional coneC _n . After reviewing hypermetric valid inequalities, we describe the new class of cycle inequalities and prove the facet property for several subclasses. The new class of parachute facets is developed and other known facets and valid inequalities are presented.     

Chapter 1 Introduction: Extensions and new developments in DEA

The extensions, new developments and new interpretations for DEA covered in this paper include: (1) new measures of efficiency, (2) new models and (3) new ways of implementing established models with new results and interpretations presented that include treatments of congestion, returns-to-scale and mix and technical inefficiencies and measures of efficiency that can be used to reflect all pertinent properties. Previously used models, such as those used to identify allocative inefficiencies, are extended by means of assurance region approaches which are less demanding in their information requirements and underlying assumptions. New opportunities for research are identified in each section of this chapter. Sources of further developments and possible sources for further help are also suggested with references supplied to other papers that appear in this volume and which are summarily described in this introductory chapter.     

Mittelwert der Eulerschen φ-Funktion und des Quadrates der Dirichletschen Teilerfunktion in algebraischen Zahlkörpern

LetK be an algebraic number field, and for every integer K let () andd(), respectively, denote the number of relatively prime residue classes and the number of divisors of the principal ideal (). Asymptotic equalities are proved for the sums () and d ²(), where runs through certain finite sets of integers ofK.     

Probability and expectation inequalities

Summary This paper introduces a mathematical framework within which a wide variety of known and new inequalities can be viewed from a common perspective. Probability and expectation inequalities of the following types are considered: (a)P(ZA) P(ZA) for some class of setsA, (b)k(Z)k(Z) for some class of functionsk, and (c)l(Z)k(Z) for some class of pairs of functionsl andk. It is shown, sometimes using explicit constructions ofZ andZ, that, in several cases, (a) (b) (c); included here are cases of normal and elliptically contoured distributions. A case where (a) (b) (c) is studied and is expressed in terms ofn monotone functions for (some of) which integral representations are obtained. Also, necessary and sufficient conditions for (c) are given.Research supported by the Air Force Office of Scientific Research under Grants AFOSR-75-2796 and AFOSR-80-0080Research supported by the National Science Foundation under Grants MCS78-01240 and MCS81-00748     

The ellipsoid algorithm using parallel cuts

We present an ellipsoid algorithm using parallel cuts which is robust and conceptually simple. If the ratio fo the distance between the parallel cuts under consideration and the corresponding radius of the current ellipsoid is less than or equal to some constant, it is called the canonical case. Applying our algorithm to this case the volume of the next ellipsoid decreases by a factor which is, at worst, exp For the noncanonical case, we first add an extra constraint to make it a canonical case in a higher-dimensional space, then apply our algorithm to this canonical case, and finally reduce it back to the original space. Some interesting variants are also presented to show the flexibility of our basic algorithm.     

Asymptotics of the Discrete Spectrum of the Three-Particle Schrödinger Difference Operator on a Lattice

We consider the Hamiltonian H (K) of a system consisting of three bosons that interact through attractive pair contact potentials on a three-dimensional integer lattice. We obtain an asymptotic value for the number N(K,z) of eigenvalues of the operator H₀(K) lying below z0 with respect to the total quasimomentum K0 and the spectral parameter z–0.     

Jensen inequalities for functions with higher monotonicities

Summary We investigate generalizations of the classical Jensen and Chebyshev inequalities. On one hand, we restrict the class of functions and on the other we enlarge the class of measures which are allowed. As an example, consider the inequality (J)(f(x) d) A (f(x) d, d d = 1. Iff is an arbitrary nonnegativeL _x function, this holds if 0, is convex andA = 1. Iff is monotone the measure need not be positive for (J) to hold for all convex withA = 1. If has higher monotonicity, e.g., is also convex, then we get a version of (J) withA < 1 and measures that need not be positive.