sci.op-research

ltloan@gmail.com wrote:
>
> I have an IP which I solve using column generation. I notice that, as
> I add more columns (and go further down the tree), the running time is
> mostly spent in solving the LP. The master has about 600-700 rows. At
> the root node alone, we can generate up to 4000 columns, LP for the
> first ones solves very fast, but closer to the end of the root node,
> the LP takes about 4-6 seconds to solve.
>

Just to be sure I'm following this, you're doing branch-and-price (or
branch-price-and-cut), which means you're adding columns to the master
IP at various nodes, and it's the LP relaxations of the node problems
that are taking progressively longer to solve? (I just want to check
this, because CPLEX doesn't do branch-and-price, so if it is
branch-and-price you must be using CPLEX within some other framework.)
If I'm getting this right, what algorithm are you using on the node
subproblems? As of version 10.2 (not sure about 11.0), the default
setting of CPLEX's NodeAlg parameter picks dual simplex for the node
LPs. Dual simplex is usually a good choice for branch-and-cut, because
adding cuts makes the previous solution superoptimal but infeasible.
Adding columns, however, makes the previous solution feasible but
suboptimal. So maybe primal simplex (with hot-starting) might be better
on the node problems?

/Paul