[SCIP] Implementing no-good cuts that cuts off feasible solutions

[Gerald Gamrath]

Hi Matheus,

I think there are multiple options how to make this work.

First, if you want to store data at a node, you need to write a 
constraint handler and add constraints to the nodes. Please have a look 
at this FAQ about branch-and-price, where something similar is done: 
https://www.scipopt.org/doc/html/FAQ.php#pricerandnodedata

On the other hand, I would argue that there may be a more SCIP-ish way 
to achieve what you want. Recall that the CIP concept asks for a linear 
objective, but allows for (almost) arbitrary constraints. So my 
suggestion would be to introduce an auxiliary variable z, change your 
objective to c^T x + z and add a new constraint handler, which is 
responsible for ensuring that z = f(x). Now, this constraint handler can 
always check if that relation is fulfilled and, if not, reject a given 
solution candidate. When doing that, it could compute the correct z 
value and add this updated solution. I guess it should not add it 
directly to SCIP, since this would then result in some recursive call of 
the solution checking, but you can pass it to heur_trysol, which will 
then try to add that solution at the next-possible time. If you would be 
able to compute bounds on z based on the partial fixings of x columns at 
the current node, your constraint handler could even tighten the bound 
of z, leading to better dual bounds.

I hope this helps,

Gerald

On 10/19/23 14:08, Matheus Ota wrote:
> Hi Leon,
>
> Thanks for the email. You are right, this is another part of the 
> context that I forgot to mention: the function f(.) is non-negative. 
> Thus, if x' is an LP solution obtained at a node of the 
> branch-and-bound tree, \bar{x} is the best (integer) solution found so 
> far, and c^T x' >= c^T \bar{x} + f(\bar{x}), then we can prune the 
> node of x' (since c^T x' + f(x') >= c^T x').
>
> I don't want to count/enumerate all integer feasible points, what I'm 
> trying to do is to solve an optimization problem with a "strange" f(.) 
> function that I just know how to compute for integer points. After 
> thinking a while about how to do this in SCIP, I think my question 
> boils down to these two points:
> 1. Is it possible to update the best feasible solution "manually" 
> inside the callback? Or maybe just updating the primal bound value.
> 2. Alternatively, when branching, is it possible for me to create some 
> type of "node data"? If so, I guess I can create a flag for the nodes 
> that correspond to a single feasible point. I think this may be 
> possible, but I don't know where to look for an example. I have a 
> custom branching rule already, so maybe when creating the child nodes, 
> I can flag some nodes as "special", and then when checking feasibility 
> in the callback, I know that "special" nodes actually correspond to a 
> single feasible solution.
>
> Thanks again for your attention,
> Matheus
>
> Em qui., 19 de out. de 2023 às 02:10, Leon Eifler <eifler at zib.de> 
> escreveu:
>
>     Hi Matheus,
>
>     I am a bit confused: Wouldn't the pruning of nodes using the
>     objective value of \bar{x} in your case be invalid since you have
>     that nonlinear part to consider? Is adding f to the model and
>     solving a MINLP not an option for you?
>
>     In any case, I wanted to mention that SCIP already contains a
>     feature to count/enumerate all integer-feasible solutions:
>     https://www.scipopt.org/doc/html/COUNTER.php#COLLECTALLFEASEBLES
>
>     I hope this helps,
>
>     Leon
>
>     Am 10/18/2023 um 8:42 PM schrieb Matheus Ota:
>>     Sorry, there is a problem in the way I phrased the question. The
>>     objective value of solution \bar{x} is not given by just c^T
>>     \bar{x}, but by c^T \bar{x} + f(\bar{x}), where f is some
>>     non-linear function that I know how to compute whenever \bar{x}
>>     is feasible. So if solving the LP relaxation returns an integer
>>     feasible point \bar{x}, it does not necessarily mean that \bar{x}
>>     is optimal (because of the f(.) function). This f() function
>>     creates the need to enumerate with the no-good cuts.
>>
>>     Em qua., 18 de out. de 2023 às 14:32, Matheus Ota
>>     <matheusota at gmail.com> escreveu:
>>
>>         Dear SCIP Team,
>>
>>         I want to implement a no-good cut (that cuts off a single
>>         integer point of the feasible region) but I don't know how to
>>         proceed. Suppose that I want to solve the following problem:
>>         (P)     min cx
>>                   s.t.  Ax <= b
>>                          x binary
>>
>>         Suppose that \bar{x} is feasible for (P), then I can cut off
>>         just \bar{x} by using the "no-good cut"
>>         \sum_{i : \bar{x}_i = 0} x_i + \sum_{i : \bar{x}_i = 1} (1 -
>>         x_i) >= 1.
>>
>>         Note that I'm not requesting the no-good cut to be feasible
>>         for (P). This is because I want to essentially use SCIP to
>>         enumerate the solutions. I want to do the following process:
>>         1. Get a feasible solution \bar{x} to (P).
>>         2. Compare \bar{x} with the best feasible solution found so
>>         far, and update the best solution found if \bar{x} is better
>>         than the current one.
>>         3. Remove \bar{x} with a no-good cut.
>>
>>         Since I'm always removing a feasible point, in the end of the
>>         branch-and-bound, it should return that the problem is
>>         infeasible. However, I don't want to simply "discard"
>>         \bar{x}. I want to use the objective value of \bar{x} to
>>         possibly prune more nodes of the branch-and-bound tree. Do
>>         you have any suggestions on how to implement this?
>>
>>         The first idea that came to my mind was to branch whenever I
>>         find a feasible solution \bar{x}. Then in the left branch
>>         node I only have { \bar{x} } as the feasible region and in
>>         the right branch node I add the no-good cut that cuts off
>>         \bar{x}. The problem with this approach is that, if I'm on
>>         the left branch node, once I get a solution \bar{x} in the
>>         CONSCHECK method, I don't know how to differentiate if this
>>         is the first time that I've found \bar{x} (in which case I
>>         should branch) or if this is the second time that I've found
>>         it (in which case I'm on the left branch node, and I should
>>         just return that the solution is feasible). Also, I'm not
>>         totally sure that this is the "correct" approach to use.
>>
>>         Sorry for the long email, and any help is appreciated.
>>
>>         Best,
>>         Matheus
>>
>>
>>     _______________________________________________
>>     Scip mailing list
>>     Scip at zib.de
>>     https://listserv.zib.de/mailman/listinfo/scip
>     _______________________________________________
>     Scip mailing list
>     Scip at zib.de
>     https://listserv.zib.de/mailman/listinfo/scip
>
>
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> https://listserv.zib.de/mailman/listinfo/scip
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20231019/84b7e3bd/attachment.html>