Topic
  • 13 replies
  • Latest Post - ‏2013-03-15T18:43:56Z by SystemAdmin
mhoang
mhoang
9 Posts

Pinned topic Heuristic callback or incumbent callback or something else?

‏2013-03-10T16:57:39Z |
Hi,

I have to solve a Mip in which the objective function = f(x) + g(x) where f(x) is linear but g(x) is non-linear and depends on an integer solution of model. My idea is that I will solve a Mip with objective function f(x) and whenever an integer solution is found, I will update the incumbent by the sum of current objective and g(x).

I don't know if Cplex can do it. As far as I know, heuristic callback can change the current incumbent value but it is not called if a feasible integer solution is found. On the other hand, incumbent callback can be called whenever a feasible integer solution is found but it can not change the current incumbent value. Can anyone help me on that one?

Thank you,

Hà Hoàng
Updated on 2013-03-15T18:43:56Z at 2013-03-15T18:43:56Z by SystemAdmin
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: Heuristic callback or incumbent callback or something else?

    ‏2013-03-10T21:45:08Z  
    If I understand your strategy, it has a fundamental flaw unrelated to CPLEX. What prevents the solver from pruning a node at which the value of f(x) in the node solution is inferior to the incumbent but would be better than the incumbent with g(x) added?

    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)
  • mhoang
    mhoang
    9 Posts

    Re: Heuristic callback or incumbent callback or something else?

    ‏2013-03-10T22:37:37Z  
    If I understand your strategy, it has a fundamental flaw unrelated to CPLEX. What prevents the solver from pruning a node at which the value of f(x) in the node solution is inferior to the incumbent but would be better than the incumbent with g(x) added?

    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)
    Thank you Paul for your answer,

    But in my strategy, I mean the incumbents are always with g(x) added. At each node at which a feasible integer solution (x*) is found, the new incumbent is smaller value between {current incumbent} and {f(x*) + g(x*)}. Note that we have a minimizing MIP and g(x) is always positive. So if we have a node at which the value of f(x)+g(x) (or even if only f(x)) in the node solution is worse than the current incumbent, the solver will prune it.

    Hoàng.
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: Heuristic callback or incumbent callback or something else?

    ‏2013-03-11T03:29:20Z  
    • mhoang
    • ‏2013-03-10T22:37:37Z
    Thank you Paul for your answer,

    But in my strategy, I mean the incumbents are always with g(x) added. At each node at which a feasible integer solution (x*) is found, the new incumbent is smaller value between {current incumbent} and {f(x*) + g(x*)}. Note that we have a minimizing MIP and g(x) is always positive. So if we have a node at which the value of f(x)+g(x) (or even if only f(x)) in the node solution is worse than the current incumbent, the solver will prune it.

    Hoàng.
    Minimizing with g nonnegative does make the strategy plausible.

    Is x entirely binary, entirely integer, or a mix of integer and continuous variables?

    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)
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: Heuristic callback or incumbent callback or something else?

    ‏2013-03-11T08:13:25Z  
    The heuristic callback allows to specify the objective function of a solution. So what you could do is the following:
    1. install an incumbent callback that stores each feasible solution in a global queue and then rejects it.
    2. install a heuristic callback that picks up feasible solutions from the global queue and injects them with the updated objective.
    You would have to be careful not to end up in an endless cycle if the incumbent callback is invoked got a solution that was injected by the heuristic callback.
    However, it is not immediately clear to me whether your approach will work since CPLEX usually assumes that it sees the full objective function. You would be doing something that is outside the intended scope of CPLEX (it may still work, though).
    What kind of non-linear function is g(x)? If it is quadratic then CPLEX can handle it directly.
  • mhoang
    mhoang
    9 Posts

    Re: Heuristic callback or incumbent callback or something else?

    ‏2013-03-11T14:49:20Z  
    Paul: The variables in my model are binary and integer only. I don't have continuous ones.
    Daniel: g(x) is a probability function and can be calculated if the integer solution becomes known. I will try your idea to tackle the problem.
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: Heuristic callback or incumbent callback or something else?

    ‏2013-03-11T21:13:40Z  
    • mhoang
    • ‏2013-03-11T14:49:20Z
    Paul: The variables in my model are binary and integer only. I don't have continuous ones.
    Daniel: g(x) is a probability function and can be calculated if the integer solution becomes known. I will try your idea to tackle the problem.
    The reason I asked about the nature of x is that I have in mind a modified version of what Daniel suggested. You could incorporate a continuous variable z >= 0 designed to act as a placeholder for g(x). It would initially be unconstrained, so you would probably have to disable presolving to prevent it from being eliminated.

    Now employ a lazy constraint callback, which would be called every time a proposed incumbent is found. The callback would compute g(x); we'll call the result G. If the value of z in the incumbent is >= G (assuming you are minimizing), the callback does nothing and the incumbent is accepted. If the value of z is < G (by some rounding tolerance), the callback adds a cut of the form

    z >= G*<expression>

    where <expression> is a linear expression of x that evaluates to 1 at the value of x specified in the proposed incumbent and to something less than or equal to 0 for every other x. Such expressions are easily written when x is all binary; for general integer x, there are ways to get such an expression but they typically involve something tedious (such as doing a binary expansion of each x_j).

    Using a lazy constraint callback should guarantee that proposed incumbents do not repeat, and will also give CPLEX some guidance (however feeble) on what to do when an incumbent is rejected.

    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)
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: Heuristic callback or incumbent callback or something else?

    ‏2013-03-12T07:00:33Z  
    The reason I asked about the nature of x is that I have in mind a modified version of what Daniel suggested. You could incorporate a continuous variable z >= 0 designed to act as a placeholder for g(x). It would initially be unconstrained, so you would probably have to disable presolving to prevent it from being eliminated.

    Now employ a lazy constraint callback, which would be called every time a proposed incumbent is found. The callback would compute g(x); we'll call the result G. If the value of z in the incumbent is >= G (assuming you are minimizing), the callback does nothing and the incumbent is accepted. If the value of z is < G (by some rounding tolerance), the callback adds a cut of the form

    z >= G*<expression>

    where <expression> is a linear expression of x that evaluates to 1 at the value of x specified in the proposed incumbent and to something less than or equal to 0 for every other x. Such expressions are easily written when x is all binary; for general integer x, there are ways to get such an expression but they typically involve something tedious (such as doing a binary expansion of each x_j).

    Using a lazy constraint callback should guarantee that proposed incumbents do not repeat, and will also give CPLEX some guidance (however feeble) on what to do when an incumbent is rejected.

    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)
    If you can do what Paul describes then I strongly suggest you do that.
    It is much more stable and much more likely to work.
    If you stay with using the incumbent and lazy constraint callback then notice that you need to take special care if the incumbent callback rejects an integral node: in this case you also need a branch callback that will explicitly prune that node (usually CPLEX will not branch on an integral node but if that node is rejected then it has to branch).
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: Heuristic callback or incumbent callback or something else?

    ‏2013-03-12T20:50:26Z  
    If you can do what Paul describes then I strongly suggest you do that.
    It is much more stable and much more likely to work.
    If you stay with using the incumbent and lazy constraint callback then notice that you need to take special care if the incumbent callback rejects an integral node: in this case you also need a branch callback that will explicitly prune that node (usually CPLEX will not branch on an integral node but if that node is rejected then it has to branch).
    I'm not sure it is automatically safe to prune the node: there could be another integer-feasible solution, with different g() value, hiding in the same node. I also don't know a good way to determine if that is the case (and, if so, a good way to separate the node) or if it is safe to prune.

    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)
  • mhoang
    mhoang
    9 Posts

    Re: Heuristic callback or incumbent callback or something else?

    ‏2013-03-12T22:42:06Z  
    It made me suprised when incumbent callback rejects an integer solution, CPLEX will still branch on that solution. How does CPLEX work in such case? And it seems that with Paul's idea, we don't need to use incumbent callback to reject an infeasible integer solution?

    @Paul: I can imagine the way to write <expression> for purely binary variables. But I don't know how we can do for general integer variables. Please tell me more about it! What do you mean "binary expansion"? DO we need to use more binary variables for each x_j? Thank you!
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: Heuristic callback or incumbent callback or something else?

    ‏2013-03-13T21:12:33Z  
    • mhoang
    • ‏2013-03-12T22:42:06Z
    It made me suprised when incumbent callback rejects an integer solution, CPLEX will still branch on that solution. How does CPLEX work in such case? And it seems that with Paul's idea, we don't need to use incumbent callback to reject an infeasible integer solution?

    @Paul: I can imagine the way to write <expression> for purely binary variables. But I don't know how we can do for general integer variables. Please tell me more about it! What do you mean "binary expansion"? DO we need to use more binary variables for each x_j? Thank you!
    > mhoang wrote:
    > It made me suprised when incumbent callback rejects an integer solution, CPLEX will still branch on that solution.

    There could very easily be more than one integer-feasible solution at that node. If you don't like the one CPLEX picked and prune the node, you throw away all the others, which might include an optimal solution. So if you reject an incumbent in an incumbent callback, CPLEX tries to explore the rest of the node by separating it.

    > How does CPLEX work in such case?

    I think it arbitrarily picks a variable (which will be an integer if the incumbent you rejected was a solution to the node LP, as opposed to one found by a heuristic) and splits it the usual way (round up, round down). One of the IBMers can say more definitely.

    > And it seems that with Paul's idea, we don't need to use incumbent callback to reject an infeasible integer solution?

    Correct. Rather than just rejecting it, you add a constraint that cuts it off (makes it infeasible). This also gives CPLEX a modified LP problem to play with, so it does not have to guess how to separate the current node.
    >
    > @Paul: I can imagine the way to write <expression> for purely binary variables. But I don't know how we can do for general integer variables. Please tell me more about it! What do you mean "binary expansion"? DO we need to use more binary variables for each x_j?

    Yes. I go into it a bit in this post, in the section on general integer variables. The first approach in that section would work if you stop the solver, added the exclusion constraint and restarted, but it will not work in a callback, since you cannot add variables on the fly in CPLEX. (You could hypothetically create a pool of binary variables to be used excluding incumbents and add them to the model at the start, initially unconstrained, but that's probably worse than just using a binary expansion in the first place.)

    Incidentally, if you write an integer variable as a sum of binary variables, you do not have to declare the original variable integer; you can make it a real variable, since the binary expansion will limit it to integer values.

    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)
  • mhoang
    mhoang
    9 Posts

    Re: Heuristic callback or incumbent callback or something else?

    ‏2013-03-15T13:09:13Z  
    > mhoang wrote:
    > It made me suprised when incumbent callback rejects an integer solution, CPLEX will still branch on that solution.

    There could very easily be more than one integer-feasible solution at that node. If you don't like the one CPLEX picked and prune the node, you throw away all the others, which might include an optimal solution. So if you reject an incumbent in an incumbent callback, CPLEX tries to explore the rest of the node by separating it.

    > How does CPLEX work in such case?

    I think it arbitrarily picks a variable (which will be an integer if the incumbent you rejected was a solution to the node LP, as opposed to one found by a heuristic) and splits it the usual way (round up, round down). One of the IBMers can say more definitely.

    > And it seems that with Paul's idea, we don't need to use incumbent callback to reject an infeasible integer solution?

    Correct. Rather than just rejecting it, you add a constraint that cuts it off (makes it infeasible). This also gives CPLEX a modified LP problem to play with, so it does not have to guess how to separate the current node.
    >
    > @Paul: I can imagine the way to write <expression> for purely binary variables. But I don't know how we can do for general integer variables. Please tell me more about it! What do you mean "binary expansion"? DO we need to use more binary variables for each x_j?

    Yes. I go into it a bit in this post, in the section on general integer variables. The first approach in that section would work if you stop the solver, added the exclusion constraint and restarted, but it will not work in a callback, since you cannot add variables on the fly in CPLEX. (You could hypothetically create a pool of binary variables to be used excluding incumbents and add them to the model at the start, initially unconstrained, but that's probably worse than just using a binary expansion in the first place.)

    Incidentally, if you write an integer variable as a sum of binary variables, you do not have to declare the original variable integer; you can make it a real variable, since the binary expansion will limit it to integer values.

    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)
    Paul: Thank you so much for your answer. Your trategy must work well for my problem.

    But another problem that I suspect is due to Cplex. I'm using Cplex 12.1 and it did not have lazy constraint callback. So I used CPXsetcutcallbackfunc and CPXcutcallbackadd to add exclusion constraints. To make sure the constraints are added only for integer solutions, I used CPX_INTEGER_INFEASIBLE to check if a solution is integer feasible.

    And sometimes I observed that Cplex could accept an integer solution without passing through cut callback. So CPXsetcutcallbackfunc in CPLEX 12.1 is NOT called for the node that is integer feasible?
  • mhoang
    mhoang
    9 Posts

    Re: Heuristic callback or incumbent callback or something else?

    ‏2013-03-15T14:51:56Z  
    Paul: I have just read again some threads in the forum and maybe I found the answer for my question from one of your comments:

    "The comment you cited applies to earlier versions of CPLEX. If you are using 12.3 (or higher, when hight becomes available), you can ignore it. As of 12.3, all you need is a LazyConstraintCallback that tests the proposed incumbent and, if it found wanting, adds a Benders cut that makes the proposed solution infeasible.

    With earlier versions, I had to use three callbacks (cut, incumbent and branch). I'll skip the details unless they are necessary (meaning you're on an older version and can't upgrade).

    Paul"

    So as I understand, to solve a model that requires lazy constraints (for example, subtour elimination constraints in Traveling Salesman Problem) by C language + CPLEX (before 12.2), we can not use CPXsetcutcallbackfunc cut callback ONLY and have to combine three callbacks (cut, incumbent and branch) at the same. Paul, could you please confirm me that one?
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: Heuristic callback or incumbent callback or something else?

    ‏2013-03-15T18:43:56Z  
    • mhoang
    • ‏2013-03-15T14:51:56Z
    Paul: I have just read again some threads in the forum and maybe I found the answer for my question from one of your comments:

    "The comment you cited applies to earlier versions of CPLEX. If you are using 12.3 (or higher, when hight becomes available), you can ignore it. As of 12.3, all you need is a LazyConstraintCallback that tests the proposed incumbent and, if it found wanting, adds a Benders cut that makes the proposed solution infeasible.

    With earlier versions, I had to use three callbacks (cut, incumbent and branch). I'll skip the details unless they are necessary (meaning you're on an older version and can't upgrade).

    Paul"

    So as I understand, to solve a model that requires lazy constraints (for example, subtour elimination constraints in Traveling Salesman Problem) by C language + CPLEX (before 12.2), we can not use CPXsetcutcallbackfunc cut callback ONLY and have to combine three callbacks (cut, incumbent and branch) at the same. Paul, could you please confirm me that one?
    Yes, I believe that is correct.

    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)