sci.op-research

On Feb 3, 3:46 pm, Paul Rubin wrote:
> ltl...@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

Hi Paul,

Yes, I'm building my own branch-price-cut framework where at each
node:
1. Cplex is used to solve the LP at each node,
2. one column with the most negative reduced cost is then generated
and added to the LP master problem,
3. Resolve LP master problem
4. When no more column can be found, a lazy cut, if violated, is added
and the node solution process goes back to 1.
5. Branch if no more column found and no more lazy cut violated

So far I use the default LP algorithm, which I assume dual simplex. So
should I try primal simplex at the beginning of the column generation
subprocess, switch to dual after a cut is found, then switch back to
primal simplex, and so on?

To TTCLW:

I did solve to optimality, it might take a long time, but a good
branching helps make a difference. For a problem instance that I'm
testing, I could go straight to one of the optimums. However, I notice
that my pricing formula still generate many inefficient columns that I
think is the main gridlock, and I'm trying to avoid that.

I'm fortunate to have pretty good computational resources, but I think
good branching might minimize the memory needed as it helps you to
proceed in the right direction. It seems to me that removing non-basic
variables wouldn't help much, as I might regenerate them later. But I
might try this.

Thanks a lot,

Loan.