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

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!