A Semidefinite Programming Based Polyhedral Cut and Price Approach for the Maxcut Problem

We investigate solution of the maximum cut problem using a polyhedral cut and price approach. The dual of the well-known SDP relaxation of maxcut is formulated as a semi-infinite linear programming problem, which is solved within an interior point cutting plane algorithm in a dual setting; this constitutes the pricing (column generation) phase of the algorithm. Cutting planes based on the polyhedral theory of the maxcut problem are then added to the primal problem in order to improve the SDP relaxation; this is the cutting phase of the algorithm. We provide computational results, and compare these results with a standard SDP cutting plane scheme. Research supported in part by NSF grant numbers CCR–9901822 and DMS–0317323. Work done as part of the first authors Ph.D. dissertation at RPI.     

A comparison of computational strategies for geometric programs

Numerous algorithms for the solution of geometric programs have been reported in the literature. Nearly all are based on the use of conventional programming techniques specialized to exploit the characteristic structure of either the primal or the dual or a transformed primal problem. This paper attempts to elucidate, via computational comparisons, whether a primal, a dual, or a transformed primal solution approach is to be preferred.The authors wish to thank Captain P. A. Beck and Dr. R. S. Dembo for making available their codes. This research was supported in part under ONR Contract No. N00014-76-C-0551 with Purdue University.     

Primal cutting plane algorithms revisited

Dual fractional cutting plane algorithms, in which cutting planes are used to iteratively tighten a linear relaxation of an integer program, are well-known and form the basis of the highly successful branch-and-cut method. It is rather less well-known that various primal cutting plane algorithms were developed in the 1960s, for example by Young. In a primal algorithm, the main role of the cutting planes is to enable a feasible solution to the original problem to be improved. Research on these algorithms has been almost non-existent.  In this paper we argue for a re-examination of these primal methods. We describe a new primal algorithm for pure 0-1 problems based on strong valid inequalities and give some encouraging computational results. Possible extensions to the case of general mixed-integer programs are also discussed.     

Sensitivity analysis in geometric programming: Theory and computations

This paper surveys the main developments in the area of sensitivity analysis for geometric programming problems, including both the theoretical and computational aspects. It presents results which characterize solution existence, continuity, and differentiability properties for primal and dual geometric programs as well as the optimal value function differentiability properties for primal and dual programs. It also provides an overview of main computational approaches to sensitivity analysis in geometric programming which attempt to estimate new optimal solutions resulting from perturbations in some problem parameters.     

Sensitivity analysis in geometric programming

A unified approach to computing first, second, or higher-order derivatives of any of the primal and dual variables or multipliers of a geometric programming problem, with respect to any of the problem parameters (term coefficients, exponents, and constraint right-hand sides) is presented. Conditions under which the sensitivity equations possess a unique solution are developed, and ranging results are also derived. The analysis for approximating second and higher-order sensitivity generalizes to any sufficiently smooth nonlinear program.     

Posynomial geometric programming as a special case of semi-infinite linear programming

This paper develops a wholly linear formulation of the posynomial geometric programming problem. It is shown that the primal geometric programming problem is equivalent to a semi-infinite linear program, and the dual problem is equivalent to a generalized linear program. Furthermore, the duality results that are available for the traditionally defined primal-dual pair are readily obtained from the duality theory for semi-infinite linear programs. It is also shown that two efficient algorithms (one primal based and the other dual based) for geometric programming actually operate on the semi-infinite linear program and its dual.     

Deriving an unconstrained convex program for linear programming

Consider a linear programming problem in Karmarkar's standard form. By perturbing its linear objective function with an entropic barrier function and applying generalized geometric programming theory to it, Fang recently proposed an unconstrained convex programming approach to finding an epsilon-optimal solution. In this paper, we show that Fang's derivation of an unconstrained convex dual program can be greatly simplified by using only one simple geometric inequality. In addition, a system of nonlinear equations, which leads to a pair of primal and dual epsilon-optimal solutions, is proposed for further investigation.This work was partially supported by the North Carolina Supercomputing Center and a 1990 Cray Research Grant. The authors are indebted to Professors E. L. Peterson and R. Saigal for stimulating discussions.     

Convergent Lagrangian heuristics for nonlinear minimum cost network flows

