Portfolio search ?

[Marcus Vilain]

Hello, 

I need an advice. I solve a problem in B&B where I have very few failures and where the solutions are very often substantially equivalent. This is related to the merits functions used to choose the variables to branch. How to bring more variability? I was considering using a portfolio with different heuristics. If so, i was even planning to interrupt  each space by causing a fail after few solutions has been found. What do you think ?

Thanks

Marcus

[Mikael Zayenz Lagerkvist]

There are several ways that you can generate diverse sets of solutions. For example

* Restart based search with some kind of randomized search

* Portfolio search as you mention with different heuristics
* A combination of portfolio search and restarts

Depending on what you are after, you might want to look at systematically generating diverse solutions. See for example https://ojs.aaai.org/index.php/AAAI/article/download/5512/5368 for some ideas in this regards.

Cheers,

Mikael

[marcus...@gmail.com]

Hello Mikael,

Thank you for your answer. I think i will go for a Portfolio search. 

The fact that I have very few failures is related to my costs functions (I have 2 objectives to optimize and for one of them, i require to be at least equal (!) or better than previous solution)
This explains the lack of diversity (and also shows that my cost function is not well designed)

Cheers,

Philippe

[Mikael Zayenz Lagerkvist]

Hi,

If I understand you correctly, you have a lexicographic optimization
problem. That is, you want to minimize [x1, x2, ...., xn] with
lexicographic comparisons so that x1 is most important, and given
equal x1 then x2 should be compared.

It is usually a much better idea to split this into multiple phases.
First optimizing x1 (with a strict comparison) and when the best value
for x1 is found, fix that and optimize x2. Repeat for the number of
different criteria.

Cheers,
Mikael

> --
> You received this message because you are subscribed to a topic in the Google Groups "Gecode" group.
> To unsubscribe from this topic, visit https://groups.google.com/d/topic/gecode/MAYcSph_L8g/unsubscribe.
> To unsubscribe from this group and all its topics, send an email to gecode+un...@googlegroups.com.
> To view this discussion on the web visit https://groups.google.com/d/msgid/gecode/28842c1a-412e-4077-acaf-bfdeb9f313f1n%40googlegroups.com.



--
Mikael Zayenz Lagerkvist

[Marcus Vilain]

Hello,

Sorry for the late response. Holidays are sacred! 

I am not trying to do lexicographic optimization. x1 and x2 have the same importance. I'm looking for the Pareto front instead.

 I overloaded the constrain() method of the bab and put something like: 

rel(*this, (x1 > sp.x1) || (x2 < sp.x2)); 

In fact, more exactly 

rel(*this, (x1 >= sp.x1) || (x2 < sp.x2)); 

Which causes probably similar solutions and highlights the fact that the cost on x1 is poorly modeled. 

x1 and x2 are highly correlated (e.g. x1 “efficiency” and x2 “price”)

Does it exists a better method ?

Cheers,

Marcus

You received this message because you are subscribed to the Google Groups "Gecode" group.
To unsubscribe from this group and stop receiving emails from it, send an email to gecode+un...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/gecode/CAPKxCj7zVKdk0zZALY3p3yhDajsCjDqEAz6KOq_EtXEN7ObPkg%40mail.gmail.com.

[Mikael Zayenz Lagerkvist]

Hi Marcus,

Ahh, interesting case with Pareto optimization. I'm not sure of what
is published in the area, maybe someone else on this list knows
something more?

My initial idea for how to structure a pareto search would probably be
to make a portfolio search where each asset tries to optimize one of
the variables strictly using a standard BAB search engine (that may
also be run in parallel mode). The controller could then be used to
update the minimum pareto frontier across the assets.

This could naturally be combined with several of the ideas previously
mentioned in the thread for different types of solutions (portfolio of
multiple heuristics, restarts, randomization, LNS, ...) for each of
the assets corresponding to one of the variables you are optimizing
over.

Cheers,
Mikael

> To view this discussion on the web visit https://groups.google.com/d/msgid/gecode/CAAG24FgPZWtcw6gVfsP0Yp94QsPui8KKRHZngt5cBfohW5yQRA%40mail.gmail.com.



--
Mikael Zayenz Lagerkvist

[Marcus Vilain]

Hi,

I had this discussion with Christian (search the keyword Pareto in this Google’s group). He kindly gave me the following paper https://link.springer.com/chapter/10.1007%2F978-3-319-18008-3_9 but it was definitely too complex for me. Your idea of the controller is interesting but for now my main concern is about lack of diversity. I definitely need to prototype some ideas…

Cheers,

Marcus

To view this discussion on the web visit https://groups.google.com/d/msgid/gecode/CAPKxCj6kBRgh_n-RG%2BAmZDC%3DMWOHj%3DJNdVcKx3bDvocvv47%3DsA%40mail.gmail.com.