Re: [Help-glpk] Using branch and cut starting with relaxed solution

[Andrew Makhorin]

> I know this has been asked in different ways, but I haven't gotten a
> clear sense of what to do from those previous posts.

> I have a relaxed solution to a binary integer program.  In most of my
> cases, well over 90% of the variables are already binary.  I'd like to
> use the branch and bound/cut code already in GLPK to get to an integer
> solution.

> The main problem I have is that I didn't arrive at the relaxed
> solution through a standard glp_simplex() call, so I don't have a basis
> ready, else I'd just call glp_intopt() and see what happens.

> So I guess I have a few questions:

> 1.  What would be the method for creating a basis in this case?  I
> assume all of the binary variables with non-binary values would need to
> be basic, but after that how do I decide which other variables are basic
> just given their values from my relaxed solution?

There exists so called crossover procedure that allows recovering
a basic solution corresponding to a given optimal solution. As a rule
it follows the interior point method to recover the basis. However,
this feature is not yet implemented in glpk.

> 2.  I have the reference manual for version 4.34 in front of me. 
> Should/can I just use the branch-and-cut API directly somehow?  If so,
> how should I go about using my relaxed solution as a starting point?

To start the search the mip solver needs an optimal *basic* solution
to lp relaxation. So even the solution you can provide is optimal,
it is useless for the mip solver until the corresponding basis is known.

> 3.  Given what I've described, is there something else I should try?

Probably, as you said, you can call glp_simplex and then glp_intopt
and (then) see what happens. I do not think that solving lp relaxation
will take more time than integer optimization.

> Any advice appreciated.  I can provide further details if they'd be
> helpful.  Thanks.