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