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

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