We consider the separable nonlinear and strictly convex single-commodity network flow problem (SSCNFP). We develop a computational scheme for generating a primal feasible solution from any Lagrangian dual vector; this is referred to as “early primal recovery”. It is motivated by the desire to obtain a primal feasible vector before convergence of a Lagrangian scheme; such a vector is not available from a Lagrangian dual vector unless it is optimal. The scheme is constructed such that if we apply it from a sequence of Lagrangian dual vectors that converge to an optimal one, then the resulting primal (feasible) vectors converge to the unique optimal primal flow vector. It is therefore also a convergent Lagrangian heuristic, akin to those primarily devised within the field of combinatorial optimization but with the contrasting and striking advantage that it is guaranteed to yield a primal optimal solution in the limit. Thereby we also gain access to a new stopping criterion for any Lagrangian dual algorithm for the problem, which is of interest in particular if the SSCNFP arises as a subproblem in a more complex model. We construct instances of convergent Lagrangian heuristics that are based on graph searches within the residual graph, and therefore are efficiently implementable; in particular we consider two shortest path based heuristics that are based on the optimality conditions of the original problem. Numerical experiments report on the relative efficiency and accuracy of the various schemes.     

Generalized geometric programming applied to problems of optimal control: I. Theory

The interest in convexity in optimal control and the calculus of variations has gone through a revival in the past decade. In this paper, we extend the theory of generalized geometric programming to infinite dimensions in order to derive a dual problem for the convex optimal control problem. This approach transfers explicit constraints in the primal problem to the dual objective functional.The authors are indebted to the referees for suggestions leading to improvement of the paper.     

Sensitivity analysis in posynomial geometric programming

Sensitivity analysis results for general parametric posynomial geometric programs are obtained by utilizing recent results from nonlinear programming. Duality theory of geometric programming is exploited to relate the sensitivity results derived for primal and dual geometric programs. The computational aspects of sensitivity calculations are also considered.This work was part of the doctoral dissertation completed in the Department of Operations Research, George Washington University, Washington, DC. The author would like to express his gratitude to the thesis advisor, Prof. A. V. Fiacco, for overall guidance and stimulating discussions which inspired the development of this research work.     

A convergent criss-cross method

Our paper presents a new Criss-Cross method for solving linear programming problems. Starting from a neither primal nor dual feasible solution, we reach an optimal solution in finite number of steps if it exists. If there is no optimal solution, then we show that there is not primal feasible or dual feasible solution, We prove the finiteness of this procedure. Our procedure is not the same as the primal or dual simplex method if we have a primal or dual feasible solution, so we have constructed a quite new procedure for solving linear programming problems.     

A cutting plane method from analytic centers for stochastic programming

