A deterministic bounding procedure for the global optimization of a bi-level mixed-integer problem

Abstract

In this paper, a deterministic bounding procedure for the global optimization of a mixed-integer bi-level programming problem is proposed. The aim has been to develop an efficient algorithm to deal with a case study in the electricity retail market. In this problem, an electricity retailer wants to define a timeof-use tariff structure to maximize profits, but he has to take into account the consumers’ reaction by means of re-scheduling appliance operation to minimize costs. The problem has been formulated as a bi-level mixed-integer programming model. The algorithm we propose uses optimal-value-function reformulations based on similar principles as the ones that have been used by other authors, which are adapted to the characteristics of this type of (pricing optimization) problems where no upper (lower) level variables appear in the lower (upper) level constraints. The overall strategy consists of generating a series of convergent upper bounds and lower bounds for the upper-level objective function until the difference between these bounds is below a given threshold. Computational results are presented as well as a comparison with a hybrid approach combining a particle swarm optimization algorithm to deal with the upper-level problem and an exact solver to tackle the lower-level problem, which we have previously developed to address a similar case study. When the lower-level model is difficult, a significant relative MIP gap is unavoidable when solving the algorithm’s subproblems. Novel reformulations of those subproblems using “elastic” variables are proposed trying to obtain meaningful lower/upper bounds within an acceptable computational time.