Originally posted by: SystemAdmin

I have a maximization problem with a variables bound to 0 and 10e18 (just below what cplex sees infinity).
if I solve it just like that I get solution.
if I use any callback, only declaring a null callback which does not do anything, cplex log reports unbounded but status is infeasible.
If I turn:

cplex.setParam(IloCplex::Reduce, CPX_PREREDUCE_NOPRIMALORDUAL );

I get unbounded in log and unbounded in status (getCplexStatus).

I use only insgle thread.
Does anyone know what is going on here?
I very much appreciate any comments.
#DecisionOptimization
#MathematicalProgramming-General

Originally posted by: SystemAdmin

With such a large but finite bound, I guess that presolve can have a very hard time in terms of numerics. So, small changes in the parameters can have the effect that you are observing. And installing a callback (if this is not the info callback) turns off dynamic search. Could it be that this is the difference?

Additionally, having a callback in place (even if empty) can lead to subtle differences in the solving path.

Which callback are you using? Is it really presolve that claims infeasibility or unboundness? Or is it the root LP solve?

Tobias
#DecisionOptimization
#MathematicalProgramming-General

Originally posted by: SystemAdmin

>>> With such a large but finite bound, I guess that presolve can have a very hard time in terms of numerics. So, small changes in the parameters can have the effect that you are observing. And installing a callback (if this is not the info callback) turns off dynamic search. Could it be that this is the difference?

Apparently this is the case.

>>> Additionally, having a callback in place (even if empty) can lead to subtle differences in the solving path.
Yes I understand as it comes as awarning that some features are disabled.

>>> Which callback are you using? Is it really presolve that claims infeasibility or unboundness? Or is it the root LP solve?
Both incumbent and cutcallbacks I use but I have no answer for the second part of your question. I learned to set the followings and now it works fine.

cplex.setParam(IloCplex::PreInd, 0 ); cplex.setParam(IloCplex::PreDual, -1 ); cplex.setParam(IloCplex::AggInd, 0 ); cplex.setParam(IloCplex::AggFill, 0 );

#DecisionOptimization
#MathematicalProgramming-General

Originally posted by: SystemAdmin

Hi again,

for the same problem above,as soon as the first integer feasible solution has been found the solver termnates with optimality and does not call the CUTcallback.
But I am not sure if that is the optimal solution because this is relaxation of the original problem (in fact any integer feasible solution is optimal for this relaxation).
I guess that it has been found by heuristic that might be the reason why the cuttcallback is not called.
The only way so far has been to reject the incumbent and separate the cuts but this is tricky because the rejected solution hmight alctually have been optimal in the original.
What can be done here to enforce cplex to call the cut callback btefore his premature convergence and not loosing any "potentially" optimal solution.

any comment is appreciated.
#DecisionOptimization
#MathematicalProgramming-General

Originally posted by: SystemAdmin

I am not sure whether I understand the issue completely.
What I get from your mail is that you can check the feasibility of a solution (with respect to your original problem) inside the cut callback. So, when a heuristic finds a solution candidate, you reject it and store it somewhere in order to then separate cuts in the cut callback to cut off this solution. But the issue is that if now the cut callback does not find any violated cuts, you have rejected a solution candidate that is actually feasible in your original problem. Did I understand the issue correctly?

If so, then my question is why you cannot check the feasibility in the original problem already in the incumbent callback?

Typically, the incumbent callback should just check feasibility and accept or reject a solution.
The cut callback should check feasibility, and if the solution is infeasible it should generate a cut to separate it from the LP relaxation.

Separating cuts for solutions that came from heuristics is probably not very helpful, as these solutions can be pretty far away from any LP optimal solutions at the nodes of the search tree.

Tobias
#DecisionOptimization
#MathematicalProgramming-General

Originally posted by: SystemAdmin

I think I must be more clear.
I solve the mip. It has a finitely large bounded variable in objective and the problem is a maximization.
setting the presolved off then it goes to cut callback for all fractional solutions before meeting the integer feasible one.
when finds a integer feasible solution visits the incumbent callback but not the cutcallback afterwrds such that the feasibility w.r. to the original model be tested.
The problem is here what to do to enforce it to visit the cutcallback.

My way is to reject the incumbent. This helps to go to cut callback but I dont know maybe the one i rejected was already the optimal?!?

this is the whle difficulties.
#DecisionOptimization
#MathematicalProgramming-General

Originally posted by: SystemAdmin

But your cut callback implements a feasibility check: if the cut callback finds a violated cut, the solution is infeasible. If it does not find a violated cut, the solution is feasible.

Instead of just rejecting every solution in the incumbent callback, you should also add a feasibility test to the incumbent callback. You could just call your separator and check whether it finds violated cuts (without actually passing them to CPLEX, as this is not possible in the incumbent callback). But typically, checking feasibility is much easier than producing violated cuts for infeasible solutions, so I guess the feasibility test in the incumbent callback can be much simpler than the separator that you call from the cut callback.

