CODEWITHSUNDEEP
optaplannerconstraint-programming
TheDarkSaint
TheDarkSaint

Reputation: 457

Constraining optaplanner's choices based on the result of different choices - Constraint Propagation / Local Consistency

I have an optimization problem that I'm working on in which the optimizer's decision for one variable needs to constrain the available choices for another variable, and I'm wondering about the suitability of different ways of accomplishing this. I'll try to pare it down for demonstration purposes (in kotlin).

@PlanningEntity
class AuctionBid {
  @PlanningId
  lateinit var entity: String
  
  @PlanningVariable(valueRangeProviderRefs = ["availOptions"])
  var bidNow: Boolean? = null
  @PlanningVariable(valueRangeProviderRefs = ["availOptions"])
  var bidFinal: Boolean? = null
  var forceBid: Boolean? = null

  @ValueRangeProvider(id = "availOptions")
  private fun availOptions(): List<Boolean> {
    return if(this.forceBid != null) {
      listOf(this.forceBid!!)
    } else {
      listOf(true,false)
    }
  }
}

In this scenario, we are trying to determine if we should bid on a given entity in a combinatorial auction (multiple entities being bid on in each round), given a hard budget and various cost/benefit tradeoffs. The bidNow choice is determined by the prices in the current round of the auction, and the bidFinal choice is determined by the anticipated/forecasted final prices in the auction. In order to avoid constantly changing decisions about what to bid on right now (switching bids is penalized in the auction rules), we want to constrain our choices on bidNow based on our decision for bidFinal, such that if we will want to bid on it at our anticipated future price, we will always choose to bid on it now. A state table seen below:

bidNow bidFinal possible
Y Y Y
Y N Y
N N Y
N Y N

As seen, we already have a method of constraining choices for situations where we know we don't want the product at all, or where we know we want it at any price. This is using the availOptions ValueRangeProvider, which only lets the optimizer choose a predetermined option if we know that is our only choice.

However, this constraint is more dynamic, as it results from a separate choice. If we are wanting to bid at the anticipated final price, our only choice for right now is to continue bidding in the current round.

I've thought of a few ways of doing this, as this is a classic Local Consistency Constraint Propagation example, but without knowing too much about optaplanner's internals, I don't really know the best way to do this. Some options:

  1. Use a separate ValueRangeProvider for bidNow than bidFinal, and constrain the value range for bidNow to True if bidFinal is true. However, I don't know if optaplanner can even handle a dynamic value range that is determined by another planning variable's value, nor do I know if this is an efficient method.
  2. Place a hard constraint (using ConstraintStreams, which is super cool BTW) on bidNow to always be True if bidFinal is True. I know this is feasible (it's my current solution), but it seems really slow.
  3. Maybe try to use a Shadow variable which I've never used before, although I'm not sure this is a good fit because bidFinal==True implies bidNow==True, but bidFinal=False doesn't necessarily imply anything about bidNow.

I know I can always just try all the different options and see, but this problem is already big and unwieldy (the demo code is dramatically simplified), and I really would like some insight into how Optaplanner is working behind the scenes because I really like working with it but come across these this-way-or-that-way scenarios all the time and it's difficult to try them all. Is there any insight into modeling this constraint propagation problem? Or problems like this?

Upvotes: 0

Views: 105

Answers (1)

Luk&#225;š Petrovick&#253;
Luk&#225;š Petrovick&#253;

Reputation: 5702

Both 1 and 2 should be possible; 2 being the straightforward way.

Another option would be to use filtered move selection to skip the moves that would set bidFinal to Y if bidNow is false (and the opposite corner case). The downside of this is that the filter needs to be applied to every move you use, which makes solver configuration verbose. And the moves will still be generated before they are thrown away, so you lose a bit of performance.

However, why not make bid an enum with three options: NOTHING, NOW_ONLY, BOTH. That way, you have the benefits of only having one planning variable and completely eliminating the original problem. Of course this is only suitable when the number of options is this low, which it may not be in your actual use case.

This last option is an example of designing your data model in a way to avoid corner cases. If they are impossible because the model precludes them, you do not need to worry about working around them later. This is always your best bet.

Upvotes: 1

Related Questions