Originally posted by: Eumpfenbach

I am trying to use column generation to solve a MIP. I use cplex MATLAB API for the LPs, I do the branching.

So say I solve the root node, branch, and then solve the first child. I can store the basis of the previous node and give it as a start for the child. It is not helping greatly, though. Is there any advanced information you can give me about warm starting? Should I condition my start somehow based on the basis codes of the previous problem? Is cplex's internal method published or proprietary? Any help/clues from the experts would be great.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: Eumpfenbach

Just some further details:

I solve the initial LP relaxation. I save the columns that have basic status 1 or 2 in a vector. I resolve the exact same problem, giving an LP start that has the column and row status from the previous solve (but no columns that have status -1 or 0) and delete the columns that had basis status -1 or 0. The LP solves VERY fast (as expected). The initial solve takes about 60 seconds, the solve with the reduced columns and basis statuses takes under 2.

Now, I repeat the process of only using the columns with status 1 or 2, but do not give Cplex an LP start. It runs so long that I don't even let it finish without finding a solution (at least an hour). I obviously wasn't expecting it to find a solution in under 2 seconds without the LP start, but I was expecting it to find one in under 60 (because there are fewer columns).

Any idea how to explain this? I am aware of things like cycling in simplex but I thought Cplex took care of that for me in solving LPs. I don't change any parameter settings from the default (except turning presolve off in all cases).
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Where do you get the basis status -1? The valid statuses are

#define CPX_AT_LOWER                     0
#define CPX_BASIC                        1
#define CPX_AT_UPPER                     2
#define CPX_FREE_SUPER                   3

Indeed, if you remove columns with basis status 0 (and those have a lower bound value of 0.0), then the problem should have the same optimal objective value, and the optimal solution of the bigger problem should still be optimal in the reduced problem.

It is hard to say why CPLEX is having trouble with the smaller problem. Which algorithm are you using? Primal or dual simplex? Or barrier?
Can you post log files? Maybe something can be seen therein...
Tobias
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: Eumpfenbach

From BasisStatus help:

NotABasicStatus = -1

So I guess based on your comment that a status of -1 should never be seen? I tried a quick problem and it didn't find any columns with status -1. So maybe I am always finding an empty set when I tell Matlab to search the basis for columns with status -1. I will look closer on future runs.

As far as the solution time, I believe I have figured it out. Barrier works well for the initial subproblem solution, then as I add columns, I solve with dual simplex and a warm start. Seems to work fairly well.

I still have an open question I asked here:

http://www.ibm.com/developerworks/forums/thread.jspa?threadID=423620&tstart=90

If I solve my standard problem with cplex, it has 55318 variables and 188485 constraints. When I check the basis statuses after solving for the columns 29110 have basis status 1, 99 have basis status 2, 0 have basis status -1 or 3, and 26109 have basis status 0. For the rows, 159375 have basis status 1, 29110 have basis status of 0. Can you tell me if I am wasting my time trying to do column generation on a problem with these solution statistics? I am pricing in a bunch of the variables with basis status 0, which takes a long time and kills performance. They do nothing to improve the LP value. I don't know if this is normal or not. My first experiment with column generation.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

You will most probably get the -1 basis status only if there is no basis at all (in which case all variables would have basis status -1). This is the case if you did not solve the problem, or if you have solved it with barrier but without crossover.

If you start from an optimal basis and then add new columns, you would typically reoptimize using the primal simplex algorithm. This is because the old basis is still primal feasible when you add new columns, but no longer dual feasible. The dual simplex algorithm would need to go into phase 1 again in this situation, which potentially could lead you pretty far away from primal feasibility, which then has to be recovered again in phase 2. But of course, this is just a general comment and it could be that for your particular problem instance dual simplex is the better choice. Note also that for a number of column generation problems it is the best choice to use barrier (without crossover!) for all LP solves, even though barrier cannot benefit from warm starts. This is because barrier produces a central solution on the optimal face and thus tends to not jump around in the (dual) solution space with consecutive solutions. This often helps to mitigate the tailing-off effect that you often see with column generation.

After solving your LP, it should be possible to remove all variables with basis status 0 (provided that the lower bound is zero for all of them) and all rows with basis status 1, and then solve the model again to get the same optimal objective value (maybe a different solution vector, if you start from scratch).

Are you saying that the full problem has 55k variables, and because the solve times are too large you are trying to use a column generation approach? I do not think that this is useful. Basically, what your pricing algorithm has to do is exactly the same calculation that CPLEX would internally do for the existing columns. So, using a column generation approach here just means to reduce the options that CPLEX has for pivoting. The run-time fo the linear system solves depend more on the number of rows than the number of columns. So, maybe it would be better to use a row generation approach? But even this, I doubt that it will help much. Of course, if you can (because of your knowledge about the problem) identify in advance a large set of rows that is very unlikely to be active in an optimal solution, then row generation (i.e., cutting plane separation) would be a viable option.
Tobias
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: Eumpfenbach

Thank you very, very much Tobias. I need to digest this and experiment now.

I don't really have a great reasoning for column generation other than I want to publish a good paper and can't just rely on an out of the box solve. Later iterations will have more variables and constraints. I am just working with a smaller problem now to work out the kinks.

If I can prove optimality without the rows with status 1 then maybe formulating the dual and doing column generation would be a very good approach. A large portion of the rows fit this description.

Thanks again.
#CPLEXOptimizers
#DecisionOptimization