Let's use the TSP as an example, modeled by the standard degree constraints plus a separator for sub-tour elimination constraints. In your cut callback, you would try to find violated sub-tour constraints for fractional and integral solutions. For fractional solutions, this can be done, for example, by constructing a Gomory-Hu tree. For integral solutions, it is much simpler: just consider the sub-graph defined by the edge variables set to 1 in the integral solution. Start at some random node and follow the edges until you get back to the start node. If you visited all nodes, the solution is valid, if not you have found a sub-tour and can add a corresponding sub-tour elimination constraint.
The incumbent callback is much simpler: just call the same procedure as in the cut callback for integral solutions. If all nodes are visited, accept the solution. If not, instead of actually generating the sub-tour elimination constraint, just reject the solution.
#DecisionOptimization
#MathematicalProgramming-General

Originally posted by: SystemAdmin

Thanks for the comments.
I know that all the integer feasible solutions are feasible as a part of a feasible solutuon to the original problem and I only need to generate the rest of the solution(compelet solution in the original model) for every integer solution , add it as an optimality cut until closes the gap. So there is no one to be rejected.
All going to be completeed. that means once an integer feasible to the problem has been found the complementary part must be made.

what I said is that after finding the first integer feasible instead of letting me go in the cut callback it terminates. if once I reject the integer feasible solution it lets me to go in cut callback but this is dangerous as it might have been the real solution.
It is not the best idea to implement the separtion also in the incumbenebt callback because it is very expensive.
#DecisionOptimization
#MathematicalProgramming-General

Originally posted by: SystemAdmin

So what you want to do is similar to solving a machine scheduling problem, where you let the MIP part find job -> machine assignments and something else (for example a CP solver) check whether there exists a valid schedule for a particular assignment, right? The master problem would be the MIP assignment problem, while the sub problems would be the scheduling problems on the individual machines.

What you are saying is that you do not want to check the feasibility of a solution candidate (i.e., whether it can be extended to a full solution or not) in the incumbent callback, because this is too expensive. But ultimately, you need to check this anyway, so deferring this to the cut callback will not avoid this work. The only beneficial thing that I can imagine is that you could avoid checking bad solutions that came out of CPLEX heuristics.

I think the easiest and cleanest way would be to just do the check in the incumbent callback.
If this is not possible, could you store the solution candidates in a queue and reject everything in the incumbent callback? Then, in the cut callback check the queue in a reasonable order. And if CPXmipopt() terminates while still having solution candidates in the queue, you need to check these remaining candidates afterwards in order to get the true optimal solution.
#DecisionOptimization
#MathematicalProgramming-General

Originally posted by: SystemAdmin

>>So what you want to do is similar to solving a machine scheduling problem, where you let the MIP part find job -> machine assignments and something else (for example a CP solver) check whether there exists a valid schedule for a particular assignment, right? The master problem would be the MIP assignment problem, while the sub problems would be the scheduling problems on the individual machines.
true- something like this.

>>What you are saying is that you do not want to check the feasibility of a solution candidate (i.e., whether it can be extended to a full solution or not) in the incumbent callback, because this is too expensive. But ultimately, you need to check this anyway, so deferring this to the cut callback will not avoid this work. The only beneficial thing that I can imagine is that you could avoid checking bad solutions that came out of CPLEX heuristics.

no i dont need to ultimately check feasibility. I only need to add optimality cuts.

I think the easiest and cleanest way would be to just do the check in the incumbent callback.
If this is not possible, could you store the solution candidates in a queue and reject everything in the incumbent callback? Then, in the cut callback check the queue in a reasonable order. And if CPXmipopt() terminates while still having solution candidates in the queue, you need to check these remaining candidates afterwards in order to get the true optimal solution.

>> do you mean that I have to queue up zillions of solutions and check them one by one ?!?! is that practically possible?

The solution is to avoid a termination after fiing the first integer feasible solution. How that is the question.
#DecisionOptimization
#MathematicalProgramming-General

Originally posted by: SystemAdmin

It seems that I still do not understand exactly what you are trying to do.

Let us first try to clarify what you want to do on a theoretical level, and then we can discuss how to actually implement this with CPLEX.

Assume the restricted master problem (RMP) is

min  cx s.t. Ax <= b x >= 0 x_i integer 

for i in I

As far as I understand, the full problem (FP) is

min  cx + f(y) s.t. Ax + g(y) <= b h(y) <= d x        >= 0 x_i integer 

for i in I y_j integer 

for j in J

f, g, and h can be anything: linear functions, non-linear functions, or just zero. It would be interesting which of them are actually zero in your application.

