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

    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

    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

    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

    An (\sqrt{n}\log \frac{(x^0)^Ts^0}{\epsilon})$ iteration primal-dual path-following method, based on wide neighborhoods and large updates, for monotone linear complementarity problems

  • Wenbao Ai
  • Shuzhong Zhang
    • Categories Linear, Cone and Semidefinite Programming Tags , ,

    In this paper we propose a new class of primal-dual path-following interior point algorithms for solving monotone linear complementarity problems. At each iteration, the method would select a target on the central path with a large update from the current iterate, and then the Newton method is used to get the search directions, followed by … Read more

    Cover Inequalities for Binary-Integer Knapsack Constraints

  • Miguel A. Lejeune
  • Andrzej Ruszczyński
    • Categories (Mixed) Integer Linear Programming, Integer Programming Tags , , , ,

    We consider knapsack constraints involving one general integer and many binary variables. We introduce the concept of a cover for such a constraint and we construct a new family of valid inequalities based on this concept. We generalize this idea to extended covers, and we propose a specialized lifting procedure for cover inequalities. Finally, we … Read more

    Conditional Risk Mappings

  • Andrzej Ruszczyński
  • Alexander Shapiro
    • Categories Finance and Economics, Stochastic Programming Tags , , , , ,

    We introduce an axiomatic definition of a conditional convex risk mapping and we derive its properties. In particular, we prove a representation theorem for conditional risk mappings in terms of conditional expectations. We also develop dynamic programming relations for multistage optimization problems involving conditional risk mappings. CitationPreprintArticleDownload View PDF