A cutting plane algorithm for convex programming that uses analytic centers

Anoracle for a convex setS ⁿ accepts as input any pointz in ⁿ , and ifz S, then it returns yes, while ifz S, then it returns no along with a separating hyperplane. We give a new algorithm that finds a feasible point inS in cases where an oracle is available. Our algorithm uses the analytic center of a polytope as test point, and successively modifies the polytope with the separating hyperplanes returned by the oracle. The key to establishing convergence is that hyperplanes judged to be unimportant are pruned from the polytope. If a ball of radius 2^–L is contained inS, andS is contained in a cube of side 2 ^L+1, then we can show our algorithm converges after O(nL ²) iterations and performs a total of O(n ⁴ L ³+TnL ²) arithmetic operations, whereT is the number of arithmetic operations required for a call to the oracle. The bound is independent of the number of hyperplanes generated in the algorithm. An important application in which an oracle is available is minimizing a convex function overS. Supported by the National Science Foundation under Grant CCR-9057481PYI.Supported by the National Science Foundation under Grants CCR-9057481 and CCR-9007195.     

Complexity of some cutting plane methods that use analytic centers

We consider cutting plane methods for minimizing a convex (possibly nondifferentiable) function subject to box constraints. At each iteration, accumulated subgradient cuts define a polytope that localizes the minimum. The objective and its subgradient are evaluated at the analytic center of this polytope to produce one or two cuts that improve the localizing set. We give complexity estimates for several variants of such methods. Our analysis is based on the works of Goffin, Luo and Ye. Research supported by the State Committee for Scientific Research under Grant 8S50502206.     

A logarithmic barrier cutting plane method for convex programming

The paper presents a logarithmic barrier cutting plane algorithm for convex (possibly non-smooth, semi-infinite) programming. Most cutting plane methods, like that of Kelley, and Cheney and Goldstein, solve a linear approximation (localization) of the problem and then generate an additional cut to remove the linear program's optimal point. Other methods, like the central cutting plane methods of Elzinga-Moore and Goffin-Vial, calculate a center of the linear approximation and then adjust the level of the objective, or separate the current center from the feasible set. In contrast to these existing techniques, we develop a method which does not solve the linear relaxations to optimality, but rather stays in the interior of the feasible set. The iterates follow the central path of a linear relaxation, until the current iterate either leaves the feasible set or is too close to the boundary. When this occurs, a new cut is generated and the algorithm iterates. We use the tools developed by den Hertog, Roos and Terlaky to analyze the effect of adding and deleting constraints in long-step logarithmic barrier methods for linear programming. Finally, implementation issues and computational results are presented. The test problems come from the class of numerically difficult convex geometric and semi-infinite programming problems.This work was completed under the support of a research grant of SHELL.On leave from the Eötvös University, Budapest, and partially supported by OTKA No. 2116.     

Accelerating convergence of cutting plane algorithms for disjoint bilinear programming

This paper presents two linear cutting plane algorithms that refine existing methods for solving disjoint bilinear programs. The main idea is to avoid constructing (expensive) disjunctive facial cuts and to accelerate convergence through a tighter bounding scheme. These linear programming based cutting plane methods search the extreme points and cut off each one found until an exhaustive process concludes that the global minimizer is in hand. In this paper, a lower bounding step is proposed that serves to effectively fathom the remaining feasible region as not containing a global solution, thereby accelerating convergence. This is accomplished by minimizing the convex envelope of the bilinear objective over the feasible region remaining after introduction of cuts. Computational experiments demonstrate that augmenting existing methods by this simple linear programming step is surprisingly effective at identifying global solutions early by recognizing that the remaining region cannot contain an optimal solution. Numerical results for test problems from both the literature and an application area are reported.     

Complexity analysis of the analytic center cutting plane method that uses multiple cuts

We analyze the complexity of the analytic center cutting plane or column generation algorithm for solving general convex problems defined by a separation oracle. The oracle is called at the analytic center of a polytope, which contains a solution set and is given by the intersection of the linear inequalities previously generated from the oracle. If the center is not in the solution set, separating hyperplanes will be placed through the center to shrink the containing polytope. While the complexity result has been recently established for the algorithm when one cutting plane is placed in each iteration, the result remains open when multiple cuts are added. Moreover, adding multiple cuts actually is a key to practical effectiveness in solving many problems and it presents theoretical difficulties in analyzing cutting plane methods. In this paper, we show that the analytic center cutting plane algorithm, with multiple cuts added in each iteration, still is a fully polynomial approximation algorithm. The research of the author is supported by NSF grant DDM-9207347, an Iowa Business School Summer Grant, and a University of Iowa Obermann Fellowship.     

A finite cutting plane method for facial disjunctive programs

