2
$\begingroup$

How can I algorithmically detect whether an (MI)NLP problem is unbounded or not?

Finding a source for this has proven tricky, because people in the literature seem to talk a lot about what to do if a problem is unbounded, but rarely about how to algorithmically detect that it is.

I have considered checking whether the dual of the linear relaxation is proven to be infeasible, but linear solvers do not seem to report this very reliably, so that won't work for me.

I have also considered the trivial case where:

  • I have an unbounded variable in the objective which does not appear anywhere else, and
  • the case where a higher-order convex term containing that var in the objective is cancelling out the unboundedness.

What I'm not sure about is how to handle unbounded variables which are also present in constraints. Are you aware of a source with a set of rules (e.g., when foo and bar happen then the problem is unbounded) or something similar?

Improve this question
$\endgroup$
8
  • $\begingroup$ What kind of (MI)NLP are you interested in? In general this as difficult as solving the problem, so do you want some easy to check heuristics to filter out cases which are fast to detect? $\endgroup$
    – user3680510
    Apr 30, 2020 at 12:40
  • $\begingroup$ I am solving general MINLPs, but MIQCQPs would be a good place to start if there are specialised algorithms for those. Yes, I am primarily interested in quick-and-dirty rule-based checks to weed out cases without having false positives (i.e. detect unboundedness where it doesn't exist). I have a symbolic engine so I can do any symbolic manipulation/comparison very easily. $\endgroup$
    – Nikos Kazazakis
    Apr 30, 2020 at 13:38
  • $\begingroup$ Am i understanding you correctly: the lp-solver has numerical troubles solving the lp-relaxation of your problem correctly? $\endgroup$
    – user3680510
    Apr 30, 2020 at 15:00
  • 1
    $\begingroup$ It is hard because you do not have something like Farkas lemma and duality for MIPs. Assume the LP relaxation is unbounded, then the MIP can still be infeasible. So I doubt checking the dual of the LP relaxation provide the info you need. $\endgroup$
    – ErlingMOSEK
    Apr 30, 2020 at 17:33
  • 1
    $\begingroup$ Btw if you are solving convex mixed integer QCQPs, then formulating them as a mixed-integer SOCPs might be a good idea. Since the homogeneous primal-dual IPM used for that sort problems are quite good at detecting infeasibilities of the continuous relaxation. $\endgroup$
    – ErlingMOSEK
    Apr 30, 2020 at 17:38

1 Answer 1

Reset to default
2
$\begingroup$

Here some quick thoughts for linear programs.

Lets assume $v_1,\ldots,v_n$ are unbounded variables in your problem and we are maximizing.

  1. Then look if there are only constraints (where $v_i$ is separable) of the form $... \leq v_i$ If $v_i$ has only a positive linear coefficient.
  2. Dominating columns with the right objective coefficients

Of course for all these methods you need at least one feasible point to come to an conclusion.

I think you can extend both methods also for MINLPs.

  1. works for any constraint and if you know that the objective is monotone increasing in $v_i$.
  2. maybe you can detect also dominating non-linear terms

I would look at examples from a MINLP library, solve unbounded instances and look at the terms the unbounded variables appears in, maybe you see additional cases there.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.