The purpose of this note is to present a robust counterpart of the Huber estimation problem in the sense of Ben-Tal and Nemirovski when the data elements are subject to ellipsoidal uncertainty. The robust counterparts are polynomially solvable second-order cone programs with the strong duality property. We illustrate the effectiveness of the robust counterpart approach … Read more
The basic principle of the cutting plane techniques is to chop away the portions of the solution space of the linear programming relaxation of an integer program that contain no integer solutions. this is true for both Gomory’s cutting planes, and other more recent cuts based on valid inequalities. Obtaining a partial or full description … Read more
SOSTOOLS is a free MATLAB toolbox for formulating and solving sum of squares (SOS) optimization programs. It uses a simple notation and a flexible and intuitive high-level user interface to specify the SOS programs. Currently these are solved using SeDuMi, a well-known semidefinite programming solver, while SOSTOOLS handles internally all the necessary reformulations and data … Read more
This paper deals with the application of pattern search methods to the numerical solution of a class of molecular geometry problems with important applications in molecular physics and chemistry. The goal is to find a configuration of a cluster or a molecule with minimum total energy. The minimization problems in this class of geometry molecular … Read more
The purpose of the traffic assignment problem is to obtain a traffic flow pattern given a set of origin-destination travel demands and flow dependent link performance functions of a road network. In the general case, the traffic assignment problem can be formulated as a variational inequality, and several algorithms have been devised for its efficient … Read more
We begin with a study of the infeasibility measures for linear programming problems. For this purpose, we consider feasibility problems in Karmarkar’s standard form. Our main focus is on the complexity measures which can be used to bound the amount of computational effort required to solve systems of linear inequalities and related problems in certain … Read more
We present a lagrangean heuristic based on the time-indexed formulation of the Single Machine Scheduling Problem with Release Dates. We observe that lagrangian relaxation of job constraints leads to a Weighted Stable Set problem on an Interval Graph. The problem is polynomially solvable by a dynamic programming algorithm. Computational experience is reported on instances up … Read more
In one of fundamental work in combinatorial optimization Edmonds gave a complete linear description of the matching polytope. Matchings in a graph are equivalent to stable sets its line graph. Also the neighborhood of any vertex in a line graph partitions into two cliques: graphs with this latter property are called quasi-line graphs. Quasi-line graphs … Read more
Non-smoothness and non-convexity in optimization problems often arise because a combinatorial structure is imposed on smooth or convex data. The combinatorial aspect can be explicit, e.g. through the use of ”max”, ”min”, or ”if” statements in a model, or implicit as in the case of bilevel optimization where the combinatorial structure arises from the possible … Read more
Recently, it has been shown that Nonlinear Programming solvers can successfully solve a range of Mathematical Programs with Equilibrium Constraints (MPECs). In particular, Sequential Quadratic Programming (SQP) methods have been very successful. This paper examines the local convergence properties of SQP methods applied to MPECs. It is shown that SQP converges superlinearly under reasonable assumptions … Read more