Valid inequalities for separable concave constraints with indicator variables

We study valid inequalities for optimization models that contain both binary indicator variables and separable concave constraints. These models reduce to a mixed-integer linear program (MILP) when the concave constraints are ignored, or to a nonconvex global optimization problem when the binary restrictions are ignored. In algorithms designed to solve these problems to global optimality, cutting planes to strengthen the relaxation are traditionally obtained using valid inequalities for the MILP only. We propose a technique to obtain valid inequalities that are based on both the MILP constraints and the concave constraints. We begin by characterizing the convex hull of a four-dimensional set consisting of a single binary indicator variable, a single concave constraint, and two linear inequalities. Using this analysis, we demonstrate how valid inequalities for the single node flow set and for the lot-sizing polyhedron can be “tilted” to give valid inequalities that also account for separable concave functions of the arc flows. We present computational results demonstrating the utility of the new inequalities for nonlinear transportation problems and for lot-sizing problems with concave costs. To our knowledge, this is one of the first works that simultaneously convexifies both nonconvex functions and binary variables to strengthen the relaxations of practical mixed-integer nonlinear programs.     

Probabilistic programming with discrete distributions and precedence constrained knapsack polyhedra

 We consider stochastic programming problems with probabilistic constraints involving random variables with discrete distributions. They can be reformulated as large scale mixed integer programming problems with knapsack constraints. Using specific properties of stochastic programming problems and bounds on the probability of the union of events we develop new valid inequalities for these mixed integer programming problems. We also develop methods for lifting these inequalities. These procedures are used in a general iterative algorithm for solving probabilistically constrained problems. The results are illustrated with a numerical example. Received: October 8, 2000 / Accepted: August 13, 2002 Published online: September 27, 2002 Key words. stochastic programming – integer programming – valid inequalities     

Convex optimization problems involving finite autocorrelation sequences

 We discuss convex optimization problems in which some of the variables are constrained to be finite autocorrelation sequences. Problems of this form arise in signal processing and communications, and we describe applications in filter design and system identification. Autocorrelation constraints in optimization problems are often approximated by sampling the corresponding power spectral density, which results in a set of linear inequalities. They can also be cast as linear matrix inequalities via the Kalman-Yakubovich-Popov lemma. The linear matrix inequality formulation is exact, and results in convex optimization problems that can be solved using interior-point methods for semidefinite programming. However, it has an important drawback: to represent an autocorrelation sequence of length $n$, it requires the introduction of a large number ($n(n+1)/2$) of auxiliary variables. This results in a high computational cost when general-purpose semidefinite programming solvers are used. We present a more efficient implementation based on duality and on interior-point methods for convex problems with generalized linear inequalities. Received: August 20, 2001 / Accepted: July 16, 2002 Published online: September 27, 2002 RID="★" ID="★" This material is based upon work supported by the National Science Foundation under Grant No. ECS-9733450.     

On the Boundedness of Solutions of Degenerate Anisotropic Elliptic Variational Inequalities

In this article, for a class of degenerate anisotropic elliptic second-order variational inequalities we give conditions on the right-hand side and the set of constraints under which solutions of the variational inequalities are bounded. Our conditions on the set of constraints admit the consideration of a sufficiently large class of problems with pointwise constraints, and in particular, unilateral and bilateral problems. They also admit the consideration of the Dirichlet problem for the corresponding equations. We provide a series of examples which demonstrate the essentiality of the imposed conditions. In particular, we show that the condition assumed for the right-hand side of the variational inequalities in general is unimprovable in the scale of Lebesgue spaces.     

Dynamic bundle methods

Lagrangian relaxation is a popular technique to solve difficult optimization problems. However, the applicability of this technique depends on having a relatively low number of hard constraints to dualize. When there are many hard constraints, it may be preferable to relax them dynamically, according to some rule depending on which multipliers are active. From the dual point of view, this approach yields multipliers with varying dimensions and a dual objective function that changes along iterations. We discuss how to apply a bundle methodology to solve this kind of dual problems. Our framework covers many separation procedures to generate inequalities that can be found in the literature, including (but not limited to) the most violated inequality. We analyze the resulting dynamic bundle method giving a positive answer for its primal-dual convergence properties, and, under suitable conditions, show finite termination for polyhedral problems. Claudia Sagastizábal is on leave from INRIA Rocquencourt, France. Research supported by CNPq Grant No.303540-03/6.     

Interior projection-like methods for monotone variational inequalities

We propose new interior projection type methods for solving monotone variational inequalities. The methods can be viewed as a natural extension of the extragradient and hyperplane projection algorithms, and are based on using non Euclidean projection-like maps. We prove global convergence results and establish rate of convergence estimates. The projection-like maps are given by analytical formulas for standard constraints such as box, simplex, and conic type constraints, and generate interior trajectories. We then demonstrate that within an appropriate primal-dual variational inequality framework, the proposed algorithms can be applied to general convex constraints resulting in methods which at each iteration entail only explicit formulas and do not require the solution of any convex optimization problem. As a consequence, the algorithms are easy to implement, with low computational cost, and naturally lead to decomposition schemes for problems with a separable structure. This is illustrated through examples for convex programming, convex-concave saddle point problems and semidefinite programming.The work of this author was partially supported by the United States–Israel Binational Science Foundation, BSF Grant No. 2002-2010.     

Multiprocessor scheduling under precedence constraints: Polyhedral results

We consider the problem of scheduling a set of tasks related by precedence constraints to a set of processors, so as to minimize their makespan. Each task has to be assigned to a unique processor and no preemption is allowed. A new integer programming formulation of the problem is given and strong valid inequalities are derived. A subset of the inequalities in this formulation has a strong combinatorial structure, which we use to define the polytope of partitions into linear orders. The facial structure of this polytope is investigated and facet defining inequalities are presented which may be helpful to tighten the integer programming formulation of other variants of multiprocessor scheduling problems. Numerical results on real-life problems are presented.     

Lagrange Multipliers and mixed formulations for some inequality constrained variational inequalities and some nonsmooth unilateral problems

Abstract

This paper addresses a class of inequality constrained variational inequalities and nonsmooth unilateral variational problems. We present mixed formulations arising from Lagrange multipliers. First we treat in a reflexive Banach space setting the canonical case of a variational inequality that has as essential ingredients a bilinear form and a non-differentiable sublinear, hence convex functional and linear inequality constraints defined by a convex cone. We extend the famous Brezzi splitting theorem that originally covers saddle point problems with equality constraints, only, to these nonsmooth problems and obtain independent Lagrange multipliers in the subdifferential of the convex functional and in the ordering cone of the inequality constraints. For illustration of the theory we provide and investigate an example of a scalar nonsmooth boundary value problem that models frictional unilateral contact problems in linear elastostatics. Finally we discuss how this approach to mixed formulations can be further extended to variational problems with nonlinear operators and equilibrium problems, and moreover, to hemivariational inequalities.     

A second-order method for the general nonlinear programming problem

This paper presents a multiplier-type method for nonlinear programming problems with both equality and inequality constraints. Slack variables are used for the inequalities. The penalty coefficient is adjusted automatically, and the method converges quadratically to points satisfying second-order conditions.The work of the first author was supported by NSF RANN and JSEP Contract No. F44620-71-C-0087; the work of the second author was supported by the National Science Foundation Grant No. ENG73-08214A01 and US Army Research Office Durham Contract No. DAHC04-73-C-0025.     

Well-posedness for Optimization Problems with Constraints defined by Variational Inequalities having a unique solution

We introduce various notions of well-posedness for a family of variational inequalities and for an optimization problem with constraints defined by variational inequalities having a unique solution. Then, we give sufficient conditions for well-posedness of these problems and we present an application to an exact penalty method.     

Valid inequalities and restrictions for stochastic programming problems with first order stochastic dominance constraints

Stochastic dominance relations are well studied in statistics, decision theory and economics. Recently, there has been significant interest in introducing dominance relations into stochastic optimization problems as constraints. In the discrete case, stochastic optimization models involving second order stochastic dominance constraints can be solved by linear programming. However, problems involving first order stochastic dominance constraints are potentially hard due to the non-convexity of the associated feasible regions. In this paper we consider a mixed 0–1 linear programming formulation of a discrete first order constrained optimization model and present a relaxation based on second order constraints. We derive some valid inequalities and restrictions by employing the probabilistic structure of the problem. We also generate cuts that are valid inequalities for the disjunctive relaxations arising from the underlying combinatorial structure of the problem by applying the lift-and-project procedure. We describe three heuristic algorithms to construct feasible solutions, based on conditional second order constraints, variable fixing, and conditional value at risk. Finally, we present numerical results for several instances of a real world portfolio optimization problem. This research was supported by the NSF awards DMS-0603728 and DMI-0354678.     

On the Determination of a Density Function by Its Autoconvolution Coefficient

We investigate eigenvalues and eigenvectors of certain linear variational eigenvalue inequalities where the constraints are defined by a convex cone as in [4], [7], [8], [10]-[12], [17]. The eigenvalues of those eigenvalue problems are of interest in connection with bifurcation from the trivial solution of nonlinear variational inequalities. A rather far reaching theory is presented for the case that the cone is given by a finite number of linear inequalities, where an eigensolution corresponds to a (+)-Kuhn-Tucker point of the Rayleigh quotient. Application to an unlaterally supported beam are discussed and numerical results are given.     

An Adaptive Dual Parametrization Algorithm for Quadratic Semi-infinite Programming Problems

The so called dual parametrization method for quadratic semi-infinite programming (SIP) problems is developed recently for quadratic SIP problems with a single infinite constraint. A dual parametrization algorithm is also proposed for numerical solution of such problems. In this paper, we consider quadratic SIP problems with positive definite objective and multiple linear infinite constraints. All the infinite constraints are supposed to be continuously dependent on their index variable on a compact set which is defined by a number equality and inequalities. We prove that in the multiple infinite constraint case, the minimu parametrization number, just as in the single infinite constraint case, is less or equal to the dimension of the SIP problem. Furthermore, we propose an adaptive dual parametrization algorithm with convergence result. Compared with the previous dual parametrization algorithm, the adaptive algorithm solves subproblems with much smaller number of constraints. The efficiency of the new algorithm is shown by solving a number of numerical examples.     

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.     

New Relaxation Method for Mathematical Programs with Complementarity Constraints

In this paper, we present a new relaxation method for mathematical programs with complementarity constraints. Based on the fact that a variational inequality problem defined on a simplex can be represented by a finite number of inequalities, we use an expansive simplex instead of the nonnegative orthant involved in the complementarity constraints. We then remove some inequalities and obtain a standard nonlinear program. We show that the linear independence constraint qualification or the Mangasarian–Fromovitz constraint qualification holds for the relaxed problem under some mild conditions. We consider also a limiting behavior of the relaxed problem. We prove that any accumulation point of stationary points of the relaxed problems is a weakly stationary point of the original problem and that, if the function involved in the complementarity constraints does not vanish at this point, it is C-stationary. We obtain also some sufficient conditions of B-stationarity for a feasible point of the original problem. In particular, some conditions described by the eigenvalues of the Hessian matrices of the Lagrangian functions of the relaxed problems are new and can be verified easily. Our limited numerical experience indicates that the proposed approach is promising.     

Clique-based facets for the precedence constrained knapsack problem

We consider a knapsack problem with precedence constraints imposed on pairs of items, known as the precedence constrained knapsack problem (PCKP). This problem has applications in manufacturing and mining, and also appears as a subproblem in decomposition techniques for network design and related problems. We present a new approach for determining facets of the PCKP polyhedron based on clique inequalities. A comparison with existing techniques, that lift knapsack cover inequalities for the PCKP, is also presented. It is shown that the clique-based approach generates facets that cannot be found through the existing cover-based approaches, and that the addition of clique-based inequalities for the PCKP can be computationally beneficial, for both PCKP instances arising in real applications, and applications in which PCKP appears as an embedded structure.     

Exploiting nested inequalities and surrogate constraints

The exploitation of nested inequalities and surrogate constraints as originally proposed in Glover [Glover, F., 1965. A multiphase-dual algorithm for the zero–one integer programming problem. Operations Research 13, 879–919; Glover, F., 1971. Flows in arborescences. Management Science 17, 568–586] has been specialized to multidimensional knapsack problems in Osorio et al. [Osorio, M.A., Glover, F., Hammer, P., 2002. Cutting and surrogate constraint analysis for improved multidimensional knapsack solutions. Annals of Operations Research 117, 71–93]. We show how this specialized exploitation can be strengthened to give better results. This outcome results by a series of observations based on surrogate constraint duality and properties of nested inequalities. The consequences of these observations are illustrated by numerical examples to provide insights into uses of surrogate constraints and nested inequalities that can be useful in a variety of problem settings.     

A polyhedral study of the cardinality constrained knapsack problem

 A cardinality constrained knapsack problem is a continuous knapsack problem in which no more than a specified number of nonnegative variables are allowed to be positive. This structure occurs, for example, in areas such as finance, location, and scheduling. Traditionally, cardinality constraints are modeled by introducing auxiliary 0-1 variables and additional constraints that relate the continuous and the 0-1 variables. We use an alternative approach, in which we keep in the model only the continuous variables, and we enforce the cardinality constraint through a specialized branching scheme and the use of strong inequalities valid for the convex hull of the feasible set in the space of the continuous variables. To derive the valid inequalities, we extend the concepts of cover and cover inequality, commonly used in 0-1 programming, to this class of problems, and we show how cover inequalities can be lifted to derive facet-defining inequalities. We present three families of non-trivial facet-defining inequalities that are lifted cover inequalities. Finally, we report computational results that demonstrate the effectiveness of lifted cover inequalities and the superiority of the approach of not introducing auxiliary 0-1 variables over the traditional MIP approach for this class of problems. Received: March 13, 2003 Published online: April 10, 2003 Key Words. mixed-integer programming – knapsack problem – cardinality constrained programming – branch-and-cut     

A converse for disjunctive constraints

A necessary and sufficient condition is given for the disjunctive constraints construction to provide all valid cuts for a system of logical constraints on linear inequalities. This condition is then applied to several commonly occurring situations of integer programming, and the issue of verification of the condition is discussed.This research was supported by NSF Grant No. GP-37510 X1 and ONR Contract No. N00014-75-C-0621, NR047-048.     

A Polyhedral Approach for Nonconvex Quadratic Programming Problems with Box Constraints

We apply a linearization technique for nonconvex quadratic problems with box constraints. We show that cutting plane algorithms can be designed to solve the equivalent problems which minimize a linear function over a convex region. We propose several classes of valid inequalities of the convex region which are closely related to the Boolean quadric polytope. We also describe heuristic procedures for generating cutting planes. Results of preliminary computational experiments show that our inequalities generate a polytope which is a fairly tight approximation of the convex region.