Optimality-based bound contraction with multiparametric disaggregation for the global optimization of mixed-integer bilinear problems

Castro, Pedro; Grossmann, Ignacio
July 2014
Journal of Global Optimization;Jul2014, Vol. 59 Issue 2/3, p277
Academic Journal
We address nonconvex mixed-integer bilinear problems where the main challenge is the computation of a tight upper bound for the objective function to be maximized. This can be obtained by using the recently developed concept of multiparametric disaggregation following the solution of a mixed-integer linear relaxation of the bilinear problem. Besides showing that it can provide tighter bounds than a commercial global optimization solver within a given computational time, we propose to also take advantage of the relaxed formulation for contracting the variables domain and further reduce the optimality gap. Through the solution of a real-life case study from a hydroelectric power system, we show that this can be an efficient approach depending on the problem size. The relaxed formulation from multiparametric formulation is provided for a generic numeric representation system featuring a base between 2 (binary) and 10 (decimal).


Related Articles

  • Bound reduction using pairs of linear inequalities. Belotti, Pietro // Journal of Global Optimization;Jul2013, Vol. 56 Issue 3, p787 

    We describe a procedure to reduce variable bounds in mixed integer nonlinear programming (MINLP) as well as mixed integer linear programming (MILP) problems. The procedure works by combining pairs of inequalities of a linear programming (LP) relaxation of the problem. This bound reduction...

  • A Framework for Globally Optimizing Mixed-Integer Signomial Programs. Misener, Ruth; Floudas, Christodoulos // Journal of Optimization Theory & Applications;Jun2014, Vol. 161 Issue 3, p905 

    Mixed-integer signomial optimization problems have broad applicability in engineering. Extending the Global Mixed-Integer Quadratic Optimizer, GloMIQO (Misener, Floudas in J. Glob. Optim., . doi:), this manuscript documents a computational framework for deterministically addressing mixed-integer...

  • Outer-approximation method for security constrained unit commitment. Ruiz, Juan P.; Jianhui Wang; Cong Liu; Gengyang Sun // IET Generation, Transmission & Distribution;2013, Vol. 7 Issue 11, p1210 

    In this study, the authors present an outer-approximation method to solve the mixed-integer non-linear security constrained unit commitment problem. The main idea lies in solving sequentially a set of mixed-integer linear programs (MILP) to obtain lower bounds (LBs) of the global optimum and...

  • A branch and bound method for the solution of multiparametric mixed integer linear programming problems. Oberdieck, Richard; Wittmann-Hohlbein, Martina; Pistikopoulos, Efstratios // Journal of Global Optimization;Jul2014, Vol. 59 Issue 2/3, p527 

    In this paper, we present a novel algorithm for the solution of multiparametric mixed integer linear programming (mp-MILP) problems that exhibit uncertain objective function coefficients and uncertain entries in the right-hand side constraint vector. The algorithmic procedure employs a branch...

  • Models and Lagrangian heuristics for a two-level lot-sizing problem with bounded inventory. Brahimi, Nadjib; Absi, Nabil; Dauzère-Pérès, Stéphane; Kedad-Sidhoum, Safia // OR Spectrum;Oct2015, Vol. 37 Issue 4, p983 

    We consider a two-level dynamic lot-sizing problem where the first level consists of N finished products competing for a single type of purchased raw material in the second level. While the procurement and production capacities are unlimited, the storage capacity of the raw material is limited...

  • Buffer allocation in stochastic flow lines via sample-based optimization with initial bounds. Weiss, Sophie; Stolletz, Raik // OR Spectrum;Oct2015, Vol. 37 Issue 4, p869 

    The allocation of buffer space in flow lines with stochastic processing times is an important decision, as buffer capacities influence the performance of these lines. The objective of this problem is to minimize the overall number of buffer spaces achieving at least one given goal production...

  • Automatic Dantzig-Wolfe reformulation of mixed integer programs. Bergner, Martin; Caprara, Alberto; Ceselli, Alberto; Furini, Fabio; Lübbecke, Marco; Malaguti, Enrico; Traversi, Emiliano // Mathematical Programming;Feb2015, Vol. 149 Issue 1/2, p391 

    Dantzig-Wolfe decomposition (or reformulation) is well-known to provide strong dual bounds for specially structured mixed integer programs (MIPs). However, the method is not implemented in any state-of-the-art MIP solver as it is considered to require structural problem knowledge and tailoring...

  • Error bounds for mixed integer linear optimization problems. Stein, Oliver // Mathematical Programming;Mar2016, Vol. 156 Issue 1/2, p101 

    We introduce computable a priori and a posteriori error bounds for optimality and feasibility of a point generated as the rounding of an optimal point of the LP relaxation of a mixed integer linear optimization problem. Treating the mesh size of integer vectors as a parameter allows us to study...

  • A Trust Region Method for the Solution of the Surrogate Dual in Integer Programming. Boland, N.; Eberhard, A.; Tsoukalas, A. // Journal of Optimization Theory & Applications;Nov2015, Vol. 167 Issue 2, p558 

    We propose an algorithm for solving the surrogate dual of a mixed integer program. The algorithm uses a trust region method based on a piecewise affine model of the dual surrogate value function. A new and much more flexible way of updating bounds on the surrogate dual's value is proposed, in...


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics