[Help-glpk] Re: MIP

[Andrew Makhorin]

> In particular we would benefit if GLPK handled
> Special Order Sets of type 1 as described in [Tomlin 70]. So I wanted to ask
> you if you plan in implementing SOS handling?

sos1 can be easiliy modeled as follows:

x1 + x2 + ... + xn = 1

where all x1, ..., xn are binary variables.

> In addition I noticed that in
> the function "create_branches" the objective function bound on the new nodes
> does not take into account the calculated penalties (P_u, P_d) as I would
> expect after reading [Tolmlin 70].  Is there a reason for that?

Penalties for "up" and "down" branches are calculated and used to
choose branching variables in branch_drtom (glplpx6c).

> Finally I
> did not see the Gomory  cut penalty P_G being calculated. Would it be any
> useful to calculate it and apply Eq. 3.14 from [Tomlin 70]?

You probably mean the article: Tomlin J.A., "Branch and bound methods
for integer and non-convex programming", 1970. Unfortunately, I do not
have it, so maybe someone else on the list could correct me.

The original cutting plane method proposed by R.Gomory is inefficient
for solving mips even of small dimensions, so it is only of theoretical
interest. For practical solving mips most state-of-the-art solvers use
so called branch-and-cut method which is a combination of branch-and-bound
and cutting plane methods (in particular, Gomory cutting planes may be
used). Although glpk includes the branch-and-cut framework, currently it
is used only in the branch-and-bound "mode".

I guess that [Tomlin 70] says about using Gomory cuts for estimating
degradation of the objective that may give useful information for
branching in the b&b context. However, no such features are implemented
in glpk.

Andrew Makhorin