Re: [Help-glpk] concave gain networks and non-global optima

[Axel Simon]

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) : address@hidden
> Webmail (preferred)           : address@hidden
> [from IMAP client]
>
>
>
>
> _______________________________________________
> Help-glpk mailing list
> address@hidden
> http://lists.gnu.org/mailman/listinfo/help-glpk