Enhancing RLT relaxations via a new class of semidefinite cuts

In this paper, we propose a mechanism to tighten Reformulation-Linearization Technique (RLT) based relaxations for solving nonconvex programming problems by importing concepts from semidefinite programming (SDP), leading to a new class of semidefinite cutting planes. Given an RLT relaxation, the usual nonnegativity restrictions on the matrix of RLT product variables is replaced by a suitable positive semidefinite constraint. Instead of relying on specific SDP solvers, the positive semidefinite stipulation is re-written to develop a semi-infinite linear programming representation of the problem, and an approach is developed that can be implemented using traditional optimization software. Specifically, the infinite set of constraints is relaxed, and members of this set are generated as needed via a separation routine in polynomial time. In essence, this process yields an RLT relaxation that is augmented with valid inequalities, which are themselves classes of RLT constraints that we call semidefinite cuts. These semidefinite cuts comprise a relaxation of the underlying semidefinite constraint. We illustrate this strategy by applying it to the case of optimizing a nonconvex quadratic objective function over a simplex. The algorithm has been implemented in C++, using CPLEX callable routines, and two types of semidefinite restrictions are explored along with several implementation strategies. Several of the most promising lower bounding strategies have been implemented within a branch-and-bound framework. Computational results indicate that the cutting plane algorithm provides a significant tightening of the lower bound obtained by using RLT alone. Moreover, when used within a branch-and-bound framework, the proposed lower bound significantly reduces the effort required to obtain globally optimal solutions.     

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.     

On the mixed integer signomial programming problems

This paper proposes an approximate method to solve the mixed integer signomial programming problem, for which the objective function and the constraints may contain product terms with exponents and decision variables, which could be continuous or integral. A linear programming relaxation is derived for the problem based on piecewise linearization techniques, which first convert a signomial term into the sum of absolute terms; these absolute terms are then linearized by linearization strategies. In addition, a novel approach is included for solving integer and undefined problems in the logarithmic piecewise technique, which leads to more usefulness of the proposed method. The proposed method could reach a solution as close as possible to the global optimum.     

求解非凸区域上凸函数比式和问题的全局优化方法

针对非凸区域上的凸函数比式和问题,给出一种求其全局最优解的确定性方法.该方法基于分支定界框架.首先通过引入变量,将原问题等价转化为d.c.规划问题,然后利用次梯度和凸包络构造松弛线性规划问题,从而将关键的估计下界问题转化为一系列线性规划问题,这些线性规划易于求解而且规模不变,更容易编程实现和应用到实际中;分支采用单纯形对分不但保证其穷举性,而且使得线性规划规模更小.理论分析和数值实验表明所提出的算法可行有效.     

Transcendental geometric programs

This paper treats a class of posynomial-like functions whose variables may appear also as exponents or in logarithms. It is shown that the resulting programs, called transcendental geometric programs, retain many useful properties of ordinary geometric programs, although the new class of problems need not have unique minima and cannot, in general, be transformed into convex programs. A duality theory, analogous to geometric programming duality, is formulated under somewhat more restrictive conditions. The dual constraints are not all linear, but the notion ofdegrees of difficulty is maintained in its geometric programming sense. One formulation of the dual program is shown to be a generalization of the chemical equilibrium problem where correction factors are added to account for nonideality. Some of the computational difficulties in solving transcendental programs are discussed briefly.This research was partially supported by the National Institute of Health Grant No. GM-14789; Office of Naval Research under Contract No. N00014-75-C-0276; National Science Foundation Grant No. MPS-71-03341 A03; and the US Atomic Energy Commission Contract No. AT(04-3)-326 PA #18.     

Computational schemes for large-scale problems in extended linear-quadratic programming

Numerical approaches are developed for solving large-scale problems of extended linear-quadratic programming that exhibit Lagrangian separability in both primal and dual variables simultaneously. Such problems are kin to large-scale linear complementarity models as derived from applications of variational inequalities, and they arise from general models in multistage stochastic programming and discrete-time optimal control. Because their objective functions are merely piecewise linear-quadratic, due to the presence of penalty terms, they do not fit a conventional quadratic programming framework. They have potentially advantageous features, however, which so far have not been exploited in solution procedures. These features are laid out and analyzed for their computational potential. In particular, a new class of algorithms, called finite-envelope methods, is described that does take advantage of the structure. Such methods reduce the solution of a high-dimensional extended linear-quadratic program to that of a sequence of low-dimensional ordinary quadratic programs.This work was supported in part by grants AFOSR 87-0821 and AFOSR 89-0081 from the Air Force Office of Scientific Research.     

Vector maximisation and lagrange multipliers

The Lagrangean function for scalar constrained optimisation problems is extended in a directly analogous manner to constrained vector optimisation problems. Some simple saddle point results are presented for vector maxima sets. Conditions are given for the characterisation of the vector maximum set of the original vector problem in terms of the vector maximum sets with respect to the vector Lagrangeans. Finally some attention is given to Lagrangean relaxation for vector optimisation problems as an extension of a result of Everett.     

