An Integrated Scenario-Based Approach for Robust Aircraft Routing, Crew Pairing and Re-timing.

  • Michelle Dunbar
  • Gary Froyland
  • Cheng-Lung Wu
    • Categories Airline Optimization Tags , , ,

    For reasons of tractability, the airline scheduling problem has traditionally been sequentially decomposed into various stages (eg. schedule generation, fleet assignment, aircraft routing, and crew pairing), with the decisions from one stage imposed upon the decision making process in subsequent stages. Whilst this approach greatly simplifies the solution process, it unfortunately fails to capture the … Read more

    Trace-Penalty Minimization for Large-scale Eigenspace Computation

  • Xin Liu
  • Zaiwen Wen
  • Yin Zhang
  • Chao Yang
    • Categories Basic Sciences Applications, Constrained Nonlinear Optimization, Parallel Algorithms Tags , ,

    The Rayleigh-Ritz (RR) procedure, including orthogonalization, constitutes a major bottleneck in computing relatively high dimensional eigenspaces of large sparse matrices. Although operations involved in RR steps can be parallelized to a certain level, their parallel scalability, which is limited by some inherent sequential steps, is lower than dense matrix-matrix multiplications. The primary motivation of this … Read more

    Intersection Cuts for Mixed Integer Conic Quadratic Sets

  • Kent Andersen
  • Anders Jensen
    • Categories (Mixed) Integer Nonlinear Programming Tags , ,

    Balas introduced intersection cuts for mixed integer linear sets. Intersection cuts are given by closed form formulas and form an important class of cuts for solving mixed integer linear programs. In this paper we introduce an extension of intersection cuts to mixed integer conic quadratic sets. We identify the formula for the conic quadratic intersection … Read more

    Embedded Online Optimization for Model Predictive Control at Megahertz Rates

  • George A. Constantinides
  • Paul J. Goulart
  • Eric C. Kerrigan
  • Stefan Richter
  • Juan L. Jerez
  • Manfred Morari
    • Categories Parallel Algorithms, Quadratic Programming Tags , ,

    Faster, cheaper, and more power efficient optimization solvers than those currently offered by general-purpose solutions are required for extending the use of model predictive control (MPC) to resource-constrained embedded platforms. We propose several custom computational architectures for different first-order optimization methods that can handle linear-quadratic MPC problems with input, input-rate, and soft state constraints. We … Read more

    On the relative strength of families of intersection cuts arising from pairs of tableau constraints in mixed integer programs

  • Yogesh Awate
  • Gérard Cornuéjols
  • Bertrand Guenin
  • Levent Tunçel
    • Categories (Mixed) Integer Linear Programming Tags , ,

    We compare the relative strength of valid inequalities for the integer hull of the feasible region of mixed integer linear programs with two equality constraints, two unrestricted integer variables and any number of nonnegative continuous variables. In particular, we prove that the closure of Type~2 triangle (resp. Type~3 triangle; quadrilateral) inequalities, are all within a … Read more

    A framework for automated PDE-constrained optimisation

  • P. E. Farrell
  • S. W. Funke
    • Categories Problem Solving Environments Tags , , , , ,

    A generic framework for the solution of PDE-constrained optimisation problems based on the FEniCS system is presented. Its main features are an intuitive mathematical interface, a high degree of automation, and an efficient implementation of the generated adjoint model. The framework is based upon the extension of a domain-specific language for variational problems to cleanly … Read more

    An Augmented Lagrangian Method for Conic Convex Programming

  • Necdet Serhat Aybat
  • Garud Iyengar
    • Categories Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming Tags , , , ,

    We propose a new first-order augmented Lagrangian algorithm ALCC for solving convex conic programs of the form min{rho(x)+gamma(x): Ax-b in K, x in chi}, where rho and gamma are closed convex functions, and gamma has a Lipschitz continuous gradient, A is mxn real matrix, K is a closed convex cone, and chi is a “simple” … Read more

    Risk-Averse Stochastic Dual Dynamic Programming

  • Vaclav Kozmik
  • David P. Morton
    • Categories Stochastic Programming Tags , , ,

    We formulate a risk-averse multi-stage stochastic program using conditional value at risk as the risk measure. The underlying random process is assumed to be stage-wise independent, and a stochastic dual dynamic programming (SDDP) algorithm is applied. We discuss the poor performance of the standard upper bound estimator in the risk-averse setting and propose a new … Read more

    Exact algorithms for the Traveling Salesman Problem with Draft Limits

  • Maria Battarra
  • Artur Alves Pessoa
  • Anand Subramanian
  • Eduardo Uchoa
    • Categories Branch and Cut Algorithms, Integer Programming Tags , , , ,

    This paper deals with the Traveling Salesman Problem (TSP) with Draft Limits (TSPDL), which is a variant of the well-known TSP in the context of maritime transportation. In this recently proposed problem, draft limits are imposed due to restrictions on the port infrastructures. Exact algorithms based on three mathematical formulations are proposed and their performance … Read more

    Computational aspects of simplex and MBU-simplex algorithms using different anti-cycling pivot rules

  • Nagy Adrienn
  • Tibor Illés
    • Categories Linear Programming, Optimization Software Benchmark Tags , , ,

    Several variations of index selection rules for simplex type algorithms for linear programming, like the Last-In-First-Out or the Most-Often-Selected-Variable are rules not only theoretically finite, but also provide significant flexibility in choosing a pivot element. Based on an implementation of the primal simplex and the monotonic build-up (MBU) simplex method, the practical benefit of the … Read more