Month: March 2004

On the Implementation of an Interior-Point Filter Line-Search Algorithm for Large-Scale Nonlinear Programming

  • Andreas Wächter
  • Lorenz T. Biegler
    • Categories Constrained Nonlinear Optimization

    We present a primal-dual interior-point algorithm with a filter line-search method for nonlinear programming. Local and global convergence properties of this method were analyzed in previous work. Here we provide a comprehensive description of the algorithm, including the feasibility restoration phase for the filter method, second-order corrections, and inertia correction of the KKT matrix. Heuristics … Read more

    Fortran subroutines for network flow optimization using an interior point algorithm

  • Joaquim J. Júdice
  • João Patrício
  • Luis F. Portugal
  • Mauricio G.C. Resende
  • Geraldo Veiga
    • Categories Network Optimization, Optimization Software and Modeling Systems Tags , ,

    We describe FORTRAN subroutines for network flow optimization using an interior point network flow algorithm. We provide FORTRAN and C language drivers, as well as C language functions that, together with the subroutines, make up PDNET (Portugal, Resende, Veiga, and Júdice, 2000). The algorithm is described in detail and its implementation is outlined. Usage of … Read more

    Dual Convergence of the Proximal Point Method with Bregman Distances for Linear Programming

  • João Xavier da Cruz Neto
  • Orizon Pereira Ferreira
  • Renato D.C. Monteiro
  • A. N. Iusem
    • Categories Convex and Nonsmooth Optimization, Convex Optimization, Linear Programming Tags , , , , , , ,

    In this paper we consider the proximal point method with Bregman distance applied to linear programming problems, and study the dual sequence obtained from the optimal multipliers of the linear constraints of each subproblem. We establish the convergence of this dual sequence, as well as convergence rate results for the primal sequence, for a suitable … Read more

    An annotated bibliography of GRASP

  • Paola Festa
  • Mauricio G.C. Resende
    • Categories Applications - OR and Management Sciences, Meta Heuristics Tags , , , ,

    This paper presents an annotated bibliography of greedy randomized adaptive search procedures (GRASP). The bibliography is current up to early 2004. The bibliography contains: background material; tutorials and surveys; enhancements to the basic method; hybrid methods; software; parallel GRASP; graph theory; quadratic and other assignment problems; location, layout, and cutting; covering, clustering, packing, and partitioning; … Read more

    An Efficient Interior-Point Method for Convex Multicriteria Optimization Problems

  • Jörg Fliege
    • Categories Convex Optimization, Multi-Criteria Optimization Tags , , , ,

    In multicriteria optimization, several objective functions, conflicting with each other, have to be minimized simultaneously. We propose a new efficient method for approximating the solution set of a multiobjective programming problem, where the objective functions involved are arbitary convex functions and the set of feasible points is convex. The method is based on generating warm-start … Read more

    Unification of lower-bound analyses of the lift-and-project rank of combinatorial optimization polyhedra

  • Sung-Pil Hong
  • Levent Tunçel
    • Categories 0-1 Programming, Semi-definite Programming Tags , , ,

    We present a unifying framework to establish a lower-bound on the number of semidefinite programming based, lift-and-project iterations (rank) for computing the convex hull of the feasible solutions of various combinatorial optimization problems. This framework is based on the maps which are commutative with the lift-and-project operators. Some special commutative maps were originally observed by … Read more

    Optimal Pricing Policies for Perishable Products

  • Miguel F. Anjos
  • Russell C H Cheng
  • Christine S M Currie
    • Categories Airline Optimization, Applications - OR and Management Sciences, Yield Management Tags , , , ,

    In many industrial settings, managers face the problem of establishing a pricing policy that maximizes the revenue from selling a given inventory of items by a fixed deadline, with the full inventory of items being available for sale from the beginning of the selling period. This problem arises in a variety of industries, including the … Read more