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

[Andrew Makhorin]

> 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).

Theoretically, glpk mip solver finds a global optimum for mip.

> 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?

Solution (or a set of solutions) to any correctly formulated
mathematical programming problem is determined by the problem itself
and therefore does not depend on the solver with which it is obtained.
Of course, I mean ideal case, when the solver does not encounter
numerical difficulties caused by floating-point arithmetic.

> 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.

All three glpk solvers (simplex, interior-point, and branch-and-cut)
are global optimizers. There exists a version of the simplex method for
so called separable programming, where a non-linear and non-convex
objective is approximated by a separable piecewise linear function, and
special additional rules are used for choosing entering and leaving
variables from special ordered sets (SOS); see, for example,
http://people.brunel.ac.uk/~mastjjb/jeb/or/sep.html . But due to
non-convexity such version of the simplex method may (as a rule, does)
converge to a local optimum. However, this feature is not implemented
in glpk.

Andrew Makhorin