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