Parametric global optimisation for bilevel programming

Nuno Faísca; Vivek Dua; Berç Rustem; Pedro Saraiva; Efstratios Pistikopoulos
August 2007
Journal of Global Optimization;Aug2007, Vol. 38 Issue 4, p609
Academic Journal
Abstract  We propose a global optimisation approach for the solution of various classes of bilevel programming problems (BLPP) based on recently developed parametric programming algorithms. We first describe how we can recast and solve the inner (follower’s) problem of the bilevel formulation as a multi-parametric programming problem, with parameters being the (unknown) variables of the outer (leader’s) problem. By inserting the obtained rational reaction sets in the upper level problem the overall problem is transformed into a set of independent quadratic, linear or mixed integer linear programming problems, which can be solved to global optimality. In particular, we solve bilevel quadratic and bilevel mixed integer linear problems, with or without right-hand-side uncertainty. A number of examples are presented to illustrate the steps and details of the proposed global optimisation strategy.


Related Articles

  • A reference point technique to compute nondominated solutions in MOLFP. Costa, J. P.; Alves, M. J. // Journal of Mathematical Sciences;Sep2009, Vol. 161 Issue 6, p820 

    This paper presents a new technique to compute nondominated solutions in multiobjective linear-fractional programming (MOLFP) by using reference points. The basic idea consists in dividing the nondominated region approximately through the �middle� making two subregions, which are then...

  • Optimal 3-terminal cuts and linear programming. Cheung, Kevin K. H.; Cunningham, William H.; Tang, Lawrence // Mathematical Programming;Mar2006, Vol. 106 Issue 1, p1 

    Given an undirected graph G=( V, E) and three specified terminal nodes t 1, t 2, t 3, a 3-cut is a subset A of E such that no two terminals are in the same component of G\ A. If a non-negative edge weight c e is specified for each e∈ E, the optimal 3-cut problem is to find a 3-cut of...

  • Adaptive discretization of convex multistage stochastic programs. Vigerske, Stefan; Nowak, Ivo // Mathematical Methods of Operations Research;2007, Vol. 65 Issue 2, p361 

    We propose a new scenario tree reduction algorithm for multistage stochastic programs, which integrates the reduction of a scenario tree into the solution process of the stochastic program. This allows to construct a scenario tree that is highly adapted on the optimization problem. The algorithm...

  • A symmetrical linear maxmin approach to disjoint bilinear programming. Audet, Charles; Hansen, Pierre; Jaumard, Brigitte; Savard, Gilles // Mathematical Programming;1999, Vol. 85 Issue 3, p573 

    Abstract. The disjoint bilinear programming problem can be reformulated using two distinct linear maxmin programming problems. There is a simple bijection between the optimal solutions of the reformulations and the bilinear problem. Moreover, the number of local optima of the reformulations is...

  • Solving of linear programming by method of structural optimization. Karganov, Sergey A. // Scientific Journals of The Maritime University of Szczecin, Zesz;2013, Vol. 106 Issue 34, p48 

    The paper lists the problems hindering the use in business practices of the results of solving direct and inverse problems in linear programming. It is shown that overcoming these obstacles lies in the way of using of developed by the author and described in this paper method of structural...

  • A Global Convergent Algorithm for Solving the Mixed Integer Bilevel Linear Programming Problem. Maoxian Zhao; Ziyou Gao // Journal of Systems Science & Information;Mar2005, Vol. 3 Issue 1, p169 

    A global optimization method for solving a mixed integer bilevel linear programming problem where the upper-level decision maker controls all discrete variables and the lower-level decision maker controls all continuous variables is proposed. By searching for a better bound from the natural...

  • A mixed-integer linear programming approach to the reduction of genome-scale metabolic networks. Röhl, Annika; Bockmayr, Alexander // BMC Bioinformatics;1/3/2017, Vol. 18, p1 

    Background: Constraint-based analysis has become a widely used method to study metabolic networks. While some of the associated algorithms can be applied to genome-scale network reconstructions with several thousands of reactions, others are limited to small or medium-sized models. In 2015,...

  • The Problem of Estimation of Importance Factors as a Symmetric-Lexicographic Problem of Optimization. Podinovskii, V. V. // Automation & Remote Control;Mar2003, Vol. 64 Issue 3, p480 

    It is shown that the problem of calculating the importance factors of objects on the basis of their interval paired comparisons, which is set up as a multicriteria problem of the minimization of equally important criteria that manifest themselves as multiplicative residuals of the system of...

  • Optimal Mechanism Design for a Sequencing Problem with Two-Dimensional Types. Hoeksma, Ruben; Uetz, Marc // Operations Research;Nov/Dec2016, Vol. 64 Issue 6, p1438 

    We study the design of mechanisms for a sequencing problem where the types of job-agents consist of processing times and waiting costs that are private to the jobs. In the Bayes-Nash setting, we seek to find a sequencing rule and incentive compatible payments that minimize the total expected...


Read the Article


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

Try another library?
Sign out of this library

Other Topics