> -----Original Message----- > From: [email protected] [mailto:help-glpk- > [email protected]] 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 [email protected] _______________________________________________ Help-glpk mailing list [email protected] http://lists.gnu.org/mailman/listinfo/help-glpk
