On the extreme inequalities of infinite group problems

Infinite group relaxations of integer programs (IP) were introduced by Gomory and Johnson (Math Program 3:23–85, 1972) to generate cutting planes for general IPs. These valid inequalities correspond to real-valued functions defined over an appropriate infinite group. Among all the valid inequalities of the infinite group relaxation, extreme inequalities are most important since they are the strongest cutting planes that can be obtained within the group-theoretic framework. However, very few properties of extreme inequalities of infinite group relaxations are known. In particular, it is not known if all extreme inequalities are continuous and what their relations are to extreme inequalities of finite group problems. In this paper, we describe new properties of extreme functions of infinite group problems. In particular, we study the behavior of the pointwise limit of a converging sequence of extreme functions as well as the relations between extreme functions of finite and infinite group problems. Using these results, we prove for the first time that a large class of discontinuous functions is extreme for infinite group problems. This class of extreme functions is the generalization of the functions given by Letchford and Lodi (Oper Res Lett 30(2):74–82, 2002), Dash and Günlük (Proceedings 10th conference on integer programming and combinatorial optimization. Springer, Heidelberg, pp 33–45 (2004), Math Program 106:29–53, 2006) and Richard et al. (Math Program 2008, to appear). We also present several other new classes of discontinuous extreme functions. Surprisingly, we prove that the functions defining extreme inequalities for infinite group relaxations of mixed integer programs are continuous. S.S. Dey and J.-P.P. Richard was supported by NSF Grant DMI-03-48611.     

Generalized mixed integer rounding inequalities: facets for infinite group polyhedra

We present a generalization of the mixed integer rounding (MIR) approach for generating valid inequalities for (mixed) integer programming (MIP) problems. For any positive integer n, we develop n facets for a certain (n + 1)-dimensional single-constraint polyhedron in a sequential manner. We then show that for any n, the last of these facets (which we call the n-step MIR facet) can be used to generate a family of valid inequalities for the feasible set of a general (mixed) IP constraint, which we refer to as the n-step MIR inequalities. The Gomory Mixed Integer Cut and the 2-step MIR inequality of Dash and günlük  (Math Program 105(1):29–53, 2006) are the first two families corresponding to n = 1,2, respectively. The n-step MIR inequalities are easily produced using periodic functions which we refer to as the n-step MIR functions. None of these functions dominates the other on its whole period. Finally, we prove that the n-step MIR inequalities generate two-slope facets for the infinite group polyhedra, and hence are potentially strong.      

Using mixed integer programming for solving the capacitated arc routing problem with vehicle/site dependencies with an application to the routing of residential sanitation collection vehicles

We present the Composite Approach for solving the Capacitated Arc Routing Problem with Vehicle/Site Dependencies (CARP-VSD). We also present two mixed integer programs, the Initial Fleet Mix Generator (IFM) and the Mathematical Programming Procedure (MPP), and a multi-criterion function called the Measure of Goodness. The IFM, MPP and Measure of Goodness are critical components of the Composite Approach. A key application area of the CARP-VSD is the routing of residential sanitation vehicles; throughout this paper, we derive parameters specific to this problem. In this paper, we describe the Composite Approach, the IFM, the MPP, the Measure of Goodness and work out several examples in detail.     

Systems of semilinear higher-order evolution inequalities on the Heisenberg group

This paper is devoted to nonexistence results for solutions to the problem

((Skm))     

Orlicz-Sobolev inequalities for sub-Gaussian measures and ergodicity of Markov semi-groups

We study coercive inequalities in Orlicz spaces associated to the probability measures on finite- and infinite-dimensional spaces which tails decay slower than the Gaussian ones. We provide necessary and sufficient criteria for such inequalities to hold and discuss relations between various classes of inequalities.     

On the strength of Gomory mixed-integer cuts as group cuts

