I have a problem described in minizinc that takes 32 minutes to completely be solved with JaCoP. When I limit the solving time to two minutes (-t 60). The result given by JaCoP is exactly the same as after half an hour. Why does the program continues running if the optimal solution is already found?
May it be the case that JaCoP gives out only solutions that are better than previously found ones? If so can I somehow make the Fz2jacop to give out all the results even if they are equal to already found ones. The option all solutions (-a) does not help here and the number of results given out is the same.
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
JaCoP, as other CP solvers, uses branch-and-bound for optimization. It means that when a solution is found, the solver puts additional constraint on the cost (lower than the currect one for minimization) and conitinues search. The goal is to find a better solution. Finally, when there is no better solution, the solver fails to find any and, when finishes search, delivers prove of optimality. In some cases, this process is very time consuming. It is basically exponential complexity in worst case :(
This explains your problem that is build-in problem not JaCoP problem. One can "help" the solver if a good lower bound is known. In such case, it it possible to define it for cost variable and the solver will stop the search when lower bound will be reached.
Best regards,
/Kris
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
Thanks Kris.
Is there any way to make the solver to use 'lower or equal' constraint with minimization or 'higher or equal' constraint with maximization when using Fz2jacop? (to get also solutions that are equal to the best one)
If there is no lower bound (for minimization or upper bound for maximization) to be known then it is no other way to "help" the solver?
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
Of course, you can add 'lower or equal' or 'higher or equal' constraints but this will not make the situation easier for the solver. The search space will be larger since the solver will try to find all solutions with the current cost or lower cost instead of only solutions with lower cost. This will not "help" the solver.
Best,
/Kris
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
I have a problem described in minizinc that takes 32 minutes to completely be solved with JaCoP. When I limit the solving time to two minutes (-t 60). The result given by JaCoP is exactly the same as after half an hour. Why does the program continues running if the optimal solution is already found?
May it be the case that JaCoP gives out only solutions that are better than previously found ones? If so can I somehow make the Fz2jacop to give out all the results even if they are equal to already found ones. The option all solutions (-a) does not help here and the number of results given out is the same.
JaCoP, as other CP solvers, uses branch-and-bound for optimization. It means that when a solution is found, the solver puts additional constraint on the cost (lower than the currect one for minimization) and conitinues search. The goal is to find a better solution. Finally, when there is no better solution, the solver fails to find any and, when finishes search, delivers prove of optimality. In some cases, this process is very time consuming. It is basically exponential complexity in worst case :(
This explains your problem that is build-in problem not JaCoP problem. One can "help" the solver if a good lower bound is known. In such case, it it possible to define it for cost variable and the solver will stop the search when lower bound will be reached.
Best regards,
/Kris
Thanks Kris.
Is there any way to make the solver to use 'lower or equal' constraint with minimization or 'higher or equal' constraint with maximization when using Fz2jacop? (to get also solutions that are equal to the best one)
If there is no lower bound (for minimization or upper bound for maximization) to be known then it is no other way to "help" the solver?
Of course, you can add 'lower or equal' or 'higher or equal' constraints but this will not make the situation easier for the solver. The search space will be larger since the solver will try to find all solutions with the current cost or lower cost instead of only solutions with lower cost. This will not "help" the solver.
Best,
/Kris