sci.op-research

On Feb 5, 9:07=A0am, "ltl...@gmail.com" wrote:
> 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? =A0(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? =A0As of version 10.2 (not sure about 11.0), the default
> > setting of CPLEX's NodeAlg parameter picks dual simplex for the node
> > LPs. =A0Dual simplex is usually a good choice for branch-and-cut, becaus=
e
> > adding cuts makes the previous solution superoptimal but infeasible.
> > Adding columns, however, makes the previous solution feasible but
> > suboptimal. =A0So maybe primal simplex (with hot-starting) might be bett=
er
> > 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.

hi Loan,

saving time on LP, you may not need to solve it to optimality. Being
close is enough, and would save time due to the 'tailing-off' effect
of column generation.

cheers,

ttCLW