Originally posted by: SystemAdmin

[hippohide said:]

Hi there!

I'm solving a mixed integer problem with boolean and linear variables. The linear variables represent flow paths (sequences of arcs) while the boolean variables indicate if an arc may be used or not. Since the number of feasible flow path is huge, i want to apply column generation to generate improving paths.

My first idea was to create the model in cplex as a regular MIP with a subset of flow paths, then solve the model, call SolveFixed to get some dual values that can be used to generate improving flow paths, add them, and then start over again.

At first, this approach seemed to work quite well, but after some testing with smaller instances that can be solved with all flow paths generated apriori, i noticed that the optimal solution found using the MIP-column generation procedure does not match the real optimal integer solution found using all columns.

Now, i'm wondering if the procedure is valid or if i have to implement Branch-And-Price to obtain the optimal solution.

Thanks for any comments,

Steve
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

[prubin said:]

First thing to check is whether your final MIP in the column generation approach is actually missing any paths from the true optimal solution, or whether you have all the right paths but somehow not added correctly to the MIP.

Assuming not all paths from the true optimal solution are represented in the final CG MIP, I'd look at the duals from the last iteration (I assume termination is because the column generator can't find a new path using those last duals).  Do any of the paths from the true optimal solution that are not included in the CG MIP price out favorably with those duals?  If yes, why didn't the column generator find them?  If no, the duals would appear to be suspect.

The Gilmore-Gomory method for solving 1-D cutting stock problems can terminate with a suboptimal solution (I've seen it happen), so it may well be you do need a full BCP implementation.  I'd just do the above checks first, because fixing what you've got (if it's broken) is liable to be less work than moving to BCP, which will require new software.

/Paul

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

[hippohide said:]

Hi Paul,

thanks for the quick reply. I checked what you told me and it looks like this:

1) not all paths from the true optimal solution are represented in the final CG MIP
2) none of the paths from the true optimal solution that are not included in the CG MIP price out favorably (max 2,22044604925031E-16, and i'm working with higher profits/costs)

-> must be a problem with the duals. Since i'm using the same model and code for adding paths, i think the improving paths are correctly linked to constraints.

What do you think? What about the cuts (e.g. implied bound cuts) that CPLEX is adding when solving the MIP? Do i need to grap these duals as well?

Thanks,

Steve
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

[prubin said:]

[quote author=hippohide link=topic=1421.msg4008#msg4008 date=1256231879]

1) not all paths from the true optimal solution are represented in the final CG MIP
2) none of the paths from the true optimal solution that are not included in the CG MIP price out favorably (max 2,22044604925031E-16, and i'm working with higher profits/costs)

-> must be a problem with the duals. Since i'm using the same model and code for adding paths, i think the improving paths are correctly linked to constraints.


This could mean that, like Gilmore-Gomory, your heuristic will not always get an optimal solution.  By solving your master problem and then fixing the integer variables, you get duals that should tell you whether a new column would improve the LP portion of the solution given those integer decisions; I don't know that it would necessarily let you find a column that would cause you to change the integer decisions.

[quote author=hippohide link=topic=1421.msg4008#msg4008 date=1256231879]
What do you think? What about the cuts (e.g. implied bound cuts) that CPLEX is adding when solving the MIP? Do i need to grap these duals as well?


No, those cuts should have no effect on column generation (not to mention you wouldn't be able to use their duals anyway -- the cuts don't exist in the column generation problem).

If you are confident that the duals of the fixed LP from the final MIP solution are being applied correctly in the column generator, then I suspect you've hit a dead end and need to do a branch-price-cut implementation.

/Paul
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

[hippohide said:]

Thanks a lot, Paul! I was fearing that I might have to do the extra work and implement B&B, but at least now i can be sure it's inevitable!

Steve
#CPLEXOptimizers
#DecisionOptimization