bad initial objective values with Chuffed default search

[Helmut Simonis]

Hi,

I have been writing a few scheduling programs in MiniZinc where the objective is makespan minimization. A conservative upper bound of the makespan is the sum of all task durations. When solving this with Chuffed with "solve minimize makespan", it finds a first solution very close to this upper bound, then finds further solutions reducing the objective by one or another small amount. After a long while, and thousands of intermediate solutions, it gets close to a lower bound, and can prove optimality for smallish instances.

Alternatively, I'm using priority_search and find a very good (often the optimal) solution very quickly, but the system is no longer able to prove optimality. I can run the system twice from my testing environment, once with priority_search to find a good solution, and then with the default search to attempt to improve this, but can I do this in a single run of MiniZinc?

Also, why does Chuffed always seem to start at the worst possible objective value? Is the SAT strategy so fixated on finding a feasible solution?

In comparison, Cplex finds a few intermediate solutions, but converges to the optimal solution quite quickly. Of course, for larger instances it is no longer working so well.

[krzysztof....@gmail.com]

Hi,

To address your question, I use the following search for this kind of problems. This is not exactly what you ask for but it is a fix for this problem. It uses restart search and priority search. Below is an example that I use for a scheduling and assignment problem with JaCoP solver (JaCoP implements priority_search as well). More advanced methods can also be constructed.

solve :: restart_luby(10000)

          :: priority_search([0 | i in 1..3], [

                                    priority_search(t, [int_search([t[i], r[i]], input_order, indomain_min, complete)  | i in 1..n], smallest),

   priority_search(t, [int_search([t[i], r[i]], input_order, indomain_min, complete)  | i in 1..n], smallest_max),

   priority_search(t, [int_search([t[i], r[i]], input_order, indomain_min, complete)  | i in 1..n], occurrence)

   ],

   random)

      minimize end;

The code above basically restart search and selects randomly one of three priority searches. I know it is not deterministic.

I do not know if, for example, MiniSearch can do similar things.

/Kris

[Helmut Simonis]

Hi Krzysztof,

thanks for your reply. 

This answer in itself is quite useful to deal with multiple heuristics that can help to find a very good solution quickly. I do have several of these heuristics for my problem, which solve 80-90% of instances to optimality, but where none dominates the other. So running them in sequence gets a (small) improvement of solutions proven optimal by reaching a lower bound. For the remaining cases, I cannot rely on a random choice though. I have to run (one or multiple) heuristic approaches first to find a good upper bound with a limited amount of work, but then allow much more time (up to the given timeout limit) to try and improve the solution with a free search that uses the clause learning to reduce the size of the tree to explore.

I'll have to read the section on warmstarts in the manual, then. 

Helmut

[krzysztof....@gmail.com]

Hi Helmut,

Yes, warm start is an interesting concept used, as I understand, mostly in linear programming solvers. I considered to implement it for JaCoP/minizinc since we have specific indomain methods. One of them basically implements enumeration of values based on the default value for each variable first. If selection of this value will not succeed it tries to assign values with the default indomain method. The other possibility is to use our hierarchical indomain. 

Good luck with your problem.

/Kris

[Mikael Zayenz Lagerkvist]

Hi Helmut,

One thing that can be tried with Chuffed is to set the extra
configuration parameter "Alternate search between user-specified and
activity-based one" to true (which by default is false) to get a mix
between the built-in search and the problem specific searches that you
have specified.

Cheers,
Mikael

> --
> You received this message because you are subscribed to the Google Groups "MiniZinc" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to minizinc+u...@googlegroups.com.
> To view this discussion on the web visit https://groups.google.com/d/msgid/minizinc/e7028fa0-39f2-43ff-b652-d666843e88acn%40googlegroups.com.



--
Mikael Zayenz Lagerkvist