Month: July 2015

Evaluation complexity for nonlinear constrained optimization using unscaled KKT conditions and high-order models

  • Ernesto G. Birgin
  • José Mario Martínez
  • Sandra Augusta Santos
  • Philippe L. Toint
  • John L. Gardenghi
    • Categories Bound-constrained Optimization, Constrained Nonlinear Optimization Tags , , ,

    The evaluation complexity of general nonlinear, possibly nonconvex,constrained optimization is analyzed. It is shown that, under suitable smoothness conditions, an $\epsilon$-approximate first-order critical point of the problem can be computed in order $O(\epsilon^{1-2(p+1)/p})$ evaluations of the problem’s function and their first $p$ derivatives. This is achieved by using a two-phases algorithm inspired by Cartis, Gould, … Read more

    Pickup and delivery problem with time windows: a new compact two-index formulation

  • Maria Gabriela S. Furtado
  • Reinaldo Morabito
  • Pedro Munari
    • Categories Combinatorial Optimization, Integer Programming, Transportation

    We propose a formulation for the pickup and delivery problem with time windows, based on a novel modeling strategy that allows the assignment of vehicles to routes explicitly in two-index flow formulations. It leads to an effective compact formulation that can benefit OR practitioners interested in solving the problem by general-purpose optimization software. Computational experiments … Read more

    Error bounds for mixed integer nonlinear optimization problems

  • Oliver Stein
    • Categories (Mixed) Integer Nonlinear Programming Tags , , ,

    We introduce a-posteriori and a-priori error bounds for optimality and feasibility of a point generated as the rounding of an optimal point of the NLP relaxation of a mixed-integer nonlinear optimization problem. Our analysis mainly bases on the construction of a tractable approximation of the so-called grid relaxation retract. Under appropriate Lipschitz assumptions on the … Read more

    A Frank-Wolfe Based Branch-and-Bound Algorithm for Mean-Risk Optimization

  • Christoph Buchheim
  • Marianna De Santis
  • Francesco Rinaldi
  • Long Trieu
    • Categories (Mixed) Integer Nonlinear Programming Tags , ,

    We present an exact algorithm for mean-risk optimization subject to a budget constraint, where decision variables may be continuous or integer. The risk is measured by the covariance matrix and weighted by an arbitrary monotone function, which allows to model risk-aversion in a very individual way. We address this class of convex mixed-integer minimization problems … Read more

    Constructing a Small Compact Binary Model for the Travelling Salesman Problem

  • J. Fabian Meier
    • Categories (Mixed) Integer Linear Programming, 0-1 Programming, Transportation Tags , ,

    A variety of formulations for the Travelling Salesman Problem as Mixed Integer Program have been proposed. They contain either non-binary variables or the number of constraints and variables is large. We want to give a new formulation that consists solely of binary variables; the number of variables and the number of constraints are of order … Read more

    A Derivative-Free Trust-Region Algorithm for the Optimization of Functions Smoothed via Gaussian Convolution Using Adaptive Multiple Importance Sampling

  • Irina S Dolinskaya
  • Alvaro Maggiar
  • Jeremy Staum
  • Andreas Wächter
    • Categories Nonlinear Optimization

    In this paper we consider the optimization of a functional $F$ defined as the co nvolution of a function $f$ with a Gaussian kernel. We propose this type of objective function for the optimization of the output of complex computational simulations, which often present some form of deterministic noise and need to be smoothed for … Read more

    A Data Driven Functionally Robust Approach for Coordinating Pricing and Order Quantity Decisions with Unknown Demand Function

  • Jian Hu
  • Sanjay Mehrotra
  • Junxuan Li
    • Categories Marketing, Robust Optimization, Supply Chain Management Tags , ,

    We consider a retailer’s problem of optimal pricing and inventory stocking decisions for a product. We assume that the price-demand curve is unknown, but data is available that loosely specifies the price-demand relationship. We propose a conceptually new framework that simultaneously considers pricing and inventory decisions without a priori fitting a function to the price-demand … Read more

    Another pedagogy for pure-integer Gomory

  • Qi He
  • Jon Lee
    • Categories Cutting Plane Approaches, Integer Programming Tags , , , , , , ,

    We present pure-integer Gomory cuts in a way so that they are derived with respect to a “dual form” pure-integer optimization problem and applied on the standard-form primal side as columns, using the primal simplex algorithm. The input integer problem is not in standard form, and so the cuts are derived a bit differently. In … Read more

    Simplified semidefinite and completely positive relaxations

  • Felix Lieder
    • Categories 0-1 Programming, Linear, Cone and Semidefinite Programming, Semi-definite Programming Tags ,

    This paper is concerned with completely positive and semidefinite relaxations of quadratic programs with linear constraints and binary variables as presented by Burer. It observes that all constraints of the relaxation associated with linear constraints of the original problem can be accumulated in a single linear constraint without changing the feasible set of either the … Read more

    Data-Driven Risk-Averse Two-Stage Stochastic Program with ζ-Structure Probability Metrics

  • Yongpei Guan
  • Chaoyue Zhao
    • Categories Stochastic Programming Tags , ,

    The traditional two-stage stochastic programming approach assumes the distribution of the random parameter in a problem is known. In most practices, however, the distribution is actually unknown. Instead, only a series of historic data are available. In this paper, we develop a data-driven stochastic optimization approach to providing a risk-averse decision making under uncertainty. In … Read more