AddReservoirConstraintWithActive resulting in solver conflicts when it previously didn't

[timothylowjc]

What version of OR-tools and what language are you using? Version: master, 7.5.7515 Language: Python

Which solver are you using (e.g. CP-SAT, Routing Solver, GLOP, BOP, Gurobi) CP-SAT

What operating system (Linux, Windows, ...) and version? Windows Subsystem Linux, Ubuntu 18.04

What did you do? Model was working perfectly, until I attempted to port my model into master last week. This required me to run all the specific apt-get commands as stipulated in https://developers.google.com/optimization/install/python/source_linux

After which I attempted to run the solver again, and suddenly it begins to produce conflicts, or solverstatus = 3.

From investigation, it seems to be caused by the AddReservoirConstraintWithActive constraints. This "infeasible" only occurs when I attempt to set a relevant "Active" in these constraints, such as x[1,1], to a constant value using a constraint, such as model.Add(x[1,1] == 1), with a corresponding IntVar, such as starts[1,1], that is used in a relevant IntervalVar as well.

I've also tested this by setting a AddReservoirConstraintWithActive constraint with my "actives" just being a list of zeroes. Produces the "infeasible" as well. NumConflicts is also = 0.

I believe the bug is most likely something to do with setting up a reservoir constraint, by pairing a constant active to a variable IntVar. Apologies if I'm wrong.

What did you expect to see Prior to this week the model would at least solve. The reservoir constraint was definitely functional, and I could force booleans to be true or false using model.Add(x[1,1] == 1) or 0, without causing any "infeasible".

Proto as below. Apologies if I did something wrong, or if I'm posting in the wrong area.

modelproto.txt

piplist if useful:

attrs               17.4.0
Automat             0.6.0
blinker             1.4
certifi             2019.9.11
chardet             3.0.4
click               6.7
cloud-init          19.4
colorama            0.3.7
command-not-found   0.3
configobj           5.0.6
constantly          15.1.0
cryptography        2.1.4
cycler              0.10.0
Cython              0.29.14
DateTime            4.3
distro-info         0.18ubuntu0.18.04.1
httplib2            0.9.2
hyperlink           17.3.1
idna                2.8
importlib-metadata  1.5.0
incremental         16.10.1
Jinja2              2.10
joblib              0.14.1
jsonpatch           1.16
jsonpointer         1.10
jsonschema          2.6.0
keyring             10.6.0
keyrings.alt        3.0
kiwisolver          1.1.0
language-selector   0.1
MarkupSafe          1.0
matplotlib          3.1.3
more-itertools      8.2.0
mysqlclient         1.4.6
netifaces           0.10.4
numpy               1.18.1
oauthlib            2.0.6
olefile             0.45.1
ortools             7.5.7515
packaging           20.1
PAM                 0.4.2
pandas              1.0.1
patsy               0.5.1
Pillow              5.1.0
pip                 19.3.1
pipenv              2018.11.26
pluggy              0.13.1
protobuf            3.11.3
PuLP                2.0
py                  1.8.1
pyasn1              0.4.2
pyasn1-modules      0.2.1
pycrypto            2.6.1
pygobject           3.26.1
PyJWT               1.5.3
pyOpenSSL           17.5.0
pyparsing           2.4.6
pyserial            3.4
pytest              5.3.5
python-apt          1.6.5+ubuntu0.2
python-dateutil     2.8.1
python-debian       0.1.32
pytz                2019.3
pyxdg               0.25
PyYAML              3.12
requests            2.22.0
requests-unixsocket 0.1.5
scikit-learn        0.22.1
scipy               1.4.1
SecretStorage       2.3.1
service-identity    16.0.0
setuptools          41.6.0
six                 1.11.0
sklearn             0.0
ssh-import-id       5.7
statsmodels         0.11.0
systemd-python      234
Twisted             17.9.0
ufw                 0.36
unattended-upgrades 0.1
urllib3             1.25.3
virtualenv          16.7.7
virtualenv-clone    0.5.3
wcwidth             0.1.8
wheel               0.30.0
xlrd                1.2.0
zipp                2.2.0
zope.interface      4.3.2

[timothylowjc]

A follow up from a friend:

The following code block also produces infeasible:

from ortools.sat.python import cp_model

model = cp_model.CpModel()

start_bool = model.NewBoolVar("x0")
fill_2_bool = model.NewBoolVar("x2")
fill_8_bool = model.NewBoolVar("x8")
empty_12_bool = model.NewBoolVar("x12")

