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.     

Gap inequalities for non-convex mixed-integer quadratic programs

Laurent and Poljak introduced a very general class of valid linear inequalities, called gap inequalities, for the max-cut problem. We show that an analogous class of inequalities can be defined for general non-convex mixed-integer quadratic programs. These inequalities dominate some inequalities arising from a natural semidefinite relaxation.     

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     

Merit functions for general variational inequalities

In this paper, we consider some classes of merit functions for general variational inequalities. Using these functions, we obtain error bounds for the solution of general variational inequalities under some mild conditions. Since the general variational inequalities include variational inequalities, quasivariational inequalities and complementarity problems as special cases, results proved in this paper hold for these problems. In this respect, results obtained in this paper represent a refinement of previously known results for classical variational inequalities.     

Operator-norm inequalities and interpolated trace inequalities

In this article, we investigate some operator-norm inequalities related to some conjectures posed by Hayajneh and Kittaneh that are related to questions of Bourin regarding a special type of inequalities referred to as subadditivity inequalities. While some inequalities are meant to answer these conjectures, other inequalities present reverse-type inequalities for these conjectures. Then, we present some new trace inequalities related to Heinz means inequality and use these inequalities to prove some variants of the aforementioned conjectures.     

Hemivariational-like inequalities

In this paper, we introduce and consider a new class of variational inequalities, known as the hemivariational-like inequalities. It is shown that the hemivariational-like inequalities include hemivariational inequalities, variational-like inequalities and the classical variational inequalities as special cases. The auxiliary principle is used to suggest and analyze some iterative methods for solving hemivariational-like inequalities under mild conditions. The results obtained in this paper can be considered as a novel application of the auxiliary principle technique.     

A Class of Differential Vector Variational Inequalities in Finite Dimensional Spaces

In this paper, we introduce and study a class of differential vector variational inequalities in finite dimensional Euclidean spaces. We establish a relationship between differential vector variational inequalities and differential scalar variational inequalities. Under various conditions, we obtain the existence and linear growth of solutions to the scalar variational inequalities. In particular we prove existence theorems for Carathéodory weak solutions of the differential vector variational inequalities. Furthermore, we give a convergence result on Euler time-dependent procedure for solving the initial-value differential vector variational inequalities.     

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.     

Weighted Variational Inequalities

In this paper, we introduce weighted variational inequalities over product of sets and system of weighted variational inequalities. It is noted that the weighted variational inequality problem over product of sets and the problem of system of weighted variational inequalities are equivalent. We give a relationship between system of weighted variational inequalities and systems of vector variational inequalities. We define several kinds of weighted monotonicities and establish several existence results for the solution of the above-mentioned problems under these weighted monotonicities. We introduce also the weighted generalized variational inequalities over product of sets, that is, weighted variational inequalities for multivalued maps and systems of weighted generalized variational inequalities. Extensions of weighted monotonicities for multivalued maps are also considered. The existence of a solution of weighted generalized variational inequalities over product of sets is also studied. The existence results for a solution of weighted generalized variational inequality problem give also the existence of solutions of systems of generalized vector variational inequalities. The first and third author express their thanks to the Department of Mathematical Sciences, King Fahd University of Petroleum and Minerals, Dhahran, Saudi Arabia for providing excellent research facilities. The authors are also grateful to the referees for comments and suggestions improving the final draft of this paper.     

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.     

Functional inequalities for the Wright functions

In this paper, our aim is to show some mean value inequalities for the Wright function, such as Turán-type inequalities, Lazarevi?-type inequalities, Wilker-type inequalities and Redheffer-type inequalities. Moreover, we prove monotonicity of ratios for sections of series of Wright functions, the result is also closely connected with Turán-type inequalities. In the end of the paper, we present some other inequalities for the Wright function.     

Comparative and restrictive inequalities