This paper shows that any linear disjunctive program with a finite number of constraints can be transformed into an equivalent facial program. Based upon linear programming technique, a new, finite cutting plane method is presented for the facial programs.

---

Zusammenfassung Die Arbeit zeigt, daß jedes lineare disjunktive Optimierungsproblem mit endlich vielen Restriktionen in ein äquivalentes Fazetten-Problem transformiert werden kann. Auf der Grundlage von linearer Optimierungstechnik wird für das Fazetten-Problem ein neues, endliches Schnittebenenverfahren vorgestellt.

     

Complexity estimates of some cutting plane methods based on the analytic barrier

In this paper we establish the efficiency estimates for two cutting plane methods based on the analytic barrier. We prove that the rate of convergence of the second method is optimal uniformly in the number of variables. We present a modification of the second method. In this modified version each test point satisfies an approximate centering condition. We also use the standard strategy for updating approximate Hessians of the logarithmic barrier function. We prove that the rate of convergence of the modified scheme remains optimal and demonstrate that the number of Newton steps in the auxiliary minimization processes is bounded by an absolute constant. We also show that the approximate Hessian strategy significantly improves the total arithmetical complexity of the method.     

A polynomial method of approximate centers for linear programming

We present a path-following algorithm for the linear programming problem with a surprisingly simple and elegant proof of its polynomial behaviour. This is done both for the problem in standard form and for its dual problem. We also discuss some implementation strategies.This author completed this work under the support of the research grant No. 1467086 of the Fonds National Suisses de la Recherche Scientifique.     

A multivariate adaptive regression splines cutting plane approach for solving a two-stage stochastic programming fleet assignment model

The fleet assignment model assigns a fleet of aircraft types to the scheduled flight legs in an airline timetable published six to twelve weeks prior to the departure of the aircraft. The objective is to maximize profit. While costs associated with assigning a particular fleet type to a leg are easy to estimate, the revenues are based upon demand, which is realized close to departure. The uncertainty in demand makes it challenging to assign the right type of aircraft to each flight leg based on forecasts taken six to twelve weeks prior to departure. Therefore, in this paper, a two-stage stochastic programming framework has been developed to model the uncertainty in demand, along with the Boeing concept of demand driven dispatch to reallocate aircraft closer to the departure of the aircraft. Traditionally, two-stage stochastic programming problems are solved using the L-shaped method. Due to the slow convergence of the L-shaped method, a novel multivariate adaptive regression splines cutting plane method has been developed. The results obtained from our approach are compared to that of the L-shaped method, and the value of demand-driven dispatch is estimated.     

A cutting plane algorithm for graph coloring

We present an approach based on integer programming formulations of the graph coloring problem. Our goal is to develop models that remove some symmetrical solutions obtained by color permutations. We study the problem from a polyhedral point of view and determine some families of facets of the 0/1-polytope associated with one of these integer programming formulations. The theoretical results described here are used to design an efficient Cutting Plane algorithm.     

Continuous cutting plane algorithms in integer programming

Cutting planes for mixed-integer linear programs (MILPs) are typically computed in rounds by iteratively solving optimization problems, the so-called separation. Instead, we reframe the problem of finding good cutting planes as a continuous optimization problem over weights parametrizing families of valid inequalities. This problem can also be interpreted as optimizing a neural network to solve an optimization problem over subadditive functions, which we call the subadditive primal problem of the MILP. To do so, we propose a concrete two-step algorithm, and demonstrate empirical gains when optimizing generalized Gomory mixed-integer inequalities over various classes of MILPs. Code for reproducing the experiments can be found at https://github.com/dchetelat/subadditive.     

Finite master programs in regularized stochastic decomposition

Stochastic decomposition is a stochastic analog of Benders' decomposition in which randomly generated observations of random variables are used to construct statistical estimates of supports of the objective function. In contrast to deterministic Benders' decomposition for two stage stochastic programs, the stochastic version requires infinitely many inequalities to ensure convergence. We show that asymptotic optimality can be achieved with a finite master program provided that a quadratic regularizing term is included. Our computational results suggest that the elimination of the cutting planes impacts neither the number of iterations required nor the statistical properties of the terminal solution.This work was supported in part by Grant No. AFOSR-88-0076 from the Air Force Office of Scientific Research and Grant Nos. DDM-89-10046, DDM-9114352 from the National Science Foundation.Corresponding author.     

Generalized fractional programming and cutting plane algorithms

