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

[Michael Hennebry]

On Fri, 19 Dec 2008, Joey Rios wrote:
> Hi Michael,
>
> > If the relaxed solution found is known to be basic,
> > the LP can be greatly reduced for the purpose of finding the basis.
> > Simply remove every constraint that is known to not be tight.
> > When you put them back, every added variable will be basic.
>
> I don't know that the relaxed solution is basic.  In fact, I'm pretty sure it 
> isn't.  If I run my regular monolithic (non-decomposed) version of the problem 
> I can (usually) get an integer solution from the glp_simplex call.  When I run 
> the decomposed version, I get the same optimal value, but a non-integer 
> solution.

The tool is GLPK's simplex method.
Once you remove enough inequalities,
the simplex method shouldn't take too long.

If your decision variables are all binary,
you might try using decomposition to minimze cx where c=0.5-x_d
and x_d is the first solution obtained from decomposition.
If you need to, scale to produce integers.
If you keep doing that, you will get to a basic solution.
You are finding a local maximum to the
distance from the center of the hypercube.
Other points might be better than the center of the hypercube.

Can your decomposition method handle a lexigraphic objective?

Here is another thought.
Make all your decision variables nonbasic
so that the LP is dual feasible.
Add only the constraints that are tight for the decomposition solution.
Use the dual simplex method to find another solution.
Add any violated constraints.
Repeat until done.

> > Finding a basis is trickier if the relaxed solution is not known to be basic.
> > Degeneracy and near degeneracy often present the
> > problem of how to tell something small from zero.
> > It's not always solvable.
> > Reduced costs can help.
> > If an optimal reduced cost is known to be nonzero,
> > the corresponding constraint must be tight.
> > If there is no optimal solution for which a constraint is tight,
> > that constraint may be dropped.
>
> I'm not sure how to use the tools you are talking about here.  How can I say 
> anything about reduced costs if I don't have a basis yet?

I don't know enough about your decomposition method to say.
Can it tell you that some variables have to be at their bounds?

> > If the factor of 100 persists in the B&B subproblems,
> > you might want to consider rolling your own
> > so that you can take advantage of decomposition.

--
Michael   address@hidden
"Pessimist: The glass is half empty.
Optimist:   The glass is half full.
Engineer:   The glass is twice as big as it needs to be."