Complete vs Incomplete Hints and Performance

[Dr-Irv]

We are doing multi-objective hierarchical optimization. After each objective is complete, we add new variables and constraints. We can run it in one of two ways:

1. Give complete hints for all variables, since there is an obvious feasible solution by using the previous solution, and setting the new variables to be the obvious solution.
2. Give hints ONLY for the variables that were in the previous problem, and leave the new variables alone.

When we do (1), we do get the message "The solution hint is complete and is feasible.", so we know the hints are correct, and solutions are generated where we see the "hint" message.
When we do (2), we don't get that message (that is expected) and we see less solutions generated where we see the "hint" message.

It's difficult to tell whether providing complete hints or incomplete hints is better from a quality of solution perspective, because we use a dynamic time limit for each objective.

I print out the elapsed time where "Starting search" appears and when new solutions appear. With (1), when we know the hints are feasible, it takes 3.64 seconds to get the first feasible solution. But if the solution hint is complete and feasible, why doesn't the first solution get returned earlier? With (2), the difference in time is 3.22 seconds (not a real difference), so it seems that by providing complete hints, you get no improvement in terms of time to the first solution is generated.

Then the question is how the hints are used after the first solution is found. When we call CpSolver.SolutionInfo(), the word "hint" sometimes appears in both (1) and (2). And since the objective is improved, it seems that indicates that the hints are used in later solutions - not just the first one.

But we know that in the case of (1), the hints for the new variables are not good with respect to the objective - they are just helping get a new feasible solution. The hints for the "old" variables are useful - they helped generate the "best" solution from a previous objective.

So is there a concept of "use the hints to get feasible, but don't use them afterwards?"

So to summarize the questions:

1. When providing a complete hint that is feasible, why does it take a few seconds to return that as a feasible solution (after presolve)?
2. Are the hints used throughout the solution process, even though some of them may be "bad" ?
3. If hints are incomplete, are they still useful?

[lperron]

The [hint] attribute is displayed each time the solver uses a hint.
It can be with general workers following the user supplied hint, or with LNS workers following the base solution the fragment is built upon.

When a hint is supplied, the solver tries to follow it for a limited number of conflicts.
This sets the the activities of variables (equivalent of strong branching I believe), then the normal search takes over, and gradually decays the supplied info.

Finally, the solution is reported after a full search, which takes time. We have a TODO to report it instantaneously. But this is not yet implemented.

[sschnug]

Related question:
Is the basis-finding of some simplex-based relaxation a necessity and potential bottleneck for hint-acceptance?
(Asking because SCIPs "heur_completesol" can also cost a minute or such for large-scale problems even if 100% of all variables are set -> aka no search/branching needed)

[Dr-Irv]

When a hint is supplied, the solver tries to follow it for a limited number of conflicts.
This sets the the activities of variables (equivalent of strong branching I believe), then the normal search takes over, and gradually decays the supplied info.

So is the way to think of a hint is "I think these variables have these values in the solution, so keep trying to use them, until they seem to not be helping", as opposed to "Here is a feasible solution - use it to start the search and see if you can do better, and ignore the values afterwards"

[lperron]

No, hints are applied to all 'complete' workers, and some of them do not use a simplex (no_lp). Laurent Perron | Operations Research | ***@***.*** | (33) 1 42 68 53 00 Le mer. 11 oct. 2023 à 14:08, sschnug ***@***.***> a écrit :

…

Related question: Is the basis-finding of some simplex-based relaxation a necessity and potential bottleneck for hint-acceptance? (Asking because SCIPs "completesol" can also cost a minute or such for large-scale problems even if 100% of all variables are set -> aka no search/branching needed) — Reply to this email directly, view it on GitHub <#3945 (reply in thread)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ACUPL3PSW75IW5XJ3YJ4SNTX62D33ANCNFSM6AAAAAA53IMHVM> . You are receiving this because you commented.Message ID: ***@***.***>