State-of-the-art implementation for bilevel programs

[rhn]

Hi,

I tried YALMIP to solve a bilevel problem with cplex as inner and outer solver. It gives correct solutions,

but the solver just gives up on any serious instance size. Is any decent performing bilevel solver available

anywhere? Bard's book mentions several implementations, but I couldn't locate any one of them on the internet.

Regards

[Johan Löfberg]

There are no public implementations of bilevel solvers as far as I know. Perhaps reveals something about the status of bilevel programming

How did you solve the problem? Completely manual setup, setup using the KKT function in YALMIP, or solving directly using solvebilevel?

[rhn]

Directly using solvebilevel.

The absence of implementations is disappointing, given the authors in the area make such bold claims

about its usefulness and applications.

[Johan Löfberg]

I could not agree more, it annoys me too. Repeated papers on great algorithms with numerical results, but nothing made public.

solvebilevel is really slow. It is only intended as an absolutely last resort when lack of dual bounds leads to numerical issues in small problems.

Try a MIQP kkt based approached (i.e., let YALMIP derive the kkt conditions and then optimize over those, leads to big-M formulations of the compl. slackness conditions. How well it performs depends on how good the derived dual bounds are)

http://users.isy.liu.se/johanl/yalmip/pmwiki.php?n=Commands.Kkt

There are some tricks and undocumented options in the dual bound derivation (set in the kkt fields of standard options structure). You are welcome to contact me by email for a detailed discussion.