Inequalities are an important topic in school mathematics, yet the body of research exploring students’ meanings for inequalities largely points to difficulties they experience. Thus, there is a need to further explore students’ meanings for inequalities. Addressing this need, we conducted an exploratory teaching experiment with two seventh-grade students to investigate their developing meanings for inequalities. We distinguish between two types of inequalities in student thinking: comparative and restrictive inequalities. Whereas a student reasoning about a comparative inequality compares two quantities’ values or magnitudes, reasoning about a restrictive inequality entails reasoning about a range of one quantity’s magnitudes or values. We realized a complexity arose in our interactions with students due to our conceiving the use of inequality symbols across the two types of inequalities as polysemous, whereas the students did not. Attending to these two types of inequalities has important implications for the teaching and learning of inequality.     

Capacitated facility location: Separation algorithms and computational experience

We consider the polyhedral approach to solving the capacitated facility location problem. The valid inequalities considered are the knapsack cover, flow cover, effective capacity, single depot, and combinatorial inequalities. The flow cover, effective capacity and single depot inequalities form subfamilies of the general family of submodular inequalities. The separation problem based on the family of submodular inequalities is NP-hard in general. For the well known subclass of flow cover inequalities, however, we show that if the client set is fixed, and if all capacities are equal, then the separation problem can be solved in polynomial time. For the flow cover inequalities based on an arbitrary client set and general capacities, and for the effective capacity and single depot inequalities we develop separation heuristics. An important part of these heuristics is based on the result that two specific conditions are necessary for the effective cover inequalities to be facet defining. The way these results are stated indicates precisely how structures that violate the two conditions can be modified to produce stronger inequalities. The family of combinatorial inequalities was originally developed for the uncapacitated facility location problem, but is also valid for the capacitated problem. No computational experience using the combinatorial inequalities has been reported so far. Here we suggest how partial output from the heuristic identifying violated submodular inequalities can be used as input to a heuristic identifying violated combinatorial inequalities. We report on computational results from solving 60 medium size problems. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.     

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.     

On the Gap Functions of Prevariational Inequalities

Gap functions play a crucial role in transforming a variational inequality problem into an optimization problem. Then, methods solving an optimization problem can be exploited for finding a solution of a variational inequality problem. It is known that the so-called prevariational inequality is closely related to some generalized convex functions, such as linear fractional functions. In this paper, gap functions for several kinds of prevariational inequalities are investigated. More specifically, prevariational inequalities, extended prevariational inequalities, and extended weak vector prevariational inequalities are considered. Furthermore, a class of gap functions for inequality constrained prevariational inequalities is investigated via a nonlinear Lagrangian.     

On a system of general mixed variational inequalities

In this paper, we introduce and consider a new system of general mixed variational inequalities involving three different operators. Using the resolvent operator technique, we establish the equivalence between the general mixed variational inequalities and the fixed point problems. We use this equivalent formulation to suggest and analyze some new explicit iterative methods for this system of general mixed variational inequalities. We also study the convergence analysis of the new iterative method under certain mild conditions. Since this new system includes the system of mixed variational inequalities involving two operators, variational inequalities and related optimization problems as special cases, results obtained in this paper continue to hold for these problems. Our results can be viewed as a refinement and improvement of the previously known results for variational inequalities.     

直线上函数的Banach空间的Poincaré型不等式的变分公式

基于研究对数Sobolev,Nash和其它泛函不等式的需要,将Poincare不等式 的变分公式拓广到一大类直线上函数的Banach(Orlicz)空间.给出了这些不等式成立 与否的显式判准和显式估计. 作为典型应用,仔细考察了对数Sobolev常数.     

On first order interpolation inequalities with weights on the Heisenberg group

In this paper, sufficient and necessary conditions for the first order interpolation inequalities with weights on the Heisenberg group are given. The necessity is discussed by polar coordinates changes of the Heisenberg group. Establishing a class of Hardy type inequalities via a new representation formula for functions and Hardy-Sobolev type inequalities by interpolation, we derive the sufficiency. Finally, sharp constants for Hardy type inequalities are determined.     

Zigzag inequalities: a new class of facet-inducing inequalities for Arc Routing Problems

In this paper we introduce a new class of facet-inducing inequalities for the Windy Rural Postman Problem and the Windy General Routing Problem. These inequalities are called Zigzag inequalities because they cut off fractional solutions containing a zigzag associated with variables with 0.5 value. Two different types of inequalities, the Odd Zigzag and the Even Zigzag inequalities, are presented. Finally, their application to other known Arc Routing Problems is discussed.