Originally posted by: Slater_jm

Hello, i am new to cplex in general , and i am doing my master thesis  solving a tsp-like problem,  i am doing a secuential procedure that solves one mip to integrality then i add some constraints (subtours) and keep iterating until i find a full tour solution. in one of the instances i tested , i found that if i start with a lowerbound set to 6000 , i get an optimal solution of 6526 (fake) , while if i start with a lowerbound of 0, i get the true optimal solution being 6547. To me it seems extremely weird and i dont know what might be causing this trouble. Do you guys have any suggestions, maybe something with the gap parameter  ?

thanks in advance

Originally posted by: EdKlotz

When you say you "start with a lowerbound of 0", what exactly do you mean?    Do you mean that is the lower bound CPLEX reports when it solves the initial LP relaxation at the root node of the branch and bound tree?   And does the tighter lower bound arise because of the subtour elimination constraints you add?  Or do you add a constraint on the objective to enforce these lower bounds?  And how do you know that the solution with objective 6526 is not optimal?   Given that you appear to be minimizing, that means you are saying that CPLEX claims an infeasible solution is optimal.   Here are some tactics that might help better assess if that is the case.  While you can execute these within your program, you may find it easier to export a SAV file of the model from your program and do these tests in the interactive CPLEX optimizer.

1)   Check the solution quality.   On some models, solutions that just barely satisfy CPLEX's feasibility and integrality tolerances can have better objectives than expected due to those slight violations.   However, this typically requires some combination of large objective coefficients and numerical instability or ill conditioning, neither of which typically appears in TSP types of problems.   Still, make sure this is not involved.

2)  Change the problem to fixed that yields the supposedly "fake" optimal objective, and solve the fixed LP.   Is it infeasible?   If not, then you should take a look at the solution values and assess why you think there are not acceptable?   Is there some constraint that you think that solution doesn't satisfy?   If so, make sure that constraint is truly present in the model.   One way you can get an objective that is better than expected is if your model is missing some constraints that you intended to include, or if some of the constraints in the model are not exactly the ones you intended

3)   Turn off dual presolve reductions (i.e. set the presolve reduce parameter to 1) and turn off all presolve reductions completely (i.e. set presolve reduce to 0).   Does this change the optimal solution objective value?

4)   Take the model that solves with an optimal solution of 6547, and add a constraint that the objective function must be <= 6526.   Is the resulting model infeasible?   If so, run CPLEX's conflict refiner on this infeasible model to get a minimal set of constraints and bounds that explains why this model is infeasible.    That output should shed some light on what is happening here.

Originally posted by: Slater_jm

Thanks for the answer, ill check ur suggestions further 

Regarding your first questions, first its a maximation problem , i just added a lowerbound  of 0 to see  if the results changes( using  the default value arises the same issue).Second, i actually improve the lowerbound with an heuristic at each iteration,, so i tested with a high lowerbound (6000) to check if the problem persisted (instead of calling the heuristic). Finally 6547 is the optimal solution because i can check it with a full formulation of the model (adding subtour constraints) and  a program that checks if the route is feasible.

Regarding your suggestions , 3), doesnt make a change , 4) (adding >=6547, since its a  maximization problem , yields that optimal value), need to see 1) and 2)

Thanks

Originally posted by: EdKlotz

OK, so since it's a maximization problem, then you are saying that the "fake" optimal solution  with objective 6526 is declaring a sub-optimal solution optimal  My suggestions were predicated on the assumption that you were minimizing since you mentioned subtours, and TSP problems, which involve minimization.  Still suggestion 1) regarding solution quality still makes sense, but primarily for the solution with objective 6547 being less precise than the one with objective of 6526.    Also, for suggestion 2) since you are maximizing, use the solution with objective 6547 for the creation of the fixed LP.  

Regarding your question about whether the MIP gap is involved, I don't think so.   The default MIP gap is .0001, and a solution with objective 6526 for a model with optimal solution of 6547 will not satisfy that gap.   So unless you changed the default relative MIP gap to something larger than about ..003 (or the absolute MIP gap to a value >= 21), the MIP gap is not in play here.

Could you also run the model with CPLEX's symmetry reductions disabled (i.e. 'set presolve symmetry 0' in interactive CPLEX) on the model that claims the 'fake' optimal solution and see if you still get the 'fake' optimal solution?

And one last question (for now):  which version of CPLEX are you using?

Originally posted by: Slater_jm

i did the simmetry reduction and still get the same problem. I am starting to think that maybe  one cut  generation at  one particular cycle might be causing a trouble, maybe when i use a better lowerbound, cplex gets a different solution with same objective value, then the subtour constraints might do smth wrong to that particular cycle found, so when i use the 0 lowerbound, just by luck cplex dont find that cycle that mess up my constraint generation. It seems pretty strange thou since  i ve checked many times that my constraint to avoid cycles  its done correctly, but it might be wrong at some particular  cycle .

im using cplex 12.71

Thanks

Originally posted by: EdKlotz

Regarding your hypothesis about the cut generation causing the issue, try disabling all the cuts and see if you then get consistent results.   From within your program, setting the number of cut passes to -1 is the easiest way to disable all cuts.   From interactive CPLEX, that and 'set mip cut all -1' are equivalent.

I'm still curious to hear what you find regarding the solution quality and fixed problem tests.

Also, based on your comments,  I presume you are setting these lower bounds by adding a constraint that the objective function is >= 6000.  If so, you could instead accomplish the same thing by setting the MIP lowercutoff tolerance to 6000.   This will remove the possibility that the constraint on the objective function affected the cuts generated, so doing this would be a useful test to see if the inconsistent results still reproduce.

Originally posted by: Slater_jm

I used the  lowercutoff parameter  for bounds. Also i think i found the problem , i did 2 types of cuts , the second one involving the starting node had a tiny error that in this particular instance generated a problem i think, i will keep running some test to see  if this is the problem buti think it is.

This might be a little off topic but you cant u add constraints involving new variables inside a callback right?

Thank you.

Originally posted by: EdKlotz

Regarding adding global valid cuts, one useful sanity check to make sure they are correct is to reverse direction of the cut and confirm that the resulting model is infeasible.   In other words if you derive a globally cut with all integer variables such as x1 + x2 + x3 >= 100, then if you instead add the constraint x1 + x2 + x3 <= 99 to the model, the model should become infeasible.   If that does not happen, then your original cut is not globally valid.    Now, this becomes a bit trickier then the cuts involve continuous variables, fractional left hand or right hand side values, or anything else that compromises the integrality of the left and right hand sides in the above examples.   But, you can usually figure out a suitable tolerance for the test.    Note also that this is not valid for symmetry breaking cuts, as they can cut off feasible solutions (just not all optimal solutions), and hence are not globally valid.

If a variable does not exist in the model, you cannot create it first in the callback.    Nor can you make any other problem modifications other than adding cuts or lazy constraints.

Originally posted by: Slater_jm

Thanks for the suggestions  and the answers, the model is working fine now