Lazy-Constraints for modelling soft-constraints (CPLEX + rejectCandidate semantics)

Question

I basically have a (somewhat bloated) assignment-problem on a boolean-matrix: (N_WORKERS, N_TASKS). Let's assume, we only look at one specific worker and therefore we have a 1d boolean assignment-vector: x.

I'm trying to model a soft-constraint which penalizes a time-interval stretch implied by assignments. Each task has a constant start- and end-time and the stretch is defined by the earliest start and latest end:

var_stretch = NonnegativeVariable()

conceptional (linearization necessary):
  var_stretch = max(end(t) for t in tasks if t assigned) - min(start(t) for t in tasks if t assigned)

var_penalty = NonnegativeVariable()

constraint:
  var_stretch - var_penalty <= constant_limit

Example (minimizing var_penalty):

x_0 = Task0 = (0, 200)
x_1 = Task1 = (600, 700)
x_2 = Task2 = (1000, 1400)

constant_limit = 480

Solution (listed = 1, not listed = 0): x_0, x_1, x_2 -> (1400 - 0) - var_penalty <= 480   -> var_penalty = 920

Solution (listed = 1, not listed = 0): x_1, x_2      -> (1400 - 600) - var_penalty <= 480 -> var_penalty = 320

Now the catch:

The problem is of larger scale and a-priori enforcing those constraints does not scale: too many constraints.

(Basically two constraints for each assignment-variable for modelling it's effect = linearization of min/max) which basically results in the solver being unable to even solve the root-relaxation, at least when follow-up MILP solving is necessary: Simplex or IPM + crossover; IPM root-relax only is less of a problem).

My hope: lazy-constraints in modern solvers.

My context / solver: CPLEX 20.1.0.0.

The idea / approach:

• a-priori introduce nonnegative variable var_stretch
• a-priori introduce nonnegative variable var_penalty
• a-priori add the constraint: var_stretch - var_penalty <= constant_limit
• add var_penalty to the objective-term

There is nothing preventing var_stretch being 0 yet -> never any penalty implied!

Then lazily (IloCplex::Callback::Context::Id::Candidate):

• get all assigned tasks of the current candidate solution
• get var_stretch value of candidate solution (which should provide the lower bound of the stretch implies by all the assigned tasks)
• check all pairwise-combinations (pairs of tasks) over those assigned
  • calculate the implied_stretch of this assigned pair (max ends of assigned - min starts of assigned)
  • IF var_stretch@candidate-solution < implied_stretch:
    • rejectCandidate(var_stretch + (1-task_a) * implied_stretch + (1-task_b) * implied_stretch >= implied_stretch)
      • In CPLEX terms: Don't accept solution and add a constraint which "CPLEX may use to cut off further candidate solutions that it finds."

So basically:

• var_penalty can correct stretches too big (soft-constraint) but the objective pushes it down
• var_penalty will correct if var_stretch becomes too big
• var_stretch only origin of becoming too big is the cut within the lazy-constraint (which is not guaranteed to be applied according to the docs)
  • ~ Idea: var_stretch >= some_constant iff both tasks are assigned together

Valid Lazy-constraint usage?

I'm always somewhat puzzled by the formal core (requirements and guarantees) of those lazy-constraints (or user-cuts) and i guess, my approach approach does not really fit both (nor what the CPLEX DOCS call optimality-cuts?).

I implemented this with the formentioned solver (using C++/Concert; Generic-Callback) and those two examples work out as expected. I also already observed the missing guarantee (CPLEX DOCS: rejectCandidate) in regards to the cut ("If not null and not empty, then CPLEX may use these constraints to cut off further candidate solutions that it finds. (There is no guarantee that it does so, though.)"): memorizing already rejected pairs and not re-checking those is wrong! (and might result in zero penalty as we miss out rejecting it again)

I'm still worried, that i might have hidden assumptions not compatible with the internal requirements rendering my approach wrong.

The question:

• Is this approach correct?

For me, the core-question is probably::

• What exactly means rejecting a solution?

  • I guess i assume that one of the following semantics are true / Is one of the following semantics true?

    • A: Rejection is time-local and forgotten after that

      • But i don't see how one would not cycle (at least in worst-case) if rejection would be posted without a cut (which is legal API-usage)

    • B: Rejection is not time-local / not forgotten = memorized but linked to a concept of full-solution-hashing:

      • Solution with task_a, task_b assigned with this one variable expressing the stretch being 0 was rejected and fully-equal solutions can be ignored / rejected again if necessary -> stretch is still 0
      • Solution with task_a, task_b assigned with this one variable expressing the stretch CHANGED (not 0 anymore), e.g. due to the cut being respected, while all others kept the same should not be rejected -> totally new situation to reason about!

Answer 1

CPLEX does not memorize rejected solutions. When you call rejectCandidate, CPLEX adds the violated constraint to a pool of lazy constraints, applies it to the current node and re-solves the LP relaxation. Assuming the original candidate does in fact violate the constraint, CPLEX may find a new candidate at the current node or may prune the node.

As CPLEX continues to chug along, the constraint you added sits in the lazy constraint pool. How it gets used is a bit of a mystery (at least to me), but I'm pretty certain that CPLEX will check whether a new candidate solution satisfies it before going into candidate context (i.e., claiming it has a new incumbent). This is not done by comparing hash codes; CPLEX will evaluate the constraint at the new candidate and see if it is satisfied to within tolerances. Even if CPLEX fails to check a new candidate against the constraint, you should be safe because it will invoke the callback and give you a chance to rediscover that constraint (or discover a new one) that rejects the new candidate.

There is a "contract" between you and CPLEX in which you guarantee to CPLEX that any constraint you add via the callback does not cut off the optimal solution. It is allowed to cut off otherwise feasible integer solutions (unlike a "user cut", which is allowed to trim the fat between the integer hull and the LP hull but is not allowed to cut off integer-feasible solutions).