On Dec 11, 2008, at 21:55, Robbie Morrison wrote:
Hello GLPK list I use a network flow model in which concave gains are represented in piecewise fashion and then "switched in" in the required order using binary variables. I imagine, under these circumstances, GLPK returns a global (as opposed to a local) optima. But I need to be sure (for my PhD write-up too).
I've recently proved in a paper [1] that you can distinguish two polyhedra within one polyhedron by using a Boolean flag (or a binary variable, same thing). The requirements are:
a) the two polyhedra must be bounded (i.e. you can only distinguish two polytopes, really) b) you need to tighten the two polyhedra around the contained integral points
If GLPK does a good job, it should give you b) when you ask for an integer solution. You need to make sure that all the convex pieces of your function are bounded.
Hope this helps, Axel. [1] http://www.di.ens.fr/~simona/simon08splitting.html
Is this kind of result general? If not, is is algorithm specific -- meaning, does it depend on the MILP (branch/cut/bound/etc) method? Or is it problem specific -- in which case, what at the determining issues? These questions may well be off-topic (and I apologize for that) -- but there could well be solver specific consideration and I wanted to consider those first. More generally, do solvers like GLPK make a distinction between global and local optima? Or is it left to the user to have a good understanding their problem and its potential characteristics. best wishes to all --- Robbie Morrison PhD student -- policy-oriented energy system simulation Institute for Energy Engineering (IET) Technical University of Berlin (TU-Berlin), Germany University email (redirected) : [email protected] Webmail (preferred) : [email protected] [from IMAP client] _______________________________________________ Help-glpk mailing list [email protected] http://lists.gnu.org/mailman/listinfo/help-glpk
_______________________________________________ Help-glpk mailing list [email protected] http://lists.gnu.org/mailman/listinfo/help-glpk