Dynamic decision making for graphical models applied to oil exploration

We present a framework for sequential decision making in problems described by graphical models. The setting is given by dependent discrete random variables with associated costs or revenues. In our examples, the dependent variables are the potential outcomes (oil, gas or dry) when drilling a petroleum well. The goal is to develop an optimal selection strategy of wells that incorporates a chosen utility function within an approximated dynamic programming scheme. We propose and compare different approximations, from naive and myopic heuristics to more complex look-ahead schemes, and we discuss their computational properties. We apply these strategies to oil exploration over multiple prospects modeled by a directed acyclic graph, and to a reservoir drilling decision problem modeled by a Markov random field. The results show that the suggested strategies clearly improve the naive or myopic constructions used in petroleum industry today. This is useful for decision makers planning petroleum exploration policies.     

Computable bounds on parametric solutions of convex problems

We present a new method for computing bounds on parametric solutions of convex problems. The approach is based on a uniform quadratic underestimation of the objective function and a simple technique for the calculation of bounds on the optimal value function.Research supported by Grant ECS-8619859, National Science Foundation and Contract N00017-86-K-0052, Office of Naval Research.     

A unified framework for primal-dual methods in minimum cost network flow problems

We introduce a broad class of algorithms for finding a minimum cost flow in a capacitated network. The algorithms are of the primal-dual type. They maintain primal feasibility with respect to capacity constraints, while trying to satisfy the conservation of flow equation at each node by means of a wide variety of procedures based on flow augmentation, price adjustment, and ascent of a dual functional. The manner in which these procedures are combined is flexible thereby allowing the construction of algorithms that can be tailored to the problem at hand for maximum effectiveness. Particular attention is given to methods that incorporate features from classical relaxation procedures. Experimental codes based on these methods outperform by a substantial margin the fastest available primal-dual and primal simplex codes on standard benchmark problems.This work was supported by the National Science Foundation under Contract NSF/ECS 8217668.     

整数规划新进展

整数规划是对全部或部分决策变量为整数的最优化问题的模型、算法及应用等的研究, 是运筹学和管理科学中应用最广泛的优化模型之一. 首先简要回顾整数规划的历史和发展进程, 概述线性和非线性整数规划的一些经典方法. 然后着重讨论整数规划若干新进展, 包括0-1二次规划的半定规划~(SDP)~松弛和随机化方法, 带半连续变量和稀疏约束的优化问题的整数规划模型和方法, 以及0-1二次规划的协正锥规划表示和协正锥的层级半定规划~(SDP)~逼近. 最后, 对整数规划未来研究方向进行展望并对一些公开问题进行讨论.     

On multilevel iterative methods for optimization problems

This paper is concerned with multilevel iterative methods which combine a descent scheme with a hierarchy of auxiliary problems in lower dimensional subspaces. The construction of auxiliary problems as well as applications to elasto-plastic model and linear programming are described. The auxiliary problem for the dual of a perturbed linear program is interpreted as a dual of perturbed aggregated linear program. Coercivity of the objective function over the feasible set is sufficient for the boundedness of the iterates. Equivalents of this condition are presented in special cases.Supported by NSF under grant DMS-8704169, AFOSR under grant 86-0126, and ONR under Contract N00014-83-K-0104. Consulting for American Airlines Decision Technologies, MD 2C55, P.O. Box 619616, DFW, TX 75261-9616, USA.Supported by NSF under grant DMS-8704169 and AFOSR under grant 86-0126.     

On projected newton barrier methods for linear programming and an equivalence to Karmarkar’s projective method

Interest in linear programming has been intensified recently by Karmarkar’s publication in 1984 of an algorithm that is claimed to be much faster than the simplex method for practical problems. We review classical barrier-function methods for nonlinear programming based on applying a logarithmic transformation to inequality constraints. For the special case of linear programming, the transformed problem can be solved by a “projected Newton barrier” method. This method is shown to be equivalent to Karmarkar’s projective method for a particular choice of the barrier parameter. We then present details of a specific barrier algorithm and its practical implementation. Numerical results are given for several non-trivial test problems, and the implications for future developments in linear programming are discussed. The research of the Stanford authors was supported by the U.S. Department of Energy Contract DE-AA03-76SF00326, PA No. DE-AS03-76ER72018; National Science Foundation Grants DCR-8413211 and ECS-8312142; the Office of Naval Research Contract N00014-85-K-0343; and the U.S. Army Research Office Contract DAAG29-84-K-0156. The research of J.A. Tomlin was supported by Ketron, Inc. and the Office of Naval Research Contract N00014-85-C-0338.     

On Anstreicher's combined phase I—phase II projective algorithm for linear programming

