3
$\begingroup$

I am considering a Mixed Interger NonLinear Program (MINLP), and using a solver to obtain admissible solutions.

Is there a general method to reduce indeterminacy of solutions (e.g. by adding additionnal constraints to the problem or by solving multiple problems in an iteravite manner)?

By indeterminacy I mean the fact that multiple solutions could be returned by a solver, and therefore change from one computer to another.

I am opened to any reference on the matter, even for MILPs.

--

What I have been doing so far is to

  1. Solve the initial program
  2. Add a new constraint: objective function of previous program $\leq$ objective value of previous program
  3. Change the objective function to a new objective function with variables which are not in the initial objective function
  4. Solve this program and iterate to stage 2. It seem like a reasonnable procedure but I don't really know if it totally reduces indeterminacy and if some stages are unecessary (i.e. iterations for which the corresponding variables already have a unique solution).
$\endgroup$
6
  • $\begingroup$ Welcome to OR SE. To be clear, you are just trying to find one (or more?) feasible (not optimal) solution(s), and you are looking for a way to ensure that different solvers would find the same solution(s)? $\endgroup$
    – prubin
    Commented Dec 17, 2021 at 16:35
  • $\begingroup$ As far as I know, in general MINLP solvers are not guaranteed to find optimal solutions. If it simplifies the context, say I am considering a MILP and would for any solver on any machin to always return the same (optimal) solution. $\endgroup$
    – Meth
    Commented Dec 17, 2021 at 16:55
  • $\begingroup$ For a MILP, the only guarantee of getting the same solution from two different solvers, or even the same solution twice from the same solver (for at least some solvers), is for the problem to have a unique solution. It is known that, for instance, running the same model in the same solver but changing the order in which the constraints are entered will occasionally lead to a different solution. $\endgroup$
    – prubin
    Commented Dec 17, 2021 at 20:24
  • $\begingroup$ Thanks @prubin for you comment! Is there a way to guarantee uniqueness of solution? Any reference? Thanks again $\endgroup$
    – Meth
    Commented Dec 20, 2021 at 15:18
  • $\begingroup$ For a MILP solved by some version of branch-and-bound/branch-and-cut, if the best bound of every remaining node is strictly worse than the value of the optimum when it is found, the optimum is on its way to being unique. What I mean there is that you can rule out a second optimum with any differences in the integer variables. It remains to be checked whether the solution to the LP resulting from fixing the integer variables is also unique. (You could have two solutions with the same values for integer variables but different values of continuous variables.) $\endgroup$
    – prubin
    Commented Dec 20, 2021 at 16:08

0

Your Answer

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