KNITRO lower bound exceeds the best objective value

[Stuart Rogers]

KNITRO finds a lower bound ( 0.682744  ) for a minimization problem (defined in the attached nonconvex MIQCP) that exceeds the best objective value ( 0.680702  ). Below is the Knitro log when solving the nonconvex MIQCP.

https://neos-server.org/neos/jobs/14340000/14349099.html

[Florian Fontan]

Hi Stuart,

For non-convex MINLPs, the bound displayed by Knitro is not valid. It gives an indication, but it might happen that a better integer feasible solution exists.

In Knitro 14.1, which will be released in the next days, Knitro displays the bound only once it becomes confident enough that it is valid. On your problem, Knitro 14.1 with MIP multi-start will display:

 

Tree search

-----------

 

       Nodes        Best solution   Best bound      Gap       Time

   Expl  |  Unexpl      value         value                  (secs)

   ---------------  -------------   ----------      ---      ------

      1       2      5.48424              -inf                3.699

 

Knitro deduced that the problem is non-convex.

 

      2       3      1.05830 FCRD         -inf                4.142

     12       5      1.05158 FCRD         -inf                5.105

     17       6      1.03222 FCRD         -inf                5.173

     50      13     0.813742 FCRD         -inf                5.583

    111      27     0.813742 FCRD         -inf                6.169

   1240      61     0.680949 FCRD         -inf               15.647

 

Best,

Florian

[Stuart Rogers]

Thanks for the clarification. Knitro v14.0.0 prints the message below about the feasibility of the initial point provided in the .nl file. Why does Knitro then say that no primal point is provided for the MIP? Is that because Knitro has already found a better primal point than the initial point provided in the .nl file? Also, there is a typo in that Knitro message: " obective value " should instead be " objective value ".

The initial point provided for the root node relaxation is feasible for the MIP and has obective value 5.484236e+00. No primal point provided for the MIP.

[Richard Waltz]

In the C API of Knitro, it is possible to provide one point used as starting point of the root node relaxation – which might not be integer feasible – and another integer feasible point which might be useful for other components of the NLPBB algorithm (bounding, heuristics…).

 

https://www.artelys.com/app/docs/knitro/3_referenceManual/callableLibraryAPI.html#KN_set_var_primal_init_values

https://www.artelys.com/app/docs/knitro/3_referenceManual/callableLibraryAPI.html#KN_set_mip_var_primal_init_values

 

If a starting point is provided for the root node relaxation, Knitro still checks if it is integer feasible. But if it is not feasible, then Knitro doesn’t try to repair it.

 

If an integer feasible point is provided, but it is actually not feasible, Knitro tries to repair it.

 

Through the AMPL interface, it is only possible to provide the initial point for the root node relaxation.

 

The typo has been fixed in Knitro 14.1

 

Best,

---

From: kni...@googlegroups.com <kni...@googlegroups.com> on behalf of Stuart Rogers <stum...@gmail.com>
Sent: Wednesday, July 3, 2024 4:10 PM
To: Artelys Knitro forum <kni...@googlegroups.com>
Subject: [Knitro] Re: KNITRO lower bound exceeds the best objective value

 

--
You received this message because you are subscribed to the Artelys "Knitro Nonlinear Optimization Solver" google group.
To post to this group, send email to kni...@googlegroups.com
To unsubscribe from this group, send email to knitro-un...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/knitro?hl=en
Thank You,
Artelys
http://www.artelys.com/en/optimization-tools/knitro
---
You received this message because you are subscribed to the Google Groups "Artelys Knitro forum" group.
To unsubscribe from this group and stop receiving emails from it, send an email to knitro+un...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/knitro/6a766519-73e9-4948-83db-f5d01d2a404bn%40googlegroups.com.