Two-edge connected subgraphs with bounded rings: Polyhedral results and Branch-and-Cut

We consider the network design problem which consists in determining at minimum cost a 2-edge connected network such that the shortest cycle (a “ring”) to which each edge belongs, does not exceed a given length K. We identify a class of inequalities, called cycle inequalities, valid for the problem and show that these inequalities together with the so-called cut inequalities yield an integer programming formulation of the problem in the space of the natural design variables. We then study the polytope associated with that problem and describe further classes of valid inequalities. We give necessary and sufficient conditions for these inequalities to be facet defining. We study the separation problem associated with these inequalities. In particular, we show that the cycle inequalities can be separated in polynomial time when K≤4. We develop a Branch-and-Cut algorithm based on these results and present extensive computational results.     

Relationships Among Flag <Emphasis Type="Italic">f</Emphasis>-Vector Inequalities for Polytopes

We examine linear inequalities satisfied by the flag $f$-vectors of polytopes. One source of these inequalities is the toric $g$-vector; convolutions of its entries are non-negative for rational polytopes. We prove a conjecture of Meisinger about a redundancy in these inequalities. Another source of inequalities is the {\bf cd}-index; among all $d$-polytopes, each {\bf cd}-index coefficient is minimized on the $d$-simplex. We show that not all of the {\bf cd}-index inequalities are implied by the toric $g$-vector inequalities, and that not all of the toric $g$-vector inequalities are implied by the {\bf cd}-index inequalities. Finally, we show that some inequalities from convolutions of {\bf cd}-index coefficients are implied by other {\bf cd}-index inequalities.     

Mixing mixed-integer inequalities

Mixed-integer rounding (MIR) inequalities play a central role in the development of strong cutting planes for mixed-integer programs. In this paper, we investigate how known MIR inequalities can be combined in order to generate new strong valid inequalities.?Given a mixed-integer region S and a collection of valid “base” mixed-integer inequalities, we develop a procedure for generating new valid inequalities for S. The starting point of our procedure is to consider the MIR inequalities related with the base inequalities. For any subset of these MIR inequalities, we generate two new inequalities by combining or “mixing” them. We show that the new inequalities are strong in the sense that they fully describe the convex hull of a special mixed-integer region associated with the base inequalities.?We discuss how the mixing procedure can be used to obtain new classes of strong valid inequalities for various mixed-integer programming problems. In particular, we present examples for production planning, capacitated facility location, capacitated network design, and multiple knapsack problems. We also present preliminary computational results using the mixing procedure to tighten the formulation of some difficult integer programs. Finally we study some extensions of this mixing procedure. Received: April 1998 / Accepted: January 2001?Published online April 12, 2001     

Generating Convex Polynomial Inequalities for Mixed 0–1 Programs

We develop a method for generating valid convex quadratic inequalities for mixed0–1 convex programs. We also show how these inequalities can be generated in the linear case by defining cut generation problems using a projection cone. The basic results for quadratic inequalities are extended to generate convex polynomial inequalities.     

A recursive procedure to generate all cuts for 0–1 mixed integer programs

We study several ways of obtaining valid inequalities for mixed integer programs. We show how inequalities obtained from a disjunctive argument can be represented by superadditive functions and we show how the superadditive inequalities relate to Gomory's mixed integer cuts. We also show how all valid inequalities for mixed 0–1 programs can be generated recursively from a simple subclass of the disjunctive inequalities.The research of this author was supported by NSF Contract No. ECS-8540898.     

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.     

Is an Orlicz–Poincaré inequality an open ended condition,and what does that mean?

In [16], Keith and Zhong prove that spaces admitting Poincaré inequalities also admit a priori stronger Poincaré inequalities. We use their technique, with slight adjustments, to obtain a similar result in the case of Orlicz–Poincaré inequalities. We give examples in the plane that show all hypotheses are required.     

The correlation bell inequalities

We consider the Bell and Bell-Clauser-Horne-Shimony-Holt inequalities for two-particle spin states. It is known that these inequalities are violated in experimental verification. We show that this can be explained because these inequalities are proved for correlation functions of random variables that are totally unrelated to one another, while the verification is done using correlation functions in which random variables refer to a pair of particles forming a two-particle state. In the case of entangled states, these random functions are dependent, and their correlation coefficient is nonzero. We give inequalities that explicitly involve this correlation coefficient. For factorable and separable states, these inequalities coincide with the standard Bell and Bell-Clauser-Horne-Shimony-Holt inequalities. __________ Translated from Teoreticheskaya i Matematicheskaya Fizika, Vol. 158, No. 2, pp. 234–249, February, 2009.     

On mixing sets arising in chance-constrained programming

The mixing set with a knapsack constraint arises in deterministic equivalent of chance-constrained programming problems with finite discrete distributions. We first consider the case that the chance-constrained program has equal probabilities for each scenario. We study the resulting mixing set with a cardinality constraint and propose facet-defining inequalities that subsume known explicit inequalities for this set. We extend these inequalities to obtain valid inequalities for the mixing set with a knapsack constraint. In addition, we propose a compact extended reformulation (with polynomial number of variables and constraints) that characterizes a linear programming equivalent of a single chance constraint with equal scenario probabilities. We introduce a blending procedure to find valid inequalities for intersection of multiple mixing sets. We propose a polynomial-size extended formulation for the intersection of multiple mixing sets with a knapsack constraint that is stronger than the original mixing formulation. We also give a compact extended linear program for the intersection of multiple mixing sets and a cardinality constraint for a special case. We illustrate the effectiveness of the proposed inequalities in our computational experiments with probabilistic lot-sizing problems.     

