ankane / or-tools-ruby

Operations research tools for Ruby
Apache License 2.0
171 stars 20 forks source link

Add way to get upper and lower bounds of `SatIntVar` #45

Closed johnnymo87 closed 1 year ago

johnnymo87 commented 1 year ago

TL;DR

Hi @ankane, I'm looking for a way to get the upper bound of a SatIntVar, and so I've put together a solution for your review 🙏 I've taken the most "true to or-tools" approach to modeling things, but I could see the argument for alternative ways of modeling things.

The problem I'm trying to solve

The business problem I'm looking to solve seeks to minimize several different variables at once. There's a strict hierarchy to these variables -- each one is infinitely more important than the next. So sort of like how one might sort a spreadsheet by column A, then column B, etc, the minutest difference in variable A "overpowers" the most massive differences in variable B.

If I had three variables (c, b, a, listed in increasing order of importance) that all had a range of 0-99, I could've implemented my cost function like so:

model.minimize(
  model.sum([
    c,
    b * (10 ** 2),
    a * (10 ** 4)
  ])
)

But in the business problem I'm trying to solve, my variables actually have dynamic ranges, so I'm looking to implement my cost function like so:

model.minimize(
  model.sum([
    c,
    b * (10 ** c.upper_bound.digits.count),
    a * (10 ** (c.upper_bound.digits.count + b.upper_bound.digits.count))
  ])
)

In this example, upper_bound is a method that doesn't exist.

A solution

I looked through the or-tools C++ source code, and I noticed that the sat IntVar has a Domain member which returns a Domain type, and this Domain type has Min and Max members which are the lower and upper bounds that the sat IntVar is initialized with. (Or at least that's my understanding of the code, I've only recently began to learn C++.)

In this PR, I've implemented things exactly like they are in or-tools -- I've added a #domain method to the SatIntVar class, which returns a new Domain class, which exposes #min and #max methods.

Alternative solutions

However, I could see the argument for an alternative approach where we skip the intermediate Domain class, and we expose some methods directly on the SatIntVar class, such as #lower_bound and #upper_bound.

Also, I could see the argument that this PR is entirely unnecessary, and that I could just separately keep track of the upper bound for each variable I'm using (e.g. in addition to variable a, and I define an a_upper_bound variable.)

ankane commented 1 year ago

Hey @johnnymo87, thanks for the PR! Makes sense to me. From what I can tell, Python doesn't have a similar method, but think it's fine to include/make an exception since C++ has it.