[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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

From: Axel Simon
Subject: Re: [Help-glpk] concave gain networks and non-global optima
Date: Fri, 12 Dec 2008 00:14:46 +0100

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,


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

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

reply via email to

[Prev in Thread] Current Thread [Next in Thread]