Anstreicher has proposed a variant of Karmarkar's projective algorithm that handles standard-form linear programming problems nicely. We suggest modifications to his method that we suspect will lead to better search directions and a more useful algorithm. Much of the analysis depends on a two-constraint linear programming problem that is a relaxation of the scaled original problem.Research supported in part by NSF Grant ECS-8602534 and ONR Contract N00014-87-K-0212.     

Resolution method for mixed integer bi-level linear problems based on decomposition technique

In this article, we propose a new algorithm for the resolution of mixed integer bi-level linear problem (MIBLP). The algorithm is based on the decomposition of the initial problem into the restricted master problem (RMP) and a series of problems named slave problems (SP). The proposed approach is based on Benders decomposition method where in each iteration a set of variables are fixed which are controlled by the upper level optimization problem. The RMP is a relaxation of the MIBLP and the SP represents a restriction of the MIBLP. The RMP interacts in each iteration with the current SP by the addition of cuts produced using Lagrangian information from the current SP. The lower and upper bound provided from the RMP and SP are updated in each iteration. The algorithm converges when the difference between the upper and lower bound is within a small difference ε. In the case of MIBLP Karush–Kuhn–Tucker (KKT) optimality conditions could not be used directly to the inner problem in order to transform the bi-level problem into a single level problem. The proposed decomposition technique, however, allows the use of KKT conditions and transforms the MIBLP into two single level problems. The algorithm, which is a new method for the resolution of MIBLP, is illustrated through a modified numerical example from the literature. Additional examples from the literature are presented to highlight the algorithm convergence properties.     

A robust secant method for optimization problems with inequality constraints

This paper presents a secant method, based on R. B. Wilson's formula for the solution of optimization problems with inequality constraints. Global convergence properties are ensured by grafting the secant method onto a phase I - phase II feasible directions method, using a rate of convergence test for crossover control.This research was sponsored by the National Science Foundation, Grant No. ENG-73-08214 and Grant No. (RANN)-ENV-76-04264, and by the Joint Services Electronics Program. Contract No. F44620-76-C-0100.     

Least-cost network topology design for a new service

We describe an implementation of the tabu search metaheuristic that effectively finds a low-cost topology for a communications network to provide a centralized new service. Our results are compared to those of a greedy algorithm which applies corresponding decision rules, but without the guidance of the tabu search framework. These problems are difficult computationally, representing integer programs that can involve as many as 10,000 integer variables and 2000 constraints in practical applications. The tabu search results approach succeeded in obtaining significant improvements over the greedy approach, yielding optimal solutions to problems small enough to allow independent verification of optimality status and, more generally, yielding both absolute and percentage cost improvements that did not deteriorate with increasing problem size.This research was partially supported by the Air Force Office of Scientific Research and the Office of Naval Research Contract No. F49629-90-C-0033.     

Semidefinite programming in combinatorial optimization

We discuss the use of semidefinite programming for combinatorial optimization problems. The main topics covered include (i) the Lovász theta function and its applications to stable sets, perfect graphs, and coding theory, (ii) the automatic generation of strong valid inequalities, (iii) the maximum cut problem and related problems, and (iv) the embedding of finite metric spaces and its relationship to the sparsest cut problem. Part of this work is supported by NSF contract 9623859-CCR, a Sloan Foundation Fellowship, and ARPA Contract N00014-95-1-1246.     

Algorithms for bound constrained quadratic programming problems

Summary We present an algorithm which combines standard active set strategies with the gradient projection method for the solution of quadratic programming problems subject to bounds. We show, in particular, that if the quadratic is bounded below on the feasible set then termination occurs at a stationary point in a finite number of iterations. Moreover, if all stationary points are nondegenerate, termination occurs at a local minimizer. A numerical comparison of the algorithm based on the gradient projection algorithm with a standard active set strategy shows that on mildly degenerate problems the gradient projection algorithm requires considerable less iterations and time than the active set strategy. On nondegenerate problems the number of iterations typically decreases by at least a factor of 10. For strongly degenerate problems, the performance of the gradient projection algorithm deteriorates, but it still performs better than the active set method.Work supported in part by the Applied Mathematical Sciences subprogram of the Office of Energy Research of the U.S. Department of Energy under Contract W-31-109-Eng-38     

Discrete linear bilevel programming problem

In this paper, we analyze some properties of the discrete linear bilevel program for different discretizations of the set of variables. We study the geometry of the feasible set and discuss the existence of an optimal solution. We also establish equivalences between different classes of discrete linear bilevel programs and particular linear multilevel programming problems. These equivalences are based on concave penalty functions and can be used to design penalty function methods for the solution of discrete linear bilevel programs.Support of this work has been provided by the INIC (Portugal) under Contract 89/EXA/5, by INVOTAN, FLAD, and CCLA (Portugal), and by FCAR (Québec), NSERC, and DND-ARP (Canada).