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.     

Uniform saturation in linear inequality systems

Redundant constraints in linear inequality systems can be characterized as those inequalities that can be removed from an arbitrary linear optimization problem posed on its solution set without modifying its value and its optimal set. A constraint is saturated in a given linear optimization problem when it is binding at the optimal set. Saturation is a property related with the preservation of the value and the optimal set under the elimination of the given constraint, phenomena which can be seen as weaker forms of excess information in linear optimization problems. We say that an inequality of a given linear inequality system is uniformly saturated when it is saturated for any solvable linear optimization problem posed on its solution set. This paper characterizes the uniform saturated inequalities and other related classes of inequalities. This work was supported by the MCYT of Spain and FEDER of UE, Grant BFM2002-04114-C02-01.     

Rigorous filtering using linear relaxations

This paper presents rigorous filtering methods for continuous constraint satisfaction problems based on linear relaxations, designed to efficiently handle the linear inequalities coming from a linear relaxation of quadratic constraints. Filtering or pruning stands for reducing the search space of constraint satisfaction problems. Discussed are old and new approaches for rigorously enclosing the solution set of linear systems of inequalities, as well as different methods for computing linear relaxations. This allows custom combinations of relaxation and filtering. Care is taken to ensure that all methods correctly account for rounding errors in the computations. The methods are implemented in the GloptLab environment for solving quadratic constraint satisfaction problems. Demonstrative examples and tests comparing the different linear relaxation methods are also presented.     

Neuro-fuzzy based constraint programming

Constraint programming models appear in many sciences including mathematics, engineering and physics. These problems aim at optimizing a cost function joint with some constraints. Fuzzy constraint programming has been developed for treating uncertainty in the setting of optimization problems with vague constraints. In this paper, a new method is presented into creation fuzzy concept for set of constraints. Unlike to existing methods, instead of constraints with fuzzy inequalities or fuzzy coefficients or fuzzy numbers, vague nature of constraints set is modeled using learning scheme with adaptive neural-fuzzy inference system (ANFIS). In the proposed approach, constraints are not limited to differentiability, continuity, linearity; also the importance degree of each constraint can be easily applied. Unsatisfaction of each weighted constraint reduces membership of certainty for set of constraints. Monte-Carlo simulations are used for generating feature vector samples and outputs for construction of necessary data for ANFIS. The experimental results show the ability of the proposed approach for modeling constrains and solving parametric programming problems.     

Gap Functions for Quasivariational Inequalities and Generalized Nash Equilibrium Problems

The gap function (or merit function) is a classic tool for reformulating a Stampacchia variational inequality as an optimization problem. In this paper, we adapt this technique for quasivariational inequalities, that is, variational inequalities in which the constraint set depends on the current point. Following Fukushima (J. Ind. Manag. Optim. 3:165–171, 2007), an axiomatic approach is proposed. Error bounds for quasivariational inequalities are provided and an application to generalized Nash equilibrium problems is also considered.     

Equilibrium problems with generalized monotone mapping and its applications

In this paper, we deal with invex equilibrium problems (IEPs for short). When the constraint set is compact convex, an existence result of solutions is obtained by Schauder's fixed point theorem. If the constraint set is closed invex, we introduce the concept of relaxed α–η pseudomonotone mappings and prove some existence results of solutions for the (IEPs), which extend and generalize several well‐known results in many respects. Moreover, we present that if the IEPs are applied to hemivariational inequalities problems, the conditions can be weakened. Copyright © 2015 John Wiley & Sons, Ltd.     

Projected Dynamical Systems and Evolutionary Variational Inequalities via Hilbert Spaces with Applications<Superscript>1</Superscript>

In this paper, we make explicit the connection between projected dynamical systems on Hilbert spaces and evolutionary variational inequalities. We give a novel formulation that unifies the underlying constraint sets for such inequalities, which arise in time-dependent traffic network, spatial price equilibrium, and a variety of financial equilibrium problems. We emphasize the importance of the results in applications and provide a traffic network numerical example in which we compute the curve of equilibria. ¹This research was funded by the Rockefeller Foundation, Bellagio Center Program. The first author was also supported by NSERC Discovery Grant 045997 and the third author by NSF Grant IIS-0002647. The authors thank Professors George Isac, Antonino Maugeri, and Panos Pardalos for support and inspiration; they are indebted to Professor Antonino Maugeri for assistance throughout their residency at Bellagio, Italy in March 2004.     

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.     

A polyhedral study on 0–1 knapsack problems with disjoint cardinality constraints: Strong valid inequalities by sequence-independent lifting

We study the set of 0–1 integer solutions to a single knapsack constraint and a set of non-overlapping cardinality constraints (MCKP), which generalizes the classical 0–1 knapsack polytope and the 0–1 knapsack polytope with generalized upper bounds. We derive strong valid inequalities for the convex hull of its feasible solutions using sequence-independent lifting. For problems with a single cardinality constraint, we derive two-dimensional superadditive lifting functions and prove that they are maximal and non-dominated under some mild conditions. We then show that these functions can be used to build strong valid inequalities for problems with multiple disjoint cardinality constraints. Finally, we present preliminary computational results aimed at evaluating the strength of the cuts obtained from sequence-independent lifting with respect to those obtained from sequential lifting.     