Correlation inequalities for statistical models of lattice gas

We consider models of statistical mechanics of the type of lattice gas with attractive interaction of general kind. We propose a method for obtaining inequalities that connect multipoint correlation functions of different order. This method allows one, on the one hand, to strengthen similar inequalities, which can be obtained within the framework of the FKG method, and on the other hand, to obtain new inequalities. We introduce the notion of duality for models of lattice gas. We show that if, under the transformation p ⇒ 1 - p, the correlation inequalities for a model with attraction turn into the corresponding inequalities that are also satisfied, then the correlation functions of the dual model also satisfy the latter inequalities. Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 50, No. 6, pp. 765–773, June, 1998.     

On the facets of the mixed–integer knapsack polyhedron

We study the mixed–integer knapsack polyhedron, that is, the convex hull of the mixed–integer set defined by an arbitrary linear inequality and the bounds on the variables. We describe facet–defining inequalities of this polyhedron that can be obtained through sequential lifting of inequalities containing a single integer variable. These inequalities strengthen and/or generalize known inequalities for several special cases. We report computational results on using the inequalities as cutting planes for mixed–integer programming.Supported, in part, by NSF grants DMII–0070127 and DMII–0218265.Mathematics Subject Classification (2000): 90C10, 90C11, 90C57     

Benders,metric and cutset inequalities for multicommodity capacitated network design

Solving multicommodity capacitated network design problems is a hard task that requires the use of several strategies like relaxing some constraints and strengthening the model with valid inequalities. In this paper, we compare three sets of inequalities that have been widely used in this context: Benders, metric and cutset inequalities. We show that Benders inequalities associated to extreme rays are metric inequalities. We also show how to strengthen Benders inequalities associated to non-extreme rays to obtain metric inequalities. We show that cutset inequalities are Benders inequalities, but not necessarily metric inequalities. We give a necessary and sufficient condition for a cutset inequality to be a metric inequality. Computational experiments show the effectiveness of strengthening Benders and cutset inequalities to obtain metric inequalities.     

Fractional Sobolev-type inequalities

Here we present univariate Sobolev-type fractional inequalities involving fractional derivatives of Canavati, Riemann–Liouville and Caputo types. The results are general L _p inequalities forward and converse on a closed interval. We give an application to a fractional ODE. We present also the mean Sobolev-type fractional inequalities.     

从积分几何的观点看几何不等式——纪念李国平院士吴新谋教授诞辰100周年

该文先介绍一些中国数学家在几何不等式方面的工作.作者用积分几何中著名的Poincarè公式及Blaschke公式估计一随机凸域包含另一域的包含测度, 得到了经典的等周不等式和Bonnesen -型不等式.还得到了一些诸如对称混合等周不等式、Minkowski -型和Bonnesen -型对称混合等似不等式在内的一些新的几何不等式.最后还研究了Gage -型等周不等式以及Ros -型等周不等式.     

Dimensional variance inequalities of Brascamp–Lieb type and a local approach to dimensional Prékopaʼs theorem

We give a new approach, inspired by Hörmander?s L²$L^2$-method, to weighted variance inequalities which extend results obtained by Bobkov and Ledoux. It provides in particular a local proof of the dimensional functional forms of the Brunn–Minkowski inequalities. We also present several applications of these variance inequalities, including reverse Hölder inequalities for convex functions, weighted Brascamp–Lieb inequalities and sharp weighted Poincaré inequalities for generalized Cauchy measures.     

Sharp maximal inequalities for stochastic integrals in which the integrator is a submartingale

We obtain sharp maximal inequalities for strong subordinates of real-valued submartingales. Analogous inequalities also hold for stochastic integrals in which the integrator is a submartingale. The impossibility of general moment inequalities is also demonstrated.

     

Functional inequalities for transient birth-death processes and their applications

We give a new diagram about uniform decay, empty essential spectrum and various functional inequalities, including Poincaré inequalities, super- and weak-Poincaré inequalities, for transient birth-death processes. This diagram is completely opposite to that in ergodic situation, and substantially points out the difference between transient birth-death processes and recurrent ones. The criterion for the empty essential spectrum is achieved. Some matching sufficient and necessary conditions for weak-Poincaré inequalities and super-Poincaré inequalities are also presented.     

Lifting inequalities for polytopes

We present a method of lifting linear inequalities for the flag f-vector of polytopes to higher dimensions. Known inequalities that can be lifted using this technique are the non-negativity of the toric g-vector and that the simplex minimizes the cd-index. We obtain new inequalities for six-dimensional polytopes. In the last section we present the currently best known inequalities for dimensions 5 through 8.     

On Hanner type inequalities with a weight for Banach spaces

We shall present several Hanner type inequalities with a weight constant and characterize 2-uniformly smooth and 2-uniformly convex Banach spaces with these inequalities. p-Uniformly smooth and q-uniformly convex Banach spaces will be also characterized with another Hanner type inequalities with a weight in the other side term. The best value of the weight in these inequalities will be determined for Lp spaces. Also we shall present a duality theorem between these inequalities in a generalized form.