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

[Matheus Ota]

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20231018/9164ce0b/attachment.html>