Lagrangian Relaxation Applied to Combinatorial Reverse Auctions for the Electricity Sector: Variation of Sub-gradient Method Parameters

Resumo

Some optimization problems are N P-hard and they can be intractable when solving for big instances
exactly. However, if most of the set of constraints has proper structure, then Lagrangian Relaxation can be a
suitable approach. Anyway, the duality gap for the non-convex problem can remain large, if no good upper-bound
for the objective function can be found. This paper presents a Lagrangian Relaxation which deals with some
problem parameters to provide better objective function bounds, by improving the sub-gradient algorithm. It is
applied to solve the Winner Determination Problem (WDP) of a Combinatorial Reverse Auction (CRA) for the
Brazilian Electricity Sector, an auction that allows bids on packages of generation power plants. The WDP is
formulated as an Integer Optimization Problem to allocate the packages that minimizes the sum of accepted bids.
Besides, packing rules are applied to ensure a totally unimodular matrix for the relaxed sub-problem constraints,
which is solved by a linear optimization method.