Simple bounds for solutions of monotone complementarity problems and convex programs

For a solvable monotone complementarity problem we show that each feasible point which is not a solution of the problem provides simple numerical bounds for some or all components of all solution vectors. Consequently for a solvable differentiable convex program each primal-dual feasible point which is not optimal provides simple bounds for some or all components of all primal-dual solution vectors. We also give an existence result and simple bounds for solutions of monotone compementarity problems satisfying a new, distributed constraint qualification. This result carries over to a simple existence and boundedness result for differentiable convex programs satisfying a similar constraint qualification.Sponsored by the United States Army under Contract No. DAAG29-80-C-0041. This material is based on work sponsored by National Science Foundation Grants MCS-8200632 and MCS-8102684.     

Solving large-scale mixed-integer programs with fixed charge variables

We consider large-scale mixed-integer programming problems containing fixed charge variables. In practice such problems are frequently approached by using commercial mathematical programming systems. Depending on the formulation, size and structure of the problem this approach may or may not be successful. We describe algorithms for preprocessing and optimization of such problems and discuss the design of an experimental software system based on MPSX/370. Numerical results for solving some large real life problems are also presented.     

Applications of the method of partial inverses to convex programming: Decomposition

A primal–dual decomposition method is presented to solve the separable convex programming problem. Convergence to a solution and Lagrange multiplier vector occurs from an arbitrary starting point. The method is equivalent to the proximal point algorithm applied to a certain maximal monotone multifunction. In the nonseparable case, it specializes to a known method, the proximal method of multipliers. Conditions are provided which guarantee linear convergence.This research was sponsored, in part, by the Air Force Office of Scientific Research under grant 80-0195.     

Rational solutions of the graphsack problem

A graphsack problem is a certain binary linear optimization problem with applications in optimal network design. From there a rational graphsack problem is derived by allowing the variables to vary continuously between 0 and 1. In this paper we deal with rational graphsack problems. First we develop the concept of compressed solutions and the concept of augmenting cuts. Making use of these concepts a very simple optimality criterion is derived. Finally an efficient algorithm solving rational graphsack problems is given which is polynomially bounded in time and which is closely related to the simplex algorithm.     

A hybrid approach to discrete mathematical programming

The dynamic programming and branch-and-bound approaches are combined to produce a hybrid algorithm for separable discrete mathematical programs. Linear programming is used in a novel way to compute bounds. Every simplex pivot permits a bounding test to be made on every active node in the search tree. Computational experience is reported.     

The complementary unboundedness of dual feasible solution sets in convex programming

F.E. Clark has shown that if at least one of the feasible solution sets for a pair of dual linear programming problems is nonempty then at least one of them is both nonempty and unbounded. Subsequently, M. Avriel and A.C. Williams have obtained the same result in the more general context of (prototype posynomial) geometric programming. In this paper we show that the same result is actually false in the even more general context of convex programming — unless a certain regularity condition is satisfied.We also show that the regularity condition is so weak that it is automatically satisfied in linear programming (prototype posynomial) geometric programming, quadratic programming (with either linear or quadratic constraints),l _p -regression analysis, optimal location, roadway network analysis, and chemical equilibrium analysis. Moreover, we develop an equivalent regularity condition for each of the usual formulations of duality.Research sponsored by the Air Force Office of Scientific Research, Air Force Systems Command, USAF, under Grant Number AFOSR-73-2516.     

Tracking elementary particles near their primary vertex: A combinatorial approach

Colliding beams experiments in High Energy Physics rely on solid state detectors to track the flight paths of charged elementary particles near their primary point of interaction. Reconstructing tracks in this region requires, per collision, a partitioning of up to 10³ highly correlated observations into an unknown number of tracks. We report on the successful implementation of a combinatorial track finding algorithm to solve this pattern recognition problem in the context of the ALEPH experiment at CERN. Central to the implementation is a 5-dimensional axial assignment model (AP5) encompassing noise and inefficiencies of the detector, whose weights of assignments are obtained by means of an extended Kalman filter. A preprocessing step, involving the clustering and geometric partitioning of the observations, ensures reasonable bounds on the size of the problems, which are solved using a branch & bound algorithm with LP relaxation. Convergence is reached within one second of CPU time on a RISC workstation in average.     

非光滑半无限多目标规划弱非控解的充分性

本文利用锥次微分的概念，在一点处定义了η－（Ａ，Ｎ）凸函数、η－（Ａ，Ｎ）伪凸函数和η－（Ａ，Ｎ）严格伪凸函数，在相当弱的假设下，在η－（Ａ，Ｎ）意义下，给出了非光滑η－（Ａ，Ｎ）凸半无限多目标规划弱非控解的一些充分条件。     

Solving staircase linear programs by the simplex method, 2: Pricing

This and a companion paper consider how current implementations of the simplex method may be adapted to better solve linear programs that have a staged, or ‘staircase’, structure. The preceding paper considered ‘inversion’ routines that factorize the basis and solve linear systems. The present paper examines ‘pricing’ routines that compute reduced costs for nonbasic variables and that select a variable to enter the basis at each iteration. Both papers describe extensive (although preliminary) computer experiments, and can point to some quite promising results. For pricing in particular, staircase computation strategies appear to offer modest but consistent savings; staircase selection strategies, properly chosen, may offer substantial savings in number of iterations, time per iteration, or both.     

On optimality conditions for structured families of nonlinear programming problems

Optimality conditions for families of nonlinear programming problems inR ⁿ are studied from a generic point of view. The objective function and some of the constraints are assumed to depend on a parameter, while others are held fixed. Techniques of differential topology are used to show that under suitable conditions, certain strong second-order conditions are necessary for optimality except possibly for parameter values lying in a negligible set.Research sponsored, in part, by the Air Force Office of Scientific Research, under grants number 77-3204 and 79-0120.