Month: March 2014

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

    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

    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

    Topology Optimization for Magnetic Circuits dedicated to Electric Propulsion

  • Carole Henaux
  • Frédéric Messine
  • Satafa Sanogo
  • Raphael Vilamot
    • Categories Applications - Science and Engineering, Optimization of Systems modeled by PDEs Tags , , , , , ,

    Abstract—In this paper, we present a method to solve inverse problems of electromagnetic circuit design which are formulated as a topology optimization problem. Indeed, by imposing the magnetic field inside a region, we search a best material distribution into variable domains. In order to perform this, we minimize the quadratic error between the prescribed magnetic … Read more

    Strengthened Benders Cuts for Stochastic Integer Programs with Continuous Recourse

  • Merve Bodur
  • Sanjeeb Dash
  • Oktay Gunluk
  • James R. Luedtke
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches, Stochastic Programming Tags , ,

    With stochastic integer programming as the motivating application, we investigate techniques to use integrality constraints to obtain improved cuts within a Benders decomposition algorithm. We compare the effect of using cuts in two ways: (i) cut-and-project, where integrality constraints are used to derive cuts in the extended variable space, and Benders cuts are then used … Read more

    Decomposition Algorithms for Two-Stage Chance-Constrained Programs

  • Simge Küçükyavuz
  • James R. Luedtke
  • Xiao Liu
    • Categories Branch and Cut Algorithms, Integer Programming, Stochastic Programming Tags , , ,

    We study a class of chance-constrained two-stage stochastic optimization problems where second-stage feasible recourse decisions incur additional cost. In addition, we propose a new model, where “recovery” decisions are made for the infeasible scenarios to obtain feasible solutions to a relaxed second-stage problem. We develop decomposition algorithms with specialized optimality and feasibility cuts to solve … Read more

    A Scalarization Proximal Point Method for Quasiconvex Multiobjective Minimization

  • H. C. F. Apolinário
  • Paulo Roberto Oliveira
  • Erik Alex Papa Quiroz
    • Categories Generalized Convexity/Monoticity, Multi-Criteria Optimization, Nonsmooth Optimization Tags , , , , ,

    In this paper we propose a scalarization proximal point method to solve multiobjective unconstrained minimization problems with locally Lipschitz and quasiconvex vector functions. We prove, under natural assumptions, that the sequence generated by the method is well defined and converges globally to a Pareto-Clarke critical point. Our method may be seen as an extension, for … Read more