Note on Affine Gagliardo–Nirenberg Inequalities

This note proves sharp affine Gagliardo–Nirenberg inequalities which are stronger than all known sharp Euclidean Gagliardo–Nirenberg inequalities and imply the affine L ^p -Sobolev inequalities. The logarithmic version of affine L ^p -Sobolev inequalities is verified. Moreover, an alternative proof of the affine Moser–Trudinger and Morrey–Sobolev inequalities is given. The main tools are the equimeasurability of rearrangements and the strengthened version of the classical Pólya–Szegö principle.     

Inequalities for t designs

A number of inequalities concerning the set structure of balanced incomplete block designs are unified, and strengthened in the case of t designs with t ? 4.     

Chebyshev type inequalities for pseudo-integrals

Chebyshev type inequalities for two classes of pseudo-integrals are shown. One of them concerning the pseudo-integrals based on a function reduces on the g-integral where pseudo-operations are defined by a monotone and continuous function g. Another one concerns the pseudo-integrals based on a semiring ([a,b],max,⊙), where ⊙ is generated. Moreover, a strengthened version of Chebyshev’s inequality for pseudo-integrals is proved.     

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.     

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.     

Generalized intersection cuts and a new cut generating paradigm

Intersection cuts are generated from a polyhedral cone and a convex set S whose interior contains no feasible integer point. We generalize these cuts by replacing the cone with a more general polyhedron C. The resulting generalized intersection cuts dominate the original ones. This leads to a new cutting plane paradigm under which one generates and stores the intersection points of the extreme rays of C with the boundary of S rather than the cuts themselves. These intersection points can then be used to generate in a non-recursive fashion cuts that would require several recursive applications of some standard cut generating routine. A procedure is also given for strengthening the coefficients of the integer-constrained variables of a generalized intersection cut. The new cutting plane paradigm yields a new characterization of the closure of intersection cuts and their strengthened variants. This characterization is minimal in the sense that every one of the inequalities it uses defines a facet of the closure.     

n-step mingling inequalities: new facets for the mixed-integer knapsack set

The n-step mixed integer rounding (MIR) inequalities of Kianfar and Fathi (Math Program 120(2):313–346, 2009) are valid inequalities for the mixed-integer knapsack set that are derived by using periodic n-step MIR functions and define facets for group problems. The mingling and 2-step mingling inequalities of Atamtürk and Günlük (Math Program 123(2):315–338, 2010) are also derived based on MIR and they incorporate upper bounds on the integer variables. It has been shown that these inequalities are facet-defining for the mixed integer knapsack set under certain conditions and generalize several well-known valid inequalities. In this paper, we introduce new classes of valid inequalities for the mixed-integer knapsack set with bounded integer variables, which we call n-step mingling inequalities (for positive integer n). These inequalities incorporate upper bounds on integer variables into n-step MIR and, therefore, unify the concepts of n-step MIR and mingling in a single class of inequalities. Furthermore, we show that for each n, the n-step mingling inequality defines a facet for the mixed integer knapsack set under certain conditions. For n?=?2, we extend the results of Atamtürk and Günlük on facet-defining properties of 2-step mingling inequalities. For n ≥ 3, we present new facets for the mixed integer knapsack set. As a special case we also derive conditions under which the n-step MIR inequalities define facets for the mixed integer knapsack set. In addition, we show that n-step mingling can be used to generate new valid inequalities and facets based on covers and packs defined for mixed integer knapsack sets.     

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.     

A polyhedral approach to the alldifferent system

This paper examines the facial structure of the convex hull of integer vectors satisfying a system of alldifferent predicates, also called an alldifferent system. The underlying analysis is based on a property, called inclusion, pertinent to such a system. For the alldifferent systems for which this property holds, we present two families of facet-defining inequalities, establish that they completely describe the convex hull and show that they can be separated in polynomial time. Consequently, the inclusion property characterises a group of alldifferent systems for which the linear optimization problem (i.e. the problem of optimizing a linear function over that system) can be solved in polynomial time. Furthermore, we establish that, for systems with three predicates, the inclusion property is also a necessary condition for the convex hull to be described by those two families of inequalities. For the alldifferent systems that do not possess that property, we establish another family of facet-defining inequalities and an accompanied polynomial-time separation algorithm. All the separation algorithms are incorporated within a cutting-plane scheme and computational experience on a set of randomly generated instances is reported. In concluding, we show that the pertinence of the inclusion property can be decided in polynomial time.     

The Attractive Traveling Salesman Problem

