Integer Programming

A dual-ascent-based branch-and-bound framework for the prize-collecting Steiner tree and related problems

  • Markus Leitner
  • Ivana Ljubić
  • Martin Luipersbeck
  • Markus Sinnl
    • Categories Combinatorial Optimization, Integer Programming, Network Optimization Tags , , , ,

    In this work we present a branch-and-bound (B&B) framework for the asymmetric prize-collecting Steiner tree problem (APCSTP). Several well-known network design problems can be transformed to the APCSTP, including the Steiner tree problem (STP), prize-collecting Steiner tree problem (PCSTP), maximum-weight connected subgraph problem (MWCS) and the node-weighted Steiner tree problem (NWSTP). The main component of … Read more

    An Adaptive Discretization MINLP Algorithm for Optimal Synthesis of Decentralized Energy Supply Systems

  • Björn Bahl
  • André Bardow
  • Arie M.C.A. Koster
  • Marco E. Lübbecke
  • Sebastian Goderbauer
  • Philip Voll
    • Categories (Mixed) Integer Nonlinear Programming, Applications - Science and Engineering Tags , , , ,

    Decentralized energy supply systems (DESS) are highly integrated and complex systems designed to meet time-varying energy demands, e.g., heating, cooling, and electricity. The synthesis problem of DESS addresses combining various types of energy conversion units, choosing their sizing and operations to maximize an objective function, e.g., the net present value. In practice, investment costs and … Read more

    Three ideas for a Feasibility Pump for nonconvex MINLP

  • Pietro Belotti
  • Timo Berthold
    • Categories (Mixed) Integer Nonlinear Programming Tags , ,

    We describe an implementation of the Feasibility Pump heuristic for nonconvex MINLPs. Our implementation takes advantage of three novel techniques, which we discuss here: a hierarchy of procedures for obtaining an integer solution, a generalized definition of the distance function that takes into account the nonlinear character of the problem, and the insertion of linearization … Read more

    Minimization of Akaike’s Information Criterion in Linear Regression Analysis via Mixed Integer Nonlinear Program

  • Keiji Kimura
  • Hayato Waki
    • Categories (Mixed) Integer Nonlinear Programming Tags ,

    Akaike’s information criterion (AIC) is a measure of the quality of a statistical model for a given set of data. We can determine the best statistical model for a particular data set by the minimization of the AIC. Since we need to evaluate exponentially many candidates of the model by the minimization of the AIC, … Read more

    Tight cycle relaxations for the cut polytope

  • Carla Michini
    • Categories 0-1 Programming, Combinatorial Optimization, Polyhedra Tags , , , , ,

    We study the problem of optimizing an arbitrary weight function w’z over the metric polytope of a graph G=(V,E), a well-known relaxation of the cut polytope. We define the signed graph (G, E^-), where E^- consists of the edges of G having negative weight. We characterize the sign patterns of the weight vector w such … Read more

    Alternating Criteria Search: A Parallel Large Neighborhood Search Algorithm for Mixed Integer Programs

  • Shabbir Ahmed
  • Lluís-Miquel Munguía
  • George L. Nemhauser
  • David A. Bader
  • Yufen Shao
    • Categories (Mixed) Integer Linear Programming, Parallel Algorithms Tags , , ,

    We present a parallel large neighborhood search framework for finding high quality primal solutions for generic Mixed Integer Programs (MIPs). The approach simultaneously solves a large number of sub-MIPs with the dual objective of reducing infeasibility and optimizing with respect to the original objective. Both goals are achieved by solving restricted versions of two auxiliary … Read more

    Some cut-generating functions for second-order conic sets

  • Santanu S. Dey
  • Asteroide Santana
    • Categories Cutting Plane Approaches, Integer Programming

    In this paper, we study cut generating functions for conic sets. Our first main result shows that if the conic set is bounded, then cut generating functions for integer linear programs can easily be adapted to give the integer hull of the conic integer program. Then we introduce a new class of cut generating functions … Read more

    Ellipsoidal Mixed-Integer Representability

  • Alberto Del Pia
  • Jeffrey Poskin
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Theory

    Representability results for mixed-integer linear systems play a fundamental role in optimization since they give geometric characterizations of the feasible sets that can be formulated by mixed-integer linear programming. We consider a natural extension of mixed-integer linear systems obtained by adding just one ellipsoidal inequality. The set of points that can be described, possibly using … Read more

    On Decomposability of Multilinear Sets

  • Alberto Del Pia
  • Aida Khajavirad
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Theory, Polyhedra

    In this paper, we consider the Multilinear set defined as the set of binary points satisfying a collection of multilinear equations. Such sets appear in factorable reformulations of many types of nonconvex optimization problems, including binary polynomial optimization. A great simplification in studying the facial structure of the convex hull of the Multilinear set is … Read more

    On Approximation Algorithms for Concave Mixed-Integer Quadratic Programming

  • Alberto Del Pia
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Theory

    Concave Mixed-Integer Quadratic Programming is the problem of minimizing a concave quadratic polynomial over the mixed-integer points in a polyhedral region. In this work we describe an algorithm that finds an ε-approximate solution to a Concave Mixed-Integer Quadratic Programming problem. The running time of the proposed algorithm is polynomial in the size of the problem … Read more