The stochastic linear programming problem with recourse has a dual block-angular structure. It can thus be handled by Benders' decomposition or by Kelley's method of cutting planes; equivalently the dual problem has a primal block-angular structure and can be handled by Dantzig-Wolfe decomposition—the two approaches are in fact identical by duality. Here we shall investigate the use of the method of cutting planes from analytic centers applied to similar formulations. The only significant difference form the aforementioned methods is that new cutting planes (or columns, by duality) will be generated not from the optimum of the linear programming relaxation, but from the analytic center of the set of localization.This research has been supported by the Fonds National de la Recherche Scientifique Suisse (grant # 12-26434.89), NSERC-Canada and FCAR-Quebec.Corresponding author.     

Controlled perturbations for quadratically constrained quadratic programs

Consider a minimization problem of a convex quadratic function of several variables over a set of inequality constraints of the same type of function. The duel program is a maximization problem with a concave objective function and a set of constrains that are essentially linear. However, the objective function is not differentiable over the constraint region. In this paper, we study a general theory of dual perturbations and derive a fundamental relationship between a perturbed dual program and the original problem. Based on this relationship, we establish a perturbation theory to display that a well-controlled perturbation on the dual program can overcome the nondifferentiability issue and generate an ε-optimal dual solution for an arbitrarily small number ε. A simple linear program is then constructed to make an easy conversion from the dual solution to a corresponding ε-optimal primal solution. Moreover, a numerical example is included to illustrate the potential of this controlled perturbation scheme.     

Augmented Lagrangian algorithms for linear programming

We introduce new augmented Lagrangian algorithms for linear programming which provide faster global convergence rates than the augmented algorithm of Polyak and Treti'akov. Our algorithm shares the same properties as the Polyak-Treti'akov algorithm in that it terminates in finitely many iterations and obtains both primal and dual optimal solutions. We present an implementable version of the algorithm which requires only approximate minimization at each iteration. We provide a global convergence rate for this version of the algorithm and show that the primal and dual points generated by the algorithm converge to the primal and dual optimal set, respectively.     

Accelerating column generation for variable sized bin-packing problems

In this paper, we study different strategies to stabilize and accelerate the column generation method, when it is applied specifically to the variable sized bin-packing problem, or to its cutting stock counterpart, the multiple length cutting stock problem. Many of the algorithms for these problems discussed in the literature rely on column generation, processes that are known to converge slowly due to primal degeneracy and the excessive oscillations of the dual variables. In the sequel, we introduce new dual-optimal inequalities, and explore the principle of model aggregation as an alternative way of controlling the progress of the dual variables. Two algorithms based on aggregation are proposed. The first one relies on a row aggregated LP, while the second one solves iteratively sequences of doubly aggregated models. Working with these approximations, in the various stages of an iterative solution process, has proven to be an effective way of achieving faster convergence.     

Primal—dual methods for linear programming

Many interior-point methods for linear programming are based on the properties of the logarithmic barrier function. After a preliminary discussion of the convergence of the (primal) projected Newton barrier method, three types of barrier method are analyzed. These methods may be categorized as primal, dual and primal—dual, and may be derived from the application of Newton's method to different variants of the same system of nonlinear equations. A fourth variant of the same equations leads to a new primal—dual method.In each of the methods discussed, convergence is demonstrated without the need for a nondegeneracy assumption or a transformation that makes the provision of a feasible point trivial. In particular, convergence is established for a primal—dual algorithm that allows a different step in the primal and dual variables and does not require primal and dual feasibility.Finally, a new method for treating free variables is proposed.Presented at the Second Asilomar Workshop on Progress in Mathematical Programming, February 1990, Asilomar, CA, United StatesThe material contained in this paper is based upon research supported by the National Science Foundation Grant DDM-9204208 and the Office of Naval Research Grant N00014-90-J-1242.     

Adding activities to the dual instead of cuts to the primal problem

When solving a problem by appending cuts the dimension of the corresponding simplex tableau and the basic inverse oscillates, which makes it difficult to implement a cutting plane algorithm based on a standard LP code. Moreover, it is complicated to express a cut in the original variables. In this paper we show that by formulating the dual to the problem and adding activities, these adverse effects can be circumvented. It is shown that the set of activities which can be added is the same as the set of cuts which can be appended and that it is easy to exhibit an activity in the original primal variables. As a consequence of this a new formulation of a cut in the original primal variables is given.     

A simple proof of a primal affine scaling method

In this paper, we present a simpler proof of the result of Tsuchiya and Muramatsu on the convergence of the primal affine scaling method. We show that the primal sequence generated by the method converges to the interior of the optimum face and the dual sequence to the analytic center of the optimal dual face, when the step size implemented in the procedure is bounded by 2/3. We also prove the optimality of the limit of the primal sequence for a slightly larger step size of 2q/(3q–1), whereq is the number of zero variables in the limit. We show this by proving the dual feasibility of a cluster point of the dual sequence.Partially supported by the grant CCR-9321550 from NSF.     

Recovering optimal dual solutions in Karmarkar's polynomial algorithm for linear programming

This paper presents a “standard form” variant of Karmarkar's algorithm for linear programming. The tecniques of using duality and cutting objective are combined in this variant to maintain polynomial-time complexity and to bypass the difficulties found in Karmarkar's original algorithm. The variant works with problems in standard form and simultaneously generates sequences of primal and dual feasible solutions whose objective function values converge to the unknown optimal value. Some computational results are also reported.     

Selective Gram–Schmidt orthonormalization for conic cutting surface algorithms

It is not straightforward to find a new feasible solution when several conic constraints are added to a conic optimization problem. Examples of conic constraints include semidefinite constraints and second order cone constraints. In this paper, a method to slightly modify the constraints is proposed. Because of this modification, a simple procedure to generate strictly feasible points in both the primal and dual spaces can be defined. A second benefit of the modification is an improvement in the complexity analysis of conic cutting surface algorithms. Complexity results for conic cutting surface algorithms proved to date have depended on a condition number of the added constraints. The proposed modification of the constraints leads to a stronger result, with the convergence of the resulting algorithm not dependent on the condition number. Research supported in part by NSF grant number DMS-0317323. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the National Science Foundation.