<div dir="ltr">Hi Leon,<div><br></div><div>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'). </div><div><br></div><div>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:</div><div>1. Is it possible to update the best feasible solution "manually" inside the callback? Or maybe just updating the primal bound value.</div><div>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.</div><div><br></div><div>Thanks again for your attention,</div><div>Matheus</div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">Em qui., 19 de out. de 2023 às 02:10, Leon Eifler <<a href="mailto:eifler@zib.de">eifler@zib.de</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"><u></u>

  
    
  
  <div>
    <p>Hi Matheus,</p>
    <p>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?<br>
    </p>
    <p>In any case, I wanted to mention that SCIP already contains a
      feature to count/enumerate all integer-feasible solutions:
      <a href="https://www.scipopt.org/doc/html/COUNTER.php#COLLECTALLFEASEBLES" target="_blank">https://www.scipopt.org/doc/html/COUNTER.php#COLLECTALLFEASEBLES</a></p>
    <p>I hope this helps,</p>
    <p>Leon<br>
    </p>
    <div>Am 10/18/2023 um 8:42 PM schrieb
      Matheus Ota:<br>
    </div>
    <blockquote type="cite">
      
      <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" target="_blank">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_6446074943444206797m_-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>
      <br>
      <fieldset></fieldset>
      <pre>_______________________________________________
Scip mailing list
<a href="mailto:Scip@zib.de" target="_blank">Scip@zib.de</a>
<a href="https://listserv.zib.de/mailman/listinfo/scip" target="_blank">https://listserv.zib.de/mailman/listinfo/scip</a>
</pre>
    </blockquote>
  </div>

_______________________________________________<br>
Scip mailing list<br>
<a href="mailto:Scip@zib.de" target="_blank">Scip@zib.de</a><br>
<a href="https://listserv.zib.de/mailman/listinfo/scip" rel="noreferrer" target="_blank">https://listserv.zib.de/mailman/listinfo/scip</a><br>
</blockquote></div>