Incremental solve options

[leonlan]

Incremental solve using callbacks during a solve. This is what incremental solve usually means in MIP solvers: adding cuts, lazy constraint generation, etc. This is not possible in CP-SAT. But there are other ways to do "incremental" solving, although in a bit higher-level fashion, which is mostly about performance (not rebuilding) and convenience (sensible interface).

Minimum

• [x] Passing solutions to warm start without rebuilding the model
  • [x] OR-Tools: clear hints
  • [x] CP Optimizer: doesn't matter I think
• [ ] Lexicographic/sequential objective: adding objective constraints and solving the next objective

Nice to haves

• [ ] ~Add constraints~
• [ ] ~Deleting constraints~
  • ~Clear the corresponding protobuf line https://stackoverflow.com/questions/68207910/how-to-modify-variables-and-constraints-of-an-existing-google-or-tools-constrain~

[leonlan]

from pyjobshop.cli import instance2data
from pyjobshop.ortools import Solver
import fjsplib

loc = "instances/FJSP/Naderi/1.fjs"
instance = fjsplib.read(loc)
data = instance2data(instance)

TIME_LIMIT = 20
NUM_TRIES = 10

solver = Solver(data)
result = solver.solve(time_limit=TIME_LIMIT, log=True)
init = result.best

for _ in range(NUM_TRIES - 1):
    result = solver.solve(
        initial_solution=init, time_limit=TIME_LIMIT, log=True
    )
    init = result.best

This simple loop already works now for warmstarting repeatedly!

[leonlan]

Sequential solve is not implemented yet. One of the decisions that is blocking this is how the user interface should look like. How does a user pass multiple objective functions to a Model? ProblemData is currently storing the objective function, which is an OK place, but it gets a bit weird when we have more objective functions. Do we allow ProblemData.objectives to store a list of objectives? What is the default behavior when calling solve? Etc.

Implementing sequential solve is relatively straightforward (with some open TODOs):

def sequential_solve(
    self,
    objectives: list[Objective],
    time_limit: float = float("inf"),
    log: bool = False,
    num_workers: Optional[int] = None,
    initial_solution: Optional[Solution] = None,
    **kwargs,
):
    result = self.solve(
        objectives[0],
        time_limit,  # TODO is time limit per solve?
        log,
        num_workers,
        initial_solution,
        **kwargs,
    )

    for idx, objective in enumerate(objectives[1:], 1):
        # TODO what if no solution was found?
        init = result.best
        prev_obj = objectives[idx - 1]
        self.add_objective_constraint(prev_obj, int(result.objective))
        result = self.solve(
            objective,
            time_limit,
            log,
            num_workers,
            init,
            **kwargs,
        )

    return result  # TODO do we need to return all results?

# Example usage
from pyjobshop.read import read
from pyjobshop.ortools import Solver
from pyjobshop import Objective

loc = "instances/FJSP/Naderi/2.fjs"
data = read(loc)
solver = Solver(data)
TIME_LIMIT = 5

objectives = [Objective.MAKESPAN, Objective.TOTAL_COMPLETION_TIME]
result = solver.sequential_solve(
    objectives,
    TIME_LIMIT,
    log=True,
    num_workers=None,
)

[leonlan]

Not doing adding/removing constraints. Both should be done by means of replacing the ProblemData. It is very hard to define a good interface for adding/removing constraints - the ProblemData interface is essentially the interface that we provide.

[leonlan]

CP Optimizer has a lexicographic objective method: https://ibmdecisionoptimization.github.io/docplex-doc/cp/docplex.cp.modeler.py.html?highlight=minimize#docplex.cp.modeler.minimize_static_lex