Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Does OptaPlanner support optimizations and constraints on continuous variables?

I'm reading contradictory things in the documentation.

On one hand, this passage seems to indicate that continuous planning variables are possible:

A planning value range is the set of possible planning values for a planning variable. This set can be a discrete (for example row 1, 2, 3 or 4) or continuous (for example any double between 0.0 and 1.0).

On the other hand, when defining a Planning Variable, you must specify a ValueRangeProvider annotation on a field to use for the value set:

The Solution implementation has method which returns a Collection. Any value from that Collection is a possible planning value for this planning variable.

Both of these snippets are in the same section of the documentation (http://docs.jboss.org/drools/release/latest/optaplanner-docs/html_single/#d0e2518)

So, which is it? Can I use a full double as my planning variable, or do I need to restrict its range to the values in a specific Collection?

Looking at the actual algorithms are provided, I don't see any that are actually suitable for optimizing continuous variables, so I doubt it's possible, but it'd be nice to have that clarified and made explicit.

like image 961
levand Avatar asked Aug 20 '13 19:08

levand


1 Answers

We're working towards fully supporting continuous variables. But currently (in 6.0.0.CR2) it's not decently supported yet.

Value ranges can indeed be continuous ranges, but the plumbing to actually use them isn't there yet. We have made good progress recently, see https://issues.jboss.org/browse/PLANNER-160.

Here's how it will work: You 'll be able to use a @ValueRangeProvider annotation on a method that returns a ValueRange (instead of a Collection) too.

A ValueRange will be an interface supports selecting a random value, getting a size, ... Out-of-the-box we will support IntValueRange, DoubleValueRange, BigDecimalValueRange, ... (Implementation detail: we'll retro-fit those Collection-returning methods into a CollectionValueRange.)

Then the ValueSelector implementations will use that directly.

As for the suitability to optimize continuous variables:

  • JIT random selection will be blazing fast and be very memory-efficient.
  • If you have an NP-complete/NP-hard problem, then OptaPlanner will be a great match. If you have only continuous variables (and not a single discrete variable), then it's unlikely that your problem is NP-complete (unless your constraints counterprove that) and in that case you're better off with a custom, handmade, polynomial algorithm anyway (because it's not NP-complete, so there's an "easy" solution).
like image 66
Geoffrey De Smet Avatar answered Dec 08 '22 00:12

Geoffrey De Smet