Gomory mixed-integer (GMI) cuts generated from optimal simplex tableaus are known to be useful in solving mixed-integer programs. Further, it is well-known that GMI cuts can be derived from facets of Gomory’s master cyclic group polyhedron and its mixed-integer extension studied by Gomory and Johnson. In this paper we examine why cutting planes derived from other facets of master cyclic group polyhedra (group cuts) do not seem to be as useful when used in conjunction with GMI cuts. For many practical problem instances, we numerically show that once GMI cuts from different rows of the optimal simplex tableau are added to the formulation, all other group cuts from the same tableau rows are satisfied.     

Nondecomposable solutions to group equations and an application to polyhedral combinatorics

This paper is based on the study of the set of nondecomposable integer solutions in a Gomory corner polyhedron, which was recently used in a reformulation method for integer linear programs. In this paper, we present an algorithm for efficiently computing this set. We precompute a database of nondecomposable solutions for cyclic groups up to order 52. As a second application of this database, we introduce an algorithm for computing nontrivial simultaneous lifting coefficients. The lifting coefficients are exact for a discrete relaxation of the integer program that consists of a group relaxation plus bound constraints. Received: November 2004 / Revised version: June 2005 AMS classification: 90C10, 90C57     

Concentration of Haar measures, with an application to random matrices

We show that the mixing times of random walks on compact groups can be used to obtain concentration inequalities for the respective Haar measures. As an application, we derive a concentration inequality for the empirical distribution of eigenvalues of sums of random Hermitian matrices, with possible applications in free probability. The advantage over existing techniques is that the new method can deal with functions that are non-Lipschitz or even discontinuous with respect to the usual metrics.     

An application of quasivariational inequalities to linear control systems

Starting from a recent result on generalized quasivariational inequalities, we derive a general theorem concerning the qualitative properties of the fixed-point set of certain multifunctions. Then, we apply our result to the problem of the existence of periodic solutions for a linear control system with the property that the final value lies on the relative boundary of the corresponding attainable set.This research was presented during the 19th Course of the International School of Mathematics G. Stampacchia, Variational Inequalities and Network Equilibrium Problems, Erice, Italy, June 1994.     

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.     

一类P-强制变分不等方程及其应用

:建立了变分不等方程〈Au,u - v〉 + j(u) - j(v)≤〈f ,u - v〉,　　 v∈ K的解的存在性定理 ,其中凸泛函 j(v)不必是半可加的 ,A是 j- P -强制算子 .并应用于Von Karman方程的障碍问题 .     

Existence of Solutions and an Algorithm for Mixed Variational-Like Inequalities in Banach Spaces

In this paper, we study the class of mixed variational-like inequalities in reflexive Banach spaces. By applying a minimax inequality due to the author, some existence and uniqueness theorems for solutions of mixed variational-like inequalities are proved. Next, by applying the auxiliary problem technique, we suggest an innovative iterative algorithm to compute approximate solutions of the mixed variational-like inequality. Finally, convergence criteria are also discussed. This research was supported by NSF, Sichman Education Department of China, Projects 2003A081 and SZD0406. The author expresses his sincere thanks to Professor H.P. Benson and the anonymous referees for careful comments leading to the present version of this paper.     

A complex semigroup approach to group algebras of infinite dimensional Lie groups

A host algebra of a topological group G is a C ^*-algebra whose representations are in one-to-one correspondence with certain continuous unitary representations of G. In this paper we present an approach to host algebras for infinite dimensional Lie groups which is based on complex involutive semigroups. Any locally bounded absolute value α on such a semigroup S leads in a natural way to a C ^*-algebra C ^*(S,α), and we describe a setting which permits us to conclude that this C ^*-algebra is a host algebra for a Lie group G. We further explain how to attach to any such host algebra an invariant weak-*-closed convex set in the dual of the Lie algebra of G enjoying certain nice convex geometric properties. If G is the additive group of a locally convex space, we describe all host algebras arising this way. The general non-commutative case is left for the future. To K.H. Hofmann on the occasion of his 75th birthday     

