mixed-integer programming

BFO, a trainable derivative-free Brute Force Optimizer for nonlinear bound-constrained optimization and equilibrium computations with continuous and discrete variables

  • Margherita Porcelli
  • Philippe L. Toint
    • Categories (Mixed) Integer Nonlinear Programming, Bound-constrained Optimization, Nonlinear Optimization Tags , , , ,

    A direct-search derivative-free Matlab optimizer for bound-constrained problems is described, whose remarkable features are its ability to handle a mix of continuous and discrete variables, a versatile interface as well as a novel self-training option. Its performance compares favourably with that of NOMAD, a state-of-the art package. It is also applicable to multilevel equilibrium- or … Read more

    Reoptimization Techniques for MIP Solvers

  • Gerald Gamrath
  • Jakob Witzig
  • Benjamin Hiller
    • Categories 0-1 Programming, Branch and Cut Algorithms, Problem Solving Environments Tags , , , ,

    Recently, there have been many successful applications of optimization algorithms that solve a sequence of quite similar mixed-integer programs (MIPs) as subproblems. Traditionally, each problem in the sequence is solved from scratch. In this paper we consider reoptimization techniques that try to benefit from information obtained by solving previous problems of the sequence. We focus … Read more

    Branch-and-Cut for Linear Programs with Overlapping SOS1 Constraints

  • Tobias Fischer
  • Marc E. Pfetsch
    • Categories Integer Programming Tags , , , , ,

    SOS1 constraints require that at most one of a given set of variables is nonzero. In this article, we investigate a branch-and-cut algorithm to solve linear programs with SOS1 constraints. We focus on the case in which the SOS1 constraints overlap. The corresponding conflict graph can algorithmically be exploited, for instance, for improved branching rules, … Read more

    Cutting planes from extended LP formulations

  • Merve Bodur
  • Sanjeeb Dash
  • Oktay Gunluk
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches Tags , ,

    Given a mixed-integer set defined by linear inequalities and integrality requirements on some of the variables, we consider extended formulations of its continuous (LP) relaxation and study the effect of adding cutting planes in the extended space. In terms of optimization, extended LP formulations do not lead to better bounds as their projection onto the … Read more

    Computational Optimization of Gas Compressor Stations: MINLP Models vs. Continuous Reformulations

  • Daniel Rose
  • Martin Schmidt
  • Marc C. Steinbach
  • Bernhard M. Willert
    • Categories (Mixed) Integer Nonlinear Programming, Applications - Science and Engineering, Nonlinear Optimization Tags , , , ,

    When considering cost-optimal operation of gas transport networks, compressor stations play the most important role. Proper modeling of these stations leads to complicated mixed-integer nonlinear and nonconvex optimization problems. In this article, we give an isothermal and stationary description of compressor stations, state MINLP and GDP models for operating a single station, and discuss several … Read more

    A mixed integer programming approach to reduce fuel load accumulation for prescribed burn planning

  • John W Hearne
  • Melih Ozlen
  • Ramya Rachmawati
  • Karin Reinke
    • Categories Applications - OR and Management Sciences Tags , , , , ,

    The increasing frequency of destructive wild land fires, with a consequent loss of life and property, has led to fire and land management agencies initiating extensive fuel management programs. This involves long-term scheduling of the location of fuel reduction activities such as prescribed burning or mechanical clearing. In this paper a Mixed Integer Programming (MIP) … Read more

    Certificates of Optimality and Sensitivity Analysis using Generalized Subadditive Generator Functions: A test study on Knapsack Problems

  • Kevin Cheung
  • Babak Moazzez
    • Categories (Mixed) Integer Linear Programming Tags , , , , , ,

    We introduce a family of subadditive functions called Generator Functions for mixed integer linear programs. These functions were previously defined for pure integer programs with non-negative entries by Klabjan [13]. They are feasible in the subadditive dual and we show that they are enough to achieve strong duality. Several properties of the functions are shown. … Read more

    Facets for Continuous Multi-Mixing Set with General Coefficients and Bounded Integer Variables

  • Manish Bansal
  • Kiavash Kianfar
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches, Integer Programming Tags , , , , ,

    Bansal and Kianfar introduced continuous multi-mixing set where the coefficients satisfy the so-called n-step MIR conditions and developed facet-defining inequalities for this set. In this paper, we first generalize their inequalities for the continuous multi-mixing set with general coefficients (where no conditions are imposed on the coefficients) and show that they are facet-defining in many … Read more

    Scenario-Tree Decomposition: Bounds for Multistage Stochastic Mixed-Integer Programs

  • Oleg A. Prokopyev
  • Andrew J. Schaefer
  • Gabriel L. Zenarosa
    • Categories Integer Programming, Parallel Algorithms, Stochastic Programming Tags , ,

    Multistage stochastic mixed-integer programming is a powerful modeling paradigm appropriate for many problems involving a sequence of discrete decisions under uncertainty; however, they are difficult to solve without exploiting special structures. We present scenario-tree decomposition to establish bounds for unstructured multistage stochastic mixed-integer programs. Our method decomposes the scenario tree into a number of smaller … Read more

    Binary Decision Rules for Multistage Adaptive Mixed-Integer Optimization

  • Dimitris Bertsimas
  • Angelos Georghiou
    • Categories Applications - OR and Management Sciences, Integer Programming, Robust Optimization Tags , ,

    Decision rules provide a flexible toolbox for solving the computationally demanding, multistage adaptive optimization problems. There is a plethora of real-valued decision rules that are highly scalable and achieve good quality solutions. On the other hand, existing binary decision rule structures tend to produce good quality solutions at the expense of limited scalability, and are … Read more