In the Attractive Traveling Salesman Problem the vertex set is partitioned into facility vertices and customer vertices. A maximum profit tour must be constructed on a subset of the facility vertices. Profit is computed through an attraction function: every visited facility vertex attracts a portion of the profit from the customer vertices based on the distance between the facility and customer vertices, and the attractiveness of the facility vertex. A gravity model is used for computing the profit attraction. The problem is formulated as an integer non-linear program. A linearization is proposed and strengthened through the introduction of valid inequalities, and a branch-and-cut algorithm is developed. A tabu search algorithm is also implemented. Computational results are reported.     

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.     

Extrapolation from A∞ weights and applications

We generalize the A_p extrapolation theorem of Rubio de Francia to A_∞ weights in the context of Muckenhoupt bases. Our result has several important features. First, it can be used to prove weak endpoint inequalities starting from strong-type inequalities, something which is impossible using the classical result. Second, it provides an alternative to the technique of good-λ inequalities for proving L^p norm inequalities relating operators. Third, it yields vector-valued inequalities without having to use the theory of Banach space valued operators. We give a number of applications to maximal functions, singular integrals, potential operators, commutators, multilinear Calderón-Zygmund operators, and multiparameter fractional integrals. In particular, we give new proofs, which completely avoid the good-λ inequalities, of Coifman's inequality relating singular integrals and the maximal operator, of the Fefferman-Stein inequality relating the maximal operator and the sharp maximal operator, and the Muckenhoupt-Wheeden inequality relating the fractional integral operator and the fractional maximal operator.     

On some partial integral inequalities in n independent variables

In this paper comparison method will be used to establish a number of fundamental partial integral inequalities in n independent variables. These inequalities can be used as ready and powerful tools in developing the qualitative theory of partial differential and integral equations in n independent variables.     

Lifting the knapsack cover inequalities for the knapsack polytope

Valid inequalities for the knapsack polytope have proven to be very useful in exact algorithms for mixed-integer linear programming. In this paper, we focus on the knapsack cover inequalities, introduced in 2000 by Carr and co-authors. In general, these inequalities can be rather weak. To strengthen them, we use lifting. Since exact lifting can be time-consuming, we present two fast approximate lifting procedures. The first procedure is based on mixed-integer rounding, whereas the second uses superadditivity.     

Isoperimetric monotony of the L p -norm of the warping function of a plane simply connected domain

Let G be a simply connected domain and let u(x,G) be its warping function. We prove that L ^p -norms of functions u and u ^?1 are monotone with respect to the parameter p. This monotony also gives isoperimetric inequalities for norms that correspond to different values of the parameter p. The main result of this paper is a generalization of classical isoperimetric inequalities of St.Venant-Pólya and the Payne inequalities.     

New inequalities for subspace arrangements

For each positive integer n?4, we give an inequality satisfied by rank functions of arrangements of n subspaces. When n=4 we recover Ingleton's inequality; for higher n the inequalities are all new. These inequalities can be thought of as a hierarchy of necessary conditions for a (poly)matroid to be realizable. Some related open questions about the “cone of realizable polymatroids” are also presented.     

Sharp inequalities for the dyadic square function in the BMO setting

We introduce a method for the simultaneous study of a BMO function φ and its dyadic square function S(φ) that can yield sharp norm inequalities between the two. One of the applications is the sharp bound for the p-th moment of S(φ), 0<p<∞, which in turn implies the square-exponential integrability of the square function. We also present sharp refinements of these inequalities in the more restrictive case when φ is assumed to be bounded.     

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.     

Applications of game theory to threshold logic

Recently,Owen demonstrated an isomorphism between characteristic function games and pseudo-Boolean functions. When a game is interpreted as a function on a lattice, then properties of pseudo-Boolean inequalities can be related to partitions of the lattice. The isomorphism also has important implications for threshold logic. In particular, by using a special reflection map, unate switching functions can be studied via monotone simple games. We can show that every unate switching function can be written as the join threshold functions. Also, using the ideas ofCharnes, Kortanek andKeene, we can give several ways to calculate approximate threshold inequalities for unate switching functions.     

On the cut polytope

The cut polytopeP _C (G) of a graphG=(V, E) is the convex hull of the incidence vectors of all edge sets of cuts ofG. We show some classes of facet-defining inequalities ofP _C (G). We describe three methods with which new facet-defining inequalities ofP _C (G) can be constructed from known ones. In particular, we show that inequalities associated with chordless cycles define facets of this polytope; moreover, for these inequalities a polynomial algorithm to solve the separation problem is presented. We characterize the facet defining inequalities ofP _C (G) ifG is not contractible toK ₅. We give a simple characterization of adjacency inP _C (G) and prove that for complete graphs this polytope has diameter one and thatP _C (G) has the Hirsch property. A relationship betweenP _C (G) and the convex hull of incidence vectors of balancing edge sets of a signed graph is studied.