Finding the symmetry group of an LP with equality constraints and its application to classifying orthogonal arrays

For a given linear program (LP) a permutation of its variables that sends feasible points to feasible points and preserves the objective function value of each of its feasible points is a symmetry of the LP. The set of all symmetries of an LP, denoted by $G^{\mathrm{LP}}$, is the symmetry group of the LP. Margot (2010) described a method for computing a subgroup of the symmetry group $G^{\mathrm{LP}}$ of an LP. This method computes $G^{\mathrm{LP}}$ when the LP has only non-redundant inequalities and its feasible set satisfies no equality constraints. However, when the feasible set of the LP satisfies equality constraints this method finds only a subgroup of $G^{\mathrm{LP}}$ and can miss symmetries. We develop a method for finding the symmetry group of a feasible LP whose feasible set satisfies equality constraints. We apply this method to find and exploit the previously unexploited symmetries of an orthogonal array defining integer linear program (ILP) within the branch-and-bound (B&B) with isomorphism pruning algorithm (Margot, 2007). Our method reduced the running time for finding all OD-equivalence classes of OA $(160,8,2,4)$ and OA $(176,8,2,4)$ by factors of $1∕(2.16)$ and $1∕(1.36)$ compared to the fastest known method (Bulutoglu and Ryan, 2018). These were the two bottleneck cases that could not have been solved until the B&B with isomorphism pruning algorithm was applied. Another key finding of this paper is that converting inequalities to equalities by introducing slack variables and exploiting the symmetry group of the resulting ILP’s LP relaxation within the B&B with isomorphism pruning algorithm can reduce the computation time by several orders of magnitude when enumerating a set of all non-isomorphic solutions of an ILP.     

Global and superlinear convergence of the smoothing Newton method and its application to general box constrained variational inequalities

The smoothing Newton method for solving a system of nonsmooth equations , which may arise from the nonlinear complementarity problem, the variational inequality problem or other problems, can be regarded as a variant of the smoothing method. At the th step, the nonsmooth function is approximated by a smooth function , and the derivative of at is used as the Newton iterative matrix. The merits of smoothing methods and smoothing Newton methods are global convergence and convenience in handling. In this paper, we show that the smoothing Newton method is also superlinearly convergent if is semismooth at the solution and satisfies a Jacobian consistency property. We show that most common smooth functions, such as the Gabriel-Moré function, have this property. As an application, we show that for box constrained variational inequalities if the involved function is -uniform, the iteration sequence generated by the smoothing Newton method will converge to the unique solution of the problem globally and superlinearly (quadratically).

     

Some inequalities for communtators and an application to spectral variation

Summary If –I is a positive semidefinite operator andA andB are either both Hermitian or both unitary, then every unitarily invariant norm ofA–B is shown to be bounded by that ofA–B. Some related inequalities are proved. An application leads to a generalization of the Lidskii-Wielandt inequality to matrices similar to Hermitian.Dedicated to the memory of Alexander M. Ostrowski on the occasion of the 100th anniversary of his birth     

A class of implicit variational inequalities and applications to frictional contact

This paper deals with the mathematical and numerical analysis of a class of abstract implicit evolution variational inequalities. The results obtained here can be applied to a large variety of quasistatic contact problems in linear elasticity, including unilateral contact or normal compliance conditions with friction. In particular, a quasistatic unilateral contact problem with nonlocal friction is considered. An algorithm is derived and some numerical examples are presented. Copyright © 2009 John Wiley & Sons, Ltd.     

Some inequalities for differentiable convex mapping with application to weighted trapezoidal formula and higher moments of random variables

Several inequalities for differentiable convex, wright-convex and quasi-convex mapping are obtained respectively that are connected with the celebrated Hermite-Hadamard integral inequality. Also, some error estimates for weighted Trapezoid formula and higher moments of random variables are given.     

Some inequalities for symmetric functions and an application to orthogonal polynomials

We present some sharp inequalities for symmetric functions and give an application to orthogonal polynomials.