Do Google Optimization Tools support Soft Constraints?

Question

I was wondering if anyone familiar with Google Optimization tools can address this. I was looking at the Google examples both employee scheduling and N-queens. Both example seem to have the optimizer running only on hard constraints (e.g. this must be the case) but doesn't seem to solve (this is the preferred but not required). Is there support for soft-constraints? Or is the only implementation of soft constraints at this time optaplanner?

I'm not opposed to optaplanner. It just will require a lot more effort to learn enough java and the "drools" syntax used.

Janiuszck

You can implement "soft constraints" with any solver. Just make the constraint elastic i.e. add slacks and put them in the objective with a penalty. – Counterweigh

I really appreciate the reply. I've been looking through the Google OR-tools and examples. I don't see where in the objective function parameters you can add slack/elasticity. Do you know where this may be documented? – Janiuszck

This not unique to OR-Tools but much more general. An LP book may help. – Counterweigh

Answer 1

Implementation of soft constraint

As Erwin points out, to implement soft constraints, we need to add slack variables to our model and place them in the objective function. To do this, we add two more decision variables for each soft-constrained variable we have in our problem. These decision variables represent the slack in our variable of interest. We can then use the following formula to create our soft constraint:

x1 + x1_surplus - x1_deficit = goal

Where x1 is our decision variable, x1_surplus and x1_deficit are our positive and negative slack variables respectively, and goal is the number we are aiming for on our decision variable x1.

Once we have this constraint in place, we must add an objective that minimizes the total percentage deviance which would look something like:

minimize:
    (1/goal) * x1_surplus + (1/goal) * x1_deficit

Note:

We use percentage deviation because we often deal with variables that are measured in different units (e.g. kilograms vs. pounds in the example below). If we do not use percentage deviation the effect of slack in our variables will be unbalanced.

Example in Google OR Tools

Here is a basic working example in Google OR Tools. Here, we are making two products, A and B, and have a certain number of each product we would like to make. We also have a cost associated with making these products and a goal for the amount that we would like to spend on making the products (+/- 10000 in this case).

from ortools.linear_solver import pywraplp

solver = pywraplp.Solver("Soft Constraint Example", pywraplp.Solver.GLOP_LINEAR_PROGRAMMING)

product_a = solver.IntVar(0, 10000, "Pounds of Product A:")
product_b = solver.IntVar(0, 10000, "Pounds of Product B:")

product_a_surplus = solver.IntVar(0, 100, "Product A Surplus:")
product_a_deficit = solver.IntVar(0, 100, "Product A Deficit:")

product_b_surplus = solver.IntVar(0, 100, "Product B Surplus:")
product_b_deficit = solver.IntVar(0, 100, "Product B Deficit:")

cost_surplus = solver.IntVar(0, 10000, "Cost Surplus:")
cost_deficit = solver.IntVar(0, 10000, "Cost Deficit:")

product_a_goal = solver.Add(product_a - product_a_surplus + product_a_deficit == 500)
product_b_goal = solver.Add(product_b - product_b_surplus + product_b_deficit == 250)

cost_goal = solver.Add(product_a * 100 + product_b * 200 - cost_surplus + cost_deficit == 75000)

solver.Minimize(
    (1/100) * product_a_surplus
    + (1/100) * product_a_deficit 
    + (1/200) * product_b_surplus 
    + (1/200) * product_b_deficit
    + (1/75000) * cost_surplus
    + (1/75000) * cost_deficit
)

status = solver.Solve()

print(status == solver.OPTIMAL)

final_cost = product_a.solution_value() * 100 + product_b.solution_value() * 200

print("Final Cost:", final_cost)

var = [product_a, product_b, product_a_surplus, product_a_deficit, 
       product_b_surplus, product_b_deficit,
       cost_surplus, cost_deficit]

for v in var:
    print(v.name(), v.solution_value())

Urga

Answer 2

In OptaPlanner, you don't have to use the drools syntax any more. You can use the new, incremental ConstraintStreams instead. ConstraintStreams are fast and scalable.

Here's an example how to use them on the NQueens problem you asked:

protected Constraint horizontalConflict(ConstraintFactory factory) {
    // Select a queen
    return factory.from(Queen.class)
            // Select a different queen on the same row
            .join(Queen.class,
                    equal(Queen::getRowIndex),
                    lessThan(Queen::getId))
            // Tell OptaPlanner not to put 2 queens on the same row
            .penalize("Horizontal conflict", HardSoftScore.ONE_HARD);
}

// For reference, the model:
@PlanningEntity
class Queen {
     long id;
     int columnIndex;
     @PlanningVariable
     int rowIndex;
     ... // getters/setters
}

Similarly for employee rostering you asked:

protected Constraint skillLacking(ConstraintFactory factory) {
    // Select a shift
    return factory.from(Shift.class)
            // The shift's employee doesn't have the required skill
            .filter(shift -> !shift.getEmployee().getSkillSet()
                    .contains(shift.getRequiredSkill())
            // Tell OptaPlanner to avoid that
            .penalize("Skill lacking", HardSoftScore.ONE_SOFT,
                    // Lose one soft point per minute of the shift
                    shift -> shift.getDurationInMinutes());
}

// For reference, the model:
@PlanningEntity
class Shift {
     Skill requiredSkill;
     LocalDateTime start;
     LocalDateTime end;
     @PlanningVariable
     Employee employee;
     ... // getters/setters
}
class Employee {
     String name;
     Set<Skill> skillSet;
     ... // getters/setters
}

Musteline