[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[Help-glpk] Strong branching

From: harald . buesching
Subject: [Help-glpk] Strong branching
Date: Tue, 25 Sep 2007 18:17:10 +0200


I am still working on a little project in my spare time for doing branches in parallel.
One side-effect which came up in the research of mine, that a so called "strong branching" is possible with glpk for sparse MILP.

It is in no way straight forward how to do it:

Convert the node you are working on to its dual problem, in fact a new problem is created.
Fix in this new problem almost all variables to the dual values of the original problem and use presolving. The dual variables which are still free are only in the region of the considered normal variable (which is now a restriction). Region can be defined via the graph of the problem.

For sparse problems this will work. Also possible, you can shrink first the problem before you do the conversion, but I didn't implement it in that way.

I can publish the code, but what I did, was first to standardize the LP first:

Only use min direction (transform objective, if needed)
No Bounds (Shall be real inequalities!)
only use <= inequalities

reply via email to

[Prev in Thread] Current Thread [Next in Thread]