In this paper, we introduce a variant of a cutting plane algorithm and show that this algorithm reduces to the well-known Dinkelbach-type procedure of Crouzeix, Ferland, and Schaible if the optimization problem is a generalized fractional program. By this observation, an easy geometrical interpretation of one of the most important algorithms in generalized fractional programming is obtained. Moreover, it is shown that the convergence of the Dinkelbach-type procedure is a direct consequence of the properties of this cutting plane method. Finally, a class of generalized fractional programs is considered where the standard positivity assumption on the denominators of the ratios of the objective function has to be imposed explicitly. It is also shown that, when using a Dinkelbach-type approach for this class of programs, the constraints ensuring the positivity on the denominators can be dropped.The authors like to thank the anonymous referees and Frank Plastria for their constructive remarks on an earlier version of this paper.This research was carried out at Erasmus University, Rotterdam, The Netherlands and was supported by JNICT, Lisboa, Portugal, under Contract BD/707/90-RM.     

A decomposition-based solution method for stochastic mixed integer nonlinear programs

This is a summary of the main results presented in the author’s PhD thesis, supervised by D. Conforti and P. Beraldi and defended on March 2005. The thesis, written in English, is available from the author upon request. It describes one of the very few existing implementations of a method for solving stochastic mixed integer nonlinear programming problems based on deterministic global optimization. In order to face the computational challenge involved in the solution of such multi-scenario nonconvex problems, a branch and bound approach is proposed that exploits the peculiar structure of stochastic programming problem.     

A stochastic programming model for scheduling call centers with global Service Level Agreements

We consider the issue of call center scheduling in an environment where arrivals rates are highly variable, aggregate volumes are uncertain, and the call center is subject to a global service level constraint. This paper is motivated by work with a provider of outsourced technical support services where call volumes exhibit significant variability and uncertainty. The outsourcing contract specifies a Service Level Agreement that must be satisfied over an extended period of a week or month. We formulate the problem as a mixed-integer stochastic program. Our model has two distinctive features. Firstly, we combine the server sizing and staff scheduling steps into a single optimization program. Secondly, we explicitly recognize the uncertainty in period-by-period arrival rates. We show that the stochastic formulation, in general, calculates a higher cost optimal schedule than a model which ignores variability, but that the expected cost of this schedule is lower. We conduct extensive experimentation to compare the solutions of the stochastic program with the deterministic programs, based on mean valued arrivals. We find that, in general, the stochastic model provides a significant reduction in the expected cost of operation. The stochastic model also allows the manager to make informed risk management decisions by evaluating the probability that the Service Level Agreement will be achieved.     

Using the analytic center in the feasibility pump

The feasibility pump (FP) has proved to be a successful heuristic for finding feasible solutions of mixed integer linear problems. Briefly, FP alternates between two sequences of points: one of feasible solutions for the relaxed problem, and another of integer points. This short paper extends FP, such that the integer point is obtained by rounding a point on the (feasible) segment between the computed feasible point and the analytic center for the relaxed linear problem.     

Analysis of stochastic dual dynamic programming method

In this paper we discuss statistical properties and convergence of the Stochastic Dual Dynamic Programming (SDDP) method applied to multistage linear stochastic programming problems. We assume that the underline data process is stagewise independent and consider the framework where at first a random sample from the original (true) distribution is generated and consequently the SDDP algorithm is applied to the constructed Sample Average Approximation (SAA) problem. Then we proceed to analysis of the SDDP solutions of the SAA problem and their relations to solutions of the “true” problem. Finally we discuss an extension of the SDDP method to a risk averse formulation of multistage stochastic programs. We argue that the computational complexity of the corresponding SDDP algorithm is almost the same as in the risk neutral case.     

The long-step method of analytic centers for fractional problems

We develop a long-step surface-following version of the method of analytic centers for the fractional-linear problem min{t ₀ |t ₀ B(x) −A(x) εH, B(x) εK, x εG}, whereH is a closed convex domain,K is a convex cone contained in the recessive cone ofH, G is a convex domain andB(·),A(·) are affine mappings. Tracing a two-dimensional surface of analytic centers rather than the usual path of centers allows to skip the initial “centering” phase of the path-following scheme. The proposed long-step policy of tracing the surface fits the best known overall polynomial-time complexity bounds for the method and, at the same time, seems to be more attractive computationally than the short-step policy, which was previously the only one giving good complexity bounds. The research was partly supported by the Israeli-American Binational Science Foundation (BSF).     

A cutting plane algorithm for MV portfolio selection model

This paper deals with a portfolio selection problem with fuzzy return rates. A possibilistic mean variance (FMVC) portfolio selection model was proposed. The possibilistic programming problem can be transformed into a linear optimal problem with an additional quadratic constraint by possibilistic theory. For such problems there are no special standard algorithms. We propose a cutting plane algorithm to solve (FMVC). The nonlinear programming problem can be solved by sequence linear programming problem. A numerical example is given to illustrate the behavior of the proposed model and algorithm.