<div dir="ltr">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.</div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">Em qua., 18 de out. de 2023 às 14:32, Matheus Ota <<a href="mailto:matheusota@gmail.com">matheusota@gmail.com</a>> escreveu:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr">Dear SCIP Team,<div><br></div><div>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:</div><div>(P)     min cx</div><div>          s.t.  Ax <= b</div><div>                 x binary</div><div><br></div><div>Suppose that \bar{x} is feasible for (P), then I can cut off just \bar{x} by using the "no-good cut"</div><div>\sum_{i : \bar{x}_i = 0} x_i <a class="gmail_plusreply" id="m_-7730717292347431225plusReplyChip-0">+</a> \sum_{i : \bar{x}_i = 1} (1 - x_i) >= 1. </div><div><br></div><div>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:</div><div>1. Get a feasible solution \bar{x} to (P).</div><div>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.</div><div>3. Remove \bar{x} with a no-good cut.</div><div><br></div><div>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?</div><div><br></div><div>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.</div><div><br></div><div>Sorry for the long email, and any help is appreciated.</div><div><br></div><div>Best,</div><div>Matheus  </div></div>
</blockquote></div>