Originally posted by: SifengLin

I developed some effective user cuts to improve the upper bound ( for my maximization problem) considerably.  But it is disappointing that the feasible solutions found by the strengthened formulation are not as good as the original formulation.  Do anyone have any leads on this?

My problem is a multi-commodity network flow problem, with some type of shared constraints between commodities.  Almost all of the constraints and cuts are in the form of

x1+x2+...+xn<=1.

My suspicion is that the strengthened formulation makes the x variables more "fractional".  For example, in one instance number of infeasible( fractional) variables raises from around 2000 to more than 4000.  Is this because more "fractional" solutions somehow make CPELX heuristics ( e.g., rounding heuristics and local improvement heuristics) less effective?

Is there any systematic study on this topic?

Thanks.

You are exactly right: Many heuristics involve the current fractional solution in one way or the other. So depending on that solution they may or may not find a (good) feasible solution. The exact effects and the exact interplay of heuristics and the fractional solutions highly depends on your model and the heuristics you run.

When does CPLEX usually find the good solutions if you do not use your cutting planes? If they are found early it might be an option to run CPLEX for a few nodes without your cutting planes and then either start separating your cutting planes or restart with the best solution as MIP start and cutting planes enabled.

Originally posted by: SifengLin

Thanks for your insightful reply and suggestion.  There are some problem instances with good solutions found in early stage in the model without applying the cutting planes.  I may try to implement your idea after more investigations.  Regarding your first idea ( separate the cuts after a few nodes), I have some concerns:

1. I noticed that almost all cuts discovered by CPLEX are discovered at root node.  Do we also have an option to postpone adding these cuts? 

2. As I know it,  heuristics are at least applied before adding any cuts and after adding all the possible cuts at root node.  Are heuristics also applied during the process of adding cuts?  Do we users have any control over this?

3.  If I delay adding of my own cuts after a few nodes, will it increase the time CPLEX uses to find new cuts?

Thanks.

Sifeng

1. No. The cut loop performend at the root node is quite different from the cut loops performed at nodes within the tree. For some cuts one can set the separation level to 2 (aggressive) which makes it more likely that they are separated at nodes within the tree but still this is not the same as the root cut loop.

2. Yes, CPLEX heuristics are also invoked during cut separation. There is no way for the user to control that.

3. Whether or when adding your cuts influences CPLEX in a good or bad way heavily depends on your problem and the cuts you add. You will have to just try and see what happens.