Relaxing nonconvex quadratic functions by multiple adaptive diagonal perturbations

  • Hongbo Dong
    • Categories Global Optimization Theory, Quadratic Programming, Semi-definite Programming

    The current bottleneck of globally solving mixed-integer (nonconvex) quadratically constrained problem (MIQCP) is still to construct strong but computationally cheap convex relaxations, especially when dense quadratic functions are present. We pro- pose a cutting surface procedure based on multiple diagonal perturbations to derive strong convex quadratic relaxations for nonconvex quadratic problem with separable constraints. Our … Read more

    A globally convergent trust-region algorithm for unconstrained derivative-free optimization

  • Priscila Savulski Ferreira
  • Elizabeth Wegner Karas
  • Mael Sachine
    • Categories Nonlinear Optimization, Other Topics, Unconstrained Optimization Tags , , ,

    In this work we explicit a derivative-free trust-region algorithm for unconstrained optimization based on the paper (Computational Optimization and Applications 53: 527-555, 2012) proposed by Powell. The objective function is approximated by quadratic models obtained by polynomial interpolation. The number of points of the interpolation set is fixed. In each iteration only one interpolation point … Read more

    CBLIB 2014: A benchmark library for conic mixed-integer and continuous optimization

  • Henrik A. Friberg
    • Categories Integer Programming, Linear, Cone and Semidefinite Programming, Optimization Software Benchmark Tags , , , , ,

    The Conic Benchmark Library (CBLIB 2014) is a collection of more than a hundred conic optimization instances under a free and open license policy. It is the first extensive benchmark library for the advancing field of conic mixed-integer and continuous optimization, which is already supported by all major commercial solvers and spans a wide range … Read more

    An Improved Stochastic Optimization Model for Water Supply Pumping Systems in Urban Networks

  • Douglas Alem
  • Jonathan De La Vega
    • Categories Applications - OR and Management Sciences, Stochastic Programming Tags , ,

    This study investigates a pump scheduling problem for the collection, transfer and storage of water in water supply systems in urban networks. The objective of this study is to determine a method to minimize the electricity costs associated with pumping operations. To address the dynamic and random nature of water demand, we propose a two-stage … Read more

    A Fast Active Set Block Coordinate Descent Algorithm for l1-regularized least squares

  • Marianna De Santis
  • Stefano Lucidi
  • Francesco Rinaldi
    • Categories Convex and Nonsmooth Optimization, Nonlinear Systems and Least-Squares Tags , ,

    The problem of finding sparse solutions to underdetermined systems of linear equations arises in several real-world problems (e.g. signal and image processing, compressive sensing, statistical inference). A standard tool for dealing with sparse recovery is the l1-regularized least-squares approach that has been recently attracting the attention of many researchers. In this paper, we describe an … Read more

    Derivative-free Methods for Mixed-Integer Constrained Optimization Problems

  • Giampaolo Liuzzi
  • Stefano Lucidi
  • Francesco Rinaldi
    • Categories (Mixed) Integer Nonlinear Programming, Applications - OR and Management Sciences, Constrained Nonlinear Optimization

    Methods which do not use any derivative information are becoming popular among researchers, since they allow to solve many real-world engineering problems. Such problems are frequently characterized by the presence of discrete variables which can further complicate the optimization process. In this paper, we propose derivative-free algorithms for solving continuously differentiable Mixed Integer NonLinear Programming … Read more

    Semidefinite Programming Reformulation of Completely Positive Programs: Range Estimation and Best-Worst Choice Modeling

  • Karthik Natarajan
  • Chung-Piaw Teo
    • Categories (Mixed) Integer Linear Programming, Semi-definite Programming

    We show that the worst case moment bound on the expected optimal value of a mixed integer linear program with a random objective c is closely related to the complexity of characterizing the convex hull of the points CH{(1 x) (1 x)’: x \in X} where X is the feasible region. In fact, we can … Read more

    Choice Based Revenue Management for Parallel Flights

  • Jim Dai
  • Anton J. Kleywegt
  • Weijun Ding
  • Xinchang Wang
  • Yi Zhang
    • Categories Airline Optimization, Applications - OR and Management Sciences, Yield Management Tags , ,

    This paper describes a revenue management project with a major airline that operates in a fiercely competitive market involving two major hubs and having more than 30 parallel daily flights. The market has a number of unusual characteristics including (1) almost half of customers choose not to purchase the tickets after booking; (2) about half … Read more

    On Auction Models of Conflict with Network Applications

  • Igor V. Konnov
    • Categories Complementarity and Variational Inequalities, Telecommunications, Transportation

    We consider several models of complex systems with active elements and show that the auction mechanism appears very natural in attaining proper equilibrium states, even in comparison with game theory ones. In particular, network equilibria are treated as implementation of the auction principle. An additional example of resource allocation in wireless communication networks is also … Read more

    A search for quantum coin-flipping protocols using optimization techniques

  • Ashwin Nayak
  • Jamie Sikora
  • Levent Tunçel
    • Categories Global Optimization Applications, Linear, Cone and Semidefinite Programming, Optimization Software Design Principles Tags , ,

    Coin-flipping is a cryptographic task in which two physically separated, mistrustful parties wish to generate a fair coin-flip by communicating with each other. Chailloux and Kerenidis (2009) designed quantum protocols that guarantee coin-flips with near optimal bias away from uniform, even when one party deviates arbitrarily from the protocol. The probability of any outcome in … Read more