(Mixed) Integer Nonlinear Programming

Penalty Alternating Direction Methods for Mixed-Integer Optimization: A New View on Feasibility Pumps

  • Björn Geißler
  • Antonio Morsi
  • Lars Schewe
  • Martin Schmidt
    • Categories (Mixed) Integer Linear Programming, (Mixed) Integer Nonlinear Programming Tags , , , ,

    Feasibility pumps are highly effective primal heuristics for mixed-integer linear and nonlinear optimization. However, despite their success in practice there are only few works considering their theoretical properties. We show that feasibility pumps can be seen as alternating direction methods applied to special reformulations of the original problem, inheriting the convergence theory of these methods. … Read more

    A Framework for Solving Mixed-Integer Semidefinite Programs

  • Tristan Gally
  • Marc E. Pfetsch
  • Stefan Ulbrich
    • Categories (Mixed) Integer Nonlinear Programming, Optimization Software and Modeling Systems, Semi-definite Programming

    Mixed-integer semidefinite programs arise in many applications and several problem-specific solution approaches have been studied recently. In this paper, we investigate a generic branch-and-bound framework for solving such problems. We first show that strict duality of the semidefinite relaxations is inherited to the subproblems. Then solver components like dual fixing, branching rules, and primal heuristics … Read more

    Computing Restricted Isometry Constants via Mixed-Integer Semidefinite Programming

  • Tristan Gally
  • Marc E. Pfetsch
    • Categories (Mixed) Integer Nonlinear Programming, Semi-definite Programming Tags , ,

    One of the fundamental tasks in compressed sensing is finding the sparsest solution to an underdetermined system of linear equations. It is well known that although this problem is NP-hard, under certain conditions it can be solved by using a linear program which minimizes the 1-norm. The restricted isometry property has been one of the … Read more

    Three Enhancements for Optimization-Based Bound Tightening

  • Timo Berthold
  • Ambros Gleixner
  • Benjamin Müller
  • Stefan Weltge
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization, Nonlinear Optimization Tags , , , , ,

    Optimization-based bound tightening (OBBT) is one of the most effective procedures to reduce variable domains of nonconvex mixed-integer nonlinear programs (MINLPs). At the same time it is one of the most expensive bound tightening procedures, since it solves auxiliary linear programs (LPs)—up to twice the number of variables many. The main goal of this paper … Read more

    A joint routing and speed optimization problem

  • Ricardo Fukasawa
  • Qie He
  • Fernando Santos
  • Yongjia Song
    • Categories (Mixed) Integer Nonlinear Programming, Dynamic Programming, Transportation

    Fuel cost contributes to a significant portion of operating cost in cargo transportation. Though classic routing models usually treat fuel cost as input data, fuel consumption heavily depends on the travel speed, which has led to the study of optimizing speeds over a given fixed route. In this paper, we propose a joint routing and … Read more

    Column Generation based Alternating Direction Methods for solving MINLPs

  • Ivo Nowak
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Theory, Parallel Algorithms Tags , , , , , ,

    Traditional decomposition based branch-and-bound algorithms, like branch-and-price, can be very efficient if the duality gap is not too large. However, if this is not the case, the branch-and-bound tree may grow rapidly, preventing the method to find a good solution. In this paper, we present a new decompositon algorithm, called ADGO (Alternating Direction Global Optimization … Read more

    GasLib – A Library of Gas Network Instances

  • Denis Aßmann
  • Robert Burlacu
  • Imke Joormann
  • Thorsten Koch
  • Marc E. Pfetsch
  • Lars Schewe
  • Martin Schmidt
  • Mathias Sirvent
  • Jesco Humpola
  • Nikolaos Kanelakis
  • Djamal Oucherif
  • Robert Schwarz
    • Categories (Mixed) Integer Nonlinear Programming, Applications - Science and Engineering Tags , , , ,

    The development of mathematical simulation and optimization models and algorithms for solving gas transport problems is an active field of research. In order to test and compare these models and algorithms, gas network instances together with demand data are needed. The goal of GasLib is to provide a set of publicly available gas network instances … Read more

    Valid Inequalities for Separable Concave Constraints with Indicator Variables

  • Cong Han Lim
  • Jeff Linderoth
  • James R. Luedtke
    • Categories (Mixed) Integer Nonlinear Programming

    We study valid inequalities for optimization models that contain both binary indicator variables and separable concave constraints. These models reduce to a mixed-integer linear program (MILP) when the concave constraints are ignored, or to a nonconvex global optimization problem when the binary restrictions are ignored. In algorithms designed to solve these problems to global optimality, … Read more

    Partial outer convexification for traffic light optimization in road networks

  • Simone Göttlich
  • Andreas Potschka
  • Ute Ziegler
    • Categories (Mixed) Integer Nonlinear Programming, Optimization of Systems modeled by PDEs, Transportation Tags , , , ,

    We consider the problem of computing optimal traffic light programs for urban road intersections using traffic flow conservation laws on networks. Based on a Partial Outer Convexification approach, which has been successfully applied in the area of mixed-integer optimal control for systems of ordinary or differential algebraic equations, we develop a computationally tractable two-stage solution … Read more

    A Cutting Plane Method for Risk-constrained Traveling Salesman Problem with Random Arc Costs

  • Vladimir Boginski
  • Qipeng Zheng
  • Zhouchun Huang
  • Tao Zhang
    • Categories (Mixed) Integer Nonlinear Programming, Cutting Plane Approaches, Transportation

    This paper considers the risk-constrained stochastic traveling salesman problem with random arc costs. In the context of stochastic arc costs, the deterministic traveling salesman problem’s optimal solutions would be ineffective because the selected route might be exposed to a greater risk where the actual cost can exceed the resource limit in extreme scenarios. We present … Read more