reformulation

Partial Relaxation of Equality-constrained Programs

  • Isaac Siwale
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization Tags , , , , ,

    This paper presents a reformulation that is a natural “by-product” of the ‘variable endogenization’ process for equality-constrained programs. The method results a partial relaxation of the constraints which in turn confers some computational advantages. A fully-annotated example illustrates the technique and presents some comparative numerical results. CitationSiwale, I.: Partial Relaxation of Equality-constrained Programs. Technical Report … Read more

    Solving Bilevel Mixed Integer Program by Reformulations and Decomposition

  • Yu An
  • Bo Zeng
    • Categories (Mixed) Integer Linear Programming, Complementarity and Variational Inequalities Tags , , ,

    In this paper, we study bilevel mixed integer programming (MIP) problem and present a novel computing scheme based on reformulations and decomposition strategy. By converting bilevel MIP into a constrained mathematical program, we present its single-level reformulations that are friendly to perform analysis and build insights. Then, we develop a decomposition algorithm based on column-and-constraint … Read more

    Transmission Expansion Planning Using an AC Model: Formulations and Possible Relaxations

  • G. Th. Heydt
  • Hans D Mittelmann
  • Vijay Vittal
  • Hui Zhang
    • Categories Facility Planning and Design Tags , , , , ,

    Transmission expansion planning (TEP) is a rather complicated process which requires extensive studies to determine when, where and how many transmission facilities are needed. A well planned power system will not only enhance the system reliability, but also tend to contribute positively to the overall system operating efficiency. Starting with two mixed-integer nonlinear programming (MINLP) … Read more

    On the impact of symmetry-breaking constraints on spatial Branch-and-Bound for circle packing in a square

  • Alberto Costa
  • Pierre Hansen
  • Leo Liberti
    • Categories Combinatorial Optimization, Global Optimization, Nonlinear Optimization Tags , , , ,

    We study the problem of packing equal circles in a square from the mathematical programming point of view. We discuss different formulations, we analyse formulation symmetries, we propose some symmetry breaking constraints and show that not only do they tighten the convex relaxation bound, but they also ease the task of local NLP solution algorithms … Read more

    On convex relaxations of quadrilinear terms

  • Sonia Cafieri
  • Jon Lee
  • Leo Liberti
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Tags , , , , , , ,

    The best known method to find exact or at least epsilon-approximate solutions to polynomial programming problems is the spatial Branch-and-Bound algorithm, which rests on computing lower bounds to the value of the objective function to be minimized on each region that it explores. These lower bounds are often computed by solving convex relaxations of the … Read more

    Reformulating Linear Programs with Transportation Constraints — with Applications to Workforce Scheduling

  • Tolga Cezik
  • Oktay Gunluk
    • Categories Combinatorial Optimization, Network Optimization Tags , ,

    We study linear programming models that contain transportation constraints in their formulation. Typically, these models have a multi-stage nature and the transportation constraints together with the associated flow variables are used to achieve consistency between consecutive stages. We describe how to reformulate these models by projecting out the flow variables. The reformulation can be more … Read more

    A Multi-stage Stochastic Integer Programming Approach for Capacity Expansion under Uncertainty

  • Shabbir Ahmed
  • Alan J. King
  • Gyana Parija
    • Categories Integer Programming, Production and Logistics, Stochastic Programming Tags , , , ,

    This paper addresses a multi-period investment model for capacity expansion in an uncertain environment. Using a scenario tree approach to model the evolution of uncertain demand and cost parameters, and fixed-charge cost functions to model the economies of scale in expansion costs, we develop a multi-stage stochastic integer programming formulation for the problem. A reformulation … Read more