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

[Robert Fourer]

> -----Original Message-----
> From: address@hidden [mailto:help-glpk-
> address@hidden On Behalf Of Andrew Makhorin
> Sent: Thursday, December 11, 2008 3:59 PM
> To: Robbie Morrison
> Cc: GLPK
> Subject: Re: [Help-glpk] concave gain networks and non-global optima
> 

.......

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

"Special ordered sets of type 2" (or SOS2) are a feature of branch-and-bound
codes for mixed-integer programming.  They permit a linear program with
separable piecewise-linear terms in its objective to be solved to guaranteed
optimality, even if the terms are not convex (in the case of a minimization) or
concave (in the case of a maximization).  But as Andrew points out, there's no
way in general to solve such problems to optimality using only a generalization
of the simplex method.

I believe that the computational cost of solving a MIP using SOS2 is not so
prohibitive these days as the quoted passage from OR-Notes might imply.  There
has been a lot of progress in MIP software in the decade since the OR-Notes
were first written.

Bob Fourer
address@hidden