start = model.NewIntVar(0, 0, "start")
fill_time_2 = model.NewIntVar(2, 2, "fill_time_2")
fill_time_8 = model.NewIntVar(8, 8, "fill_time_8",)
empty_time_12 = model.NewIntVar(12, 12, "empty_time_12")

times = [start, fill_time_2, fill_time_8, empty_time_12]
demands = [10, 1, 1, -3]
actives = [start_bool, fill_2_bool, fill_8_bool, empty_12_bool]

model.AddReservoirConstraintWithActive(times, demands, actives, 0, 20)
model.Add(start_bool == 1)
model.Add(fill_2_bool == 0)
model.Add(fill_8_bool == 1)
# model.Add(empty_12_bool == 0)

solver = cp_model.CpSolver()
solver.Solve(model)
print(solver.ResponseStats())
print(solver.Value(start_bool), solver.Value(fill_2_bool), solver.Value(fill_8_bool), solver.Value(empty_12_bool))

On ortools 7.5.7466

[EverGreen1253]

Thanks Mizux! You're the best!

https://youtu.be/GC5E8ie2pdM

[Mizux]

C++ version:

#include "ortools/sat/cp_model.h"
#include <stdexcept>
#include <vector>
#include <list>
#include <functional>

namespace operations_research {
  namespace sat {

    ReservoirConstraint AddReservoirConstraintWithActive(
        CpModelBuilder& model,
        const std::vector<std::reference_wrapper<const IntVar>>& times,
        const std::vector<int>& demands,
        const std::vector<std::reference_wrapper<const BoolVar>>& actives,
        int64 min_level,
        int64 max_level) {
      if (max_level < min_level) {
        throw std::invalid_argument("Reservoir constraint must have a max_level >= min_level");
      }

      ReservoirConstraint rc = model.AddReservoirConstraint(min_level, max_level);
      ConstraintProto* ct_proto = rc.MutableProto();
      ReservoirConstraintProto* reservoir = ct_proto->mutable_reservoir();

      for(const auto& it : times) {
        reservoir->add_times(it.get().index());
      }
      for(auto it : demands) {
        reservoir->add_demands(it);
      }
      for(const auto& it : actives) {
        reservoir->add_actives(it.get().index());
      }
      reservoir->set_min_level(min_level);
      reservoir->set_max_level(max_level);
      return rc;
    }

    void SimpleSatProgram() {
      CpModelBuilder model;

      const BoolVar start_bool = model.NewBoolVar().WithName("x0");
      const BoolVar fill_2_bool = model.NewBoolVar().WithName("x2");
      const BoolVar fill_8_bool = model.NewBoolVar().WithName("x8");
      const BoolVar empty_12_bool = model.NewBoolVar().WithName("x12");

      //const Domain domain(0, 2);
      const IntVar start = model.NewIntVar({0, 0}).WithName("start");
      const IntVar fill_time_2 = model.NewIntVar({2, 2}).WithName("fill_time_2");
      const IntVar fill_time_8 = model.NewIntVar({8, 8}).WithName("fill_time_8");
      const IntVar empty_time_12 = model.NewIntVar({12, 12}).WithName("empty_time_8");

      std::vector<std::reference_wrapper<const IntVar>> times { start, fill_time_2, fill_time_8, empty_time_12 };
      std::vector<int> demands {10, 1, 1, -3};
      std::vector<std::reference_wrapper<const BoolVar>> actives { start_bool, fill_2_bool, fill_8_bool, empty_12_bool };

      AddReservoirConstraintWithActive(model, times, demands, actives, 0, 20);
      model.AddEquality(start_bool, true);
      model.AddEquality(fill_2_bool, false);
      model.AddEquality(fill_8_bool, true);
      //model.AddEquality(empty_12_bool, false);

      // Solving part.
      const CpSolverResponse response = Solve(model.Build());
      LOG(INFO) << CpSolverResponseStats(response);

      if (response.status() == CpSolverStatus::FEASIBLE) {
        // Get the value of x in the solution.
        LOG(INFO) << "start_bool = " << SolutionIntegerValue(response, start_bool);
        LOG(INFO) << "fill_2_bool = " << SolutionIntegerValue(response, fill_2_bool);
        LOG(INFO) << "fill_8_bool = " << SolutionIntegerValue(response, fill_8_bool);
        LOG(INFO) << "empty_12_bool = " << SolutionIntegerValue(response, empty_12_bool);
      }
    }

  }  // namespace sat
}  // namespace operations_research

int main() {
  operations_research::sat::SimpleSatProgram();

  return EXIT_SUCCESS;
}

[lperron]

I just pushed the fix. Thanks again for the report.