Month: March 2018

Superiorization and perturbation resilience of algorithms: A continuously updated bibliography

  • Yair Censor
    • Categories Biomedical Applications, Constrained Nonlinear Optimization Tags ,

    This document presents a, chronologically ordered, bibliography of scientific publications on the superiorization methodology and perturbation resilience of algorithms which is compiled and continuously updated by us at: http://math.haifa.ac.il/yair/bib-superiorization-censor.html. Since the topic is relatively new it is possible to trace the work that has been published about it since its inception. To the best of … Read more

    Approximation Algorithms for D-optimal Design

  • Mohit Singh
  • Weijun Xie
    • Categories Combinatorial Optimization

    Experimental design is a classical statistics problem and its aim is to estimate an unknown m-dimensional vector from linear measurements where a Gaussian noise is introduced in each measurement. For the combinatorial experimental design problem, the goal is to pick k out of the given n experiments so as to make the most accurate estimate … Read more

    Outer Approximation for Integer Nonlinear Programs via Decision Diagrams

  • Danial Davarnia
  • Willem-Jan van Hoeve
    • Categories (Mixed) Integer Nonlinear Programming, Cutting Plane Approaches, Dynamic Programming Tags , , , ,

    As an alternative to traditional integer programming (IP), decision diagrams (DDs) provide a new solution technology for discrete problems based on their combinatorial structure and dynamic programming representation. While the literature mainly focuses on the competitive aspects of DDs as a stand-alone solver, we investigate their complementary role by studying IP techniques that can be … Read more

    Strong Convex Nonlinear Relaxations of the Pooling Problem

  • Claudia D'Ambrosio
  • Jeff Linderoth
  • James R. Luedtke
  • Jonas Schweiger
    • Categories Chemical Engineering, Cutting Plane Approaches, Global Optimization Tags , ,

    We investigate new convex relaxations for the pooling problem, a classic nonconvex production planning problem in which input materials are mixed in intermediate pools, with the outputs of these pools further mixed to make output products meeting given attribute percentage requirements. Our relaxations are derived by considering a set which arises from the formulation by … Read more

    Branch-Cut-and-Price for the Vehicle Routing Problem with Time Windows and Convex Node Costs

  • Qie He
  • Yongjia Song
  • Stefan Irnich
    • Categories Transportation Tags , , , ,

    Two critical yet frequently conflicting objectives for logistics and transportation service companies are improving customer satisfaction and reducing transportation cost. In particular, given a net- work of customer requests with preferred service times, it is very challenging to find vehicle routes and service schedules simultaneously that respect all operating constraints and minimize the total transportation … Read more

    A Newton-CG Algorithm with Complexity Guarantees for Smooth Unconstrained Optimization

  • Michael J. O'Neill
  • ClĂ©ment W. Royer
  • Stephen Wright
    • Categories Unconstrained Optimization Tags , , ,

    We consider minimization of a smooth nonconvex objective function using an iterative algorithm based on Newton’s method and linear conjugate gradient, with explicit detection and use of negative curvature directions for the Hessian of the objective function. The algorithm tracks Newton-conjugate gradient procedures developed in the 1980s closely, but includes enhancements that allow worst-case complexity … Read more

    A comparison of methods for traversing non-convex regions in optimization problems

  • Michael Bartholomew-Biggs
  • Salah Beddiaf
  • Bruce Christianson
    • Categories Unconstrained Optimization Tags , ,

    This paper considers again the well-known problem of dealing with non-convex regions during the minimization of a nonlinear function F(x) by Newton-like methods. The proposal made here involves a curvilinear search along an approximation to the continuous steepest descent path defined by the solution of the ODE dx/dt = -grad F(x). The algorithm we develop … Read more

    A finite ε-convergence algorithm for two-stage convex 0-1 mixed-integer nonlinear stochastic programs with mixed-integer first and second stage variables

  • Ignacio E. Grossmann
  • Can Li
    • Categories Stochastic Programming Tags , , ,

    In this paper, we propose a generalized Benders decomposition-based branch and bound algorithm, GBDBAB, to solve two-stage convex 0-1 mixed-integer nonlinear stochastic programs with mixed-integer variables in both first and second stage decisions. In order to construct the convex hull of the MINLP subproblem for each scenario in closed-form, we first represent each MINLP subproblem … Read more

    Exploring the Numerics of Branch-and-Cut for Mixed Integer Linear Optimization

  • Matthias Miltenberger
  • Ted K. Ralphs
  • Daniel E. Steffy
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Optimization Software and Modeling Systems

    We investigate how the numerical properties of the LP relaxations evolve throughout the solution procedure in a solver employing the branch-and-cut algorithm. The long-term goal of this work is to determine whether the effect on the numerical conditioning of the LP relaxations resulting from the branching and cutting operations can be effectively predicted and whether … Read more

    An Improved Method of Total Variation Superiorization Applied to Reconstruction in Proton Computed Tomography

  • Yair Censor
  • Paniz Karbasi
  • Keith E. Schubert
  • Reinhard W. Schulte
  • Blake Schultze
    • Categories Biomedical Applications, Constrained Nonlinear Optimization, Convex Optimization Tags , , , , ,

    Previous work showed that total variation superiorization (TVS) improves reconstructed image quality in proton computed tomography (pCT). The structure of the TVS algorithm has evolved since then and this work investigated if this new algorithmic structure provides additional benefits to pCT image quality. Structural and parametric changes introduced to the original TVS algorithm included: (1) … Read more