Now, in a typical Bender's decomposition approach you solve (RMP) using a MIP solver. Whenever the MIP solver encounters a feasible solution x' for (RMP), you need to find a y' vector such that (x',y') is feasible for (FP). If there is no such y', then you need to prune x' from (RMP), either by just rejecting it and letting the MIP solver continue, or by even introducing a Bender's cut to actively cut off x and hopefully an even larger part of the (RMP) search space.
If you find a y' such that (x',y') is feasible for (FP), then it would be good to restrict (RMP) in such a way that no or at least fewer solutions x" for which cx" + f(y") >= cx' + f(y') for all feasible extensions y" are generated by the (RMP) MIP solve.
If f == 0, this is very easy: just accept x' as feasible solution to (RMP), and the MIP solver will do the rest. If f(y) >= 0 for all y, then you can introduce the objective cutoff cx <= cx' + f(y'). If f(y) can be negative, then it is not so easy.

Does your application fit into this framework? If not, please explain in more detail what you want to do.

What exactly do you mean by "optimality cuts"? Is this the "cx <= cx' + f(y')"?

Why do you think that zillions of solutions would pile up in your queue? The queue would just store all heuristic solutions that are generated between two consecutive calls to your cut callback. Shouldn't be that many.
#DecisionOptimization
#MathematicalProgramming-General

Originally posted by: SystemAdmin

Thanks for the time you put on this:
The FP is the following having all coefficients c, f positive

max  -cx + f(y) s.t. Ax + g(y) <= b h(y) <= d x        >= 0 x_i integer 

for i in I y_j integer 

for j in J

The RMP always generates feasible PARTIAL solution with negative cost which will be completed by a solution to the remaining problem with positive cost. The overall obj value is positive!

max  -cx + phi s.t. Dx  <= b 0<= phi<=10e18 x_i integer 

for i in I

I only need to get a solution from RMP and add the cut.

The RMP terminates on the first integer solutions and this is the problem.
#DecisionOptimization
#MathematicalProgramming-General

Originally posted by: SystemAdmin

Is this really true?
>>> If f == 0, this is very easy: just accept x' as feasible solution to (RMP), and the MIP solver will do the rest.
isnt that like "accept x' as feasible solution to sub problem" ?
#DecisionOptimization
#MathematicalProgramming-General

Originally posted by: SystemAdmin

What Tobias is saying is that if x' is a feasible solution to RMP such that (x', y') is a feasible solution to FP for some y', and if f = 0, then you will accept x' as an incumbent in RMP and never encounter another solution x'' in RMP with c.x'' >= c.x'. Since f= 0 implies FP has the same objective as RMP, you need do no additional work to avoid RMP solutions that will produce feasible but inferior solutions in FP. Underlying this is the assumption that x' will remain feasible in RMP despite any future added cuts, which is true for a typical Benders implementation. At least that's how I read his comment.

/Paul

Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
#DecisionOptimization
#MathematicalProgramming-General

Originally posted by: SystemAdmin

Paul thanks for your comments.
The problem I descibed two posts earlier does nto have any of such structures and treating it in benders required rejection of the first incumbent to avoid premature convergence of master problem if implemented by callback otherwise is not that complicated.
do you know any work dealing with this type of objective function I explained in benders when maximizing a +- model like that.
I am more interested to see hoe they make their cuts. because my cuts are not that strong enough
#DecisionOptimization
#MathematicalProgramming-General

Originally posted by: SystemAdmin

Paul's understanding of my comments is correct. But unfortunately, my comment about just keeping the objective from the FP as objective in the RMP does not apply, because in your case f != 0.

Even worse, if we state your problem as minimization (I always think in terms of minimization, so this is easier for me...), we have

min  cx + f(y) s.t. Ax + g(y) <= b h(y) <= d x        >= 0 x_i integer 

for i in I y_j integer 

for j in J

with f <= 0. Hence we are in the bad case that I described as "If f(y) can be negative, then it is not so easy."

The issue is that if you do nothing about f, you cannot derive any bound in the RMP that allows you to prune nodes solely based on the RMP information about x. This is because even if x has a very large objective function value, there may exist a feasible extension y with f(y) being very negative and thereby better than the current incumbent solution.

In your RMP model that includes the additional variable phi to model the objective function contribution from y, what you will see is that CPLEX always sets the phi variable to 1e+18. I guess you added this very big but finite upper bound to prevent CPLEX from claiming unboundness. In any case, the large objective value of the (x,phi) solution will let the x contribution on the objective be completely dominated by the 1e+18 coming from phi. On the one hand, there is the mipgap parameter that is set to 0.01% by default, which will let CPLEX terminate once a feasible solution has been found, because every (x,phi) is less than 0.01% away from the LP bound (which will also be about 1e+18), as long as phi = 1e+18.
On the other hand, there is the numerical issue. Let's assume that c*x is in the order of 1. For floating point arithmetic with 64 bits we have 1 + 1e+18 == 1 exactly, because 1e+18 is about 2^59, but the mantissa of a double only has 52 bit. Thus, even if you set the mipgap to 0, CPLEX would still think that all solutions in x which only differ by 2^7 = 128 in objective value have exactly the same objective. And this is just theory... in practice we apply some tolerances (even for mipgap 0) that will give you a much larger value than 128.

If you do not have a better bound than 1e+18 on your psi variable, then I think you are in trouble. If you have a better bound, then your approach seems to be viable. But then, I still don't understand what the issue is. It should be possible to just reject all RMP solution candidates coming from CPLEX (which will have psi set to its upper bound), and then just add the very same solution with a correct psi in the heuristic callback.
Tobias
#DecisionOptimization
#MathematicalProgramming-General