Generalized abstract economy and systems of generalized vector quasi-equilibrium problems

The present paper is in two-fold. The first fold is devoted to the existence theory of equilibria for generalized abstract economy with a lower semicontinuous constraint correspondence and a fuzzy constraint correspondence defined on a noncompact/nonparacompact strategy set. In the second fold, we consider systems of generalized vector quasi-equilibrium problems for multivalued maps (for short, SGVQEPs) which contain systems of vector quasi-equilibrium problems, systems of generalized mixed vector quasi-variational inequalities and Debreu-type equilibrium problems for vector valued functions as special cases. By using the results of first fold, we establish some existence results for solutions of SGVQEPs.     

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.     

A hybrid evolutionary algorithm for the two-dimensional packing problem

This paper presents a hybrid evolutionary algorithm for the two-dimensional non-guillotine packing problem. The problem consists of packing many rectangular pieces into a single rectangular sheet in order to maximize the total area of the pieces packed. Moreover, there is a constraint on the maximum number of times that a piece may be used in a packing pattern. The set of packing patterns is processed by an evolutionary algorithm. Three mutation operators and two types of quality functions are used in the algorithm. The best solution obtained by the evolutionary algorithm is used as the initial solution in a tree search improvement procedure. This approach is tested on a set of benchmark problems taken from the literature and compared with the results published by other authors.     

Linear convergence analysis of the use of gradient projection methods on total variation problems

Optimization problems using total variation frequently appear in image analysis models, in which the sharp edges of images are preserved. Direct gradient descent methods usually yield very slow convergence when used for such optimization problems. Recently, many duality-based gradient projection methods have been proposed to accelerate the speed of convergence. In this dual formulation, the cost function of the optimization problem is singular, and the constraint set is not a polyhedral set. In this paper, we establish two inequalities related to projected gradients and show that, under some non-degeneracy conditions, the rate of convergence is linear.     

A Result on Vector Variational Inequalities with Polyhedral Constraint Sets

In this note, by using some well-known results on properly efficient solutions of vector optimization problems, we show that the Pareto solution set of a vector variational inequality with a polyhedral constraint set can be expressed as the union of the solution sets of a family of (scalar) variational inequalities.     

Lagrange multiplier rules for non-differentiable DC generalized semi-infinite programming problems

This paper aims to study a broad class of generalized semi-infinite programming problems with (upper and lower level) objectives given as the difference of two convex functions, and (lower level) constraints described by a finite number of convex inequalities and a set constraints. First, we are interested in some various lower level constraint qualifications for the problem. Then, the results are used to establish efficient upper estimate of certain subdifferential of value functions. Finally, we apply the obtained subdifferential estimates to derive necessary optimality conditions for the problem.     

Regularity properties of optimal controls for problems with time-varying state and control constraints

In this paper we report new results on the regularity of optimal controls for dynamic optimization problems with functional inequality state constraints, a convex time-dependent control constraint and a coercive cost function. Recently, it has been shown that the linear independence condition on active state constraints, present in the earlier literature, can be replaced by a less restrictive, positive linear independence condition, that requires linear independence merely with respect to non-negative weighting parameters, provided the control constraint set is independent of the time variable. We show that, if the control constraint set, regarded as a time-dependent multifunction, is merely Lipschitz continuous with respect to the time variable, then optimal controls can fail to be Lipschitz continuous. In these circumstances, however, a weaker Hölder continuity-like regularity property can be established. On the other hand, Lipschitz continuity of optimal controls is guaranteed for time-varying control sets under a positive linear independence hypothesis, when the control constraint sets are described, at each time, by a finite collection of functional inequalities.     

Metric regularity of the feasible set mapping in semi-infinite optimization

For parametric systems of (finitely many) equations and (infinitely many) inequalities the well-known concept of metric regularity is shown to be equivalent to the so-called extended Mangasarian-Fromovitz constraint qualification. By this, a corresponding result obtained by Robinson for finite optimization problems my be transferred to semi-infinite optimization. For the proof a local epigraph representation of the constraint set is mainly used.     

Primal and Dual Stability Results for Variational Inequalities

The purpose of this paper is to study the continuous dependence of solutions of variational inequalities with respect to perturbations of the data that are maximal monotone operators and closed convex functions. The constraint sets are defined by a finite number of linear equalities and non linear convex inequalities. Primal and dual stability results are given, extending the classical ones for optimization problems.     

Infinite dimensional duality and applications

The usual duality theory cannot be applied to infinite dimensional problems because the underlying constraint set mostly has an empty interior and the constraints are possibly nonlinear. In this paper we present an infinite dimensional nonlinear duality theory obtained by using new separation theorems based on the notion of quasi-relative interior, which, in all the concrete problems considered, is nonempty. We apply this theory to solve the until now unsolved problem of finding, in the infinite dimensional case, the Lagrange multipliers associated to optimization problems or to variational inequalities. As an example, we find the Lagrange multiplier associated to a general elastic–plastic torsion problem.