Limit Variable Creation to Viable Options

Let’s say that Andrew is not available on D4 and D5 because of Thanksgiving. If the worker is not available, then the engine should not select them. If the engine cannot select them, then WHY create a variable? By avoiding creating the variable, you eliminate a selection variable, and you save the need for a constraint. This preprocess enforces a constraint before the solver is executed.

Distance is a great example. If the Worker is too far away from the Task, then the Worker cannot be assigned the task. Where is the constraint in the engine that describes this??? It doesn’t exist? Did Sara fail to write code correctly? No. She simply did not create a variable for a combination of worker, and task that was not valid.

Obvious right?

Well no. Remember how the mathematicians are writing the loops…

This implies EVERY worker on EVERY task for EVERY day, but this is NOT what they mean. What they mean is everyone for which they created a variable. If they didn’t create a Variable for R=3, T=2, and D=4, then that variable is NOT part of the objective.

Multiple Objectives

The design may call for multiple objectives. Perhaps one objective is to maximize the number of selections. But there may be multiple ways to solve the problem and achieve that number of selections. The second objective could be to minimize cost.

This objective maximizes the number of selections X. This could be followed by…

The idea would be to solve the problem with the first objective and turn around and solve it again but with the second objective.

If this is done, the only result will be for the minimization of cost. It likely results in no selections. This isn’t very useful. It is because a step is missing. The result from the first objective must be converted to a constraint and added to the problem before solver for the second objective. This would result in minimizing the cost for a solution that results in now fewer than the maximum number.

Logical Operations

Constraints can be created to produce logical operations. These can apply to selection problems with selection variables. As a developer, you will likely not be called upon to write these yourself. The science team will have likely designed the MIP for you, but it’s enlightening to see some combinations to really gain a depth of understanding of the mathematicians’ work.

Logical AND: Use the linear constraints y1≥x1+x2−1, y1≤x1, y1≤x2, 0≤y1≤1, where y1

is constrained to be an integer.

Notice that Y1 is only true if both X1 “and” X2 are true.

Logical OR: Use the linear constraints y2≤x1+x2, y2≥x1, y2≥x2, 0≤y2≤1, where y2 is constrained to be an integer.

Notice that Y2 is only true if either X1 “or” X2 is true.

Logical NOT: Use y3=1−x1.

Logical Implication: To express y4=(x1⇒x2) (i.e., y4=¬x1∨x2), we can adapt the construction for logical OR. In particular, use the linear constraints y4≤1−x1+x2, y4≥1−x1, y4≥x2, 0≤y4≤1, where y4 is constrained to be an integer.

Notice that Y4 is only true if X1 and X2 are equal. The value is the ability to use Y4 in other constraints.

Forced logical implication: To express that x1⇒x2 must hold, simply use the linear constraint x1≤x2 (assuming that x1 and x2are already constrained to boolean values).

Notice that Y4 is true if X2 is true or both X1 and X2 are false.

XOR: To express y5=x1⊕x2 (the exclusive-or of x1 and x2), use linear inequalities y5≤x1+x2, y5≥x1−x2, y5≥x2−x1, y5≤2−x1−x2, 0≤y5≤1, where y5 is constrained to be an integer.

Notice that Y5 is true if and only if X1 or X2 is true but not if both X1 and X2 are true.

Cast to boolean (version 1): Suppose you have an integer variable x, and you want to define y so that y=1 if x≠0 and y=0 if x=0. If you additionally know that 0≤x≤U, then you can use the linear inequalities 0≤y≤1, y≤x, x≤Uy; however, this only works if you know an upper and lower bound on x. Alternatively, if you know that |x|≤U(that is, −U≤x≤U) for some constant U, then you can use the method described here. This is only applicable if you know an upper bound on |x|.

Decision variables may be Boolean for selection variables. The logic may be based on some real or integer number. A conversion from that to a Boolean is helpful in getting useful results from the program. Notice the requirement to know the maximum; this is not always trivial.

Cast to boolean (version 2): Let's consider the same goal, but now we don't know an upper bound on x. However, assume we do know that x≥0. Here's how you might be able to express that constraint in a linear system. First, introduce a new integer variable t. Add inequalities 0≤y≤1, y≤x, t=x−y. Then, choose the objective function so that you minimize t. This only works if you didn't already have an objective function. If you have n non-negative integer variables x1,…,xn and you want to cast all of them to booleans, so that yi=1 if xi≥1 and yi=0 if xi=0, then you can introduce n variables t1,…,tn with inequalities 0≤yi≤1, yi≤xi, ti=xi−yi and define the objective function to minimize t1+⋯+tn. Again, this only works nothing else needs to define an objective function (if, apart from the casts to boolean, you were planning to just check the feasibility of the resulting ILP, not trying to minimize/maximize some function of the variables).

BIG M (IF THEN): If a tech is assigned to this task in this district on this day, then it cannot be assigned to any of these tasks in the other districts on that day.

if z = 0, then x = 0

where z binary, and x >= 0

We could use the big-M formulation:

x - M * z <= 0

If Z is zero, then X is 0. If Z is not zero, then we don’t care. Truth table reflects not caring as 1. That is driven by the M being so large that it outweighs the X. Hence Big M.

Notice that this is very similar as Cast to Boolean. It’s just a different presentation of the same idea. M is U. The problem must be set up with these to be sufficiently large. The result is 1 if a set of conditions is true else it is 1 – a cast to Boolean.

Configuring Solver

Platform supplies a MIPConfig class. This class is extended by a GurobiMIPConfig. These classes wrap a JSON and provide common config values. This structure is loose to allow specific engines to add in their own custom config information that they need to pass to the engine.

• MIP_ENGINE – which solver to use: Gurobi, Cplex, etc.

• TIMIE_LIMIT_IN_SECONDS – maximum time described in seconds

• TIME_LIMIT – maximum time described in milliseconds

• RELATIVE_MIP_GAP – stop solver as soon as it gets close enough to optimal answer

• ABSOLUTE_MIP_GAP – stop solver as soon as it gets close enough to optimal answer

• EXPORT_MIP – instruct the solver to export the program in LP format

MIP Wrapper

Platform supplies a MIPWrapper that separates ONE Network engines from the specific solver such as Gurobi, CPlex, etc…

MipWrapper has functions that help you build the program, define variables, constraints, exporting problems, and solving. The MIPWrapper also contains MipMap which assists in the difficult task of mapping variables within the MIP and variables in the engine code.

The following code snippet shows how to instantiate the wrapper. Notice that it passes a MIPConfig (basically a JSON string of engine parameters). The engine name defaults to GUROBI but the MIPConfig can override this.

String engineName = MIPEngineFactory.GUROBI;

mipWrapper = new MIPWrapper(engineName, mipEngine);

mipWrapper.setConfig(dataModel.getMIPConfig());

MIP Map

Platform provides a MIPMap class. This class matches a key in the form of a byte array to an index. The index is an index for a variable within the solver. The byte array is a combination of attributes that describe the variable.

In a previous section, we had a variable Xrtd. Assume that there were other variables such as Y and Z. The first attribute is the fact that it is X. The next set of attributes is the r, t, and d. There are four attributes in all.

In order to form the byte array, we must know the maximum value for each attribute. The number of variable types is 3 (X, Y, and Z). The number of r might be 16, the number of tasks might be 24, and the number of d might be 48. It takes 2 bits for the 3, 5 bits for 24, and 6 for 48. The total number of bits is 13. Two bytes for 13 bits. The key is a 2-byte array.

The following code segment is key to setting up the MIPMap within the MIPWrapper.

private void defineVariableKeyFormat(DataModel dataModel, MIPProcessData mipProcessData) {

ArrayList<ByteArrayEncoder.Entry> keyFormat = new ArrayList<ByteArrayEncoder.Entry>();

int noOfResourceVariables = dataModel.getResourceGeographies().size();

//task variables

int noOfTaskVariables = dataModel.getTasks().size();

// Goal variables

int noOfGoalVariables = dataModel.getObjective().getObjectiveSequence().size();

ByteArrayEncoder.Entry varEntry = new ByteArrayEncoder.Entry(RESOURCES, noOfResourceVariables);

ByteArrayEncoder.Entry varEntryTasks = new ByteArrayEncoder.Entry(TASKS, noOfTaskVariables);

Optional<Entry<Integer, Integer>> maxEntry = mipProcessData.getResIndexToMaxDayCount().entrySet().stream().max((e1, e2) -> e1.getValue()

.compareTo(e2.getValue())

);

int noOfDayVariables= maxEntry.get().getValue();

ByteArrayEncoder.Entry varEntryDays = new ByteArrayEncoder.Entry(DAYS, noOfDayVariables);

ByteArrayEncoder.Entry varEntryGoals = new ByteArrayEncoder.Entry(GOALS, noOfGoalVariables+1);

keyFormat.add(varEntry);

keyFormat.add(varEntryTasks);

keyFormat.add(varEntryDays);

keyFormat.add(varEntryGoals);

mipWrapper.setVariableFormat(keyFormat);

}

The key here is that four attributes are used to describe all of the variables in this program. The first attribute is a number of resources, next is a number of tasks, third is a number of days, and the last is a number of goals. Notice that for each of these it inspects the data model (contain of all data being used by engine) to calculate these maximums.

The real takeaway is that the developer needs to know that a mapping must take place. This mapping is done by a set of attributes to an index. The developer needs the index when working with the solver and the set of attributes when working with their code. The set of attributes is an array of values that must be meaningful to the engine code (i.e. the 3^rd worker, 17^th task, and the 2^nd day).

Variable Declaration

MIPWrapper provides method createVariable(). There are two basic uses of this function – create a variable with a name and without a name. Named variables are easy to use – no need for MIPWrapper. You can refer to the variable by know and the solver understands the correct variable. But this is terrible for performance in that you build up millions of string names. The second use is for variables without names. This is where it becomes important to track the index within the solver to variable in your code.

The following is a sample of a call. It is a variable with no name. The minimum is 0 and the maximum is the maximum value of a real number. The type of Float (i.e. real). The goalKeyArray requires a little more understanding.

mipWrapper.createVariable(NO_NAME, BOOLEAN_MIN, Double.MAX_VALUE, MipVariableTypeEnum.FLOAT, goalKeyArray);

goalKeyArray is an array of attributes that define the variable. In the previous section that discussed the MIPMap, the map is keyed by a byte array. To avoid having all of the engine code work with byte arrays, Platform exposes this as an array of integers. One element in the array for each attribute. The value of each attribute should NOT exceed the maximum as defined when the MIPMap was first created. If this is not adhered to, then the mapping will break down as keys will overlap.

MIPWrapper is smart enough to know if the variable has been added before. The engine code simply tries and creates variables as required, safe in the knowledge that it will not create duplicates. But it should be noted that this processing is not free. If a process can be developed such that the order will generate no duplicates, then this is optimal. If the engine code must keep its own map of variables, then it is wasting its time. It's no more difficult for MIPWrapper to compare against its map than for the engine code to compare against its own.

The following sample code puts the variable creation inside a couple of loops. In this case, it is days and the available days a worker can be assigned. assignmentKeyArray is the integer array of attributes that describe the variable. You can imagine that in here there could be logic – do not create this variable if the worker is not available for example. Placing the logic here removes the option from the solver. Rather than creating a variable and a constraint, avoid creating the variable in the first place.

for (int day = 0; day<= noOfDays; day++) {

long taskDate = dateIncrementer(task.getEarliestDate(), day);

int dayIndex = -1;

for (Long key : mapDateToAvlHours.keySet()) {

++dayIndex;

if(key.equals(taskDate)) {

List<Double> estDriveAndTotalTime = new ArrayList<Double>();

estDriveAndTotalTime.add(xEstDriveTime);

estDriveAndTotalTime.add(xTotalTime);

int[] assignmentKeyArray = {resIndex, taskIndex, dayIndex, NO_INDEX};

estDriveAndTotalTime.add((double)mapDateToAvlHours.get(taskDate));

if (resGeo.getWorkerType().equals(WorkerTypeEnum.CONTRACTOR.toString())) {

estDriveAndTotalTime.add(1d);

}

else {

estDriveAndTotalTime.add(0d);

}

estDriveAndTotalTime.add(eDist);

taskIndexes.add(taskIndex);

mapAssignmentArrayToDriveTimeToTotalTime.put(assignmentKeyArray, estDriveAndTotalTime);

if (LOG.isDebugEnabled()) {

mipWrapper.createVariable(AssignmentSelection.getVariableName(assignmentKeyArray), BOOLEAN_MIN, Double.MAX_VALUE, MipVariableTypeEnum.BOOLEAN, assignmentKeyArray);

}

else {

mipWrapper.createVariable(NO_NAME,BOOLEAN_MIN, Double.MAX_VALUE, MipVariableTypeEnum.BOOLEAN, assignmentKeyArray);

}

break;

}

}

}

Constraint Creation

MIPWrapper provides a function to add Constraints. The addConstraints function is very flexible and thus a little confusing. addConstraints can add multiple constraints in one call! This can be useful if the logic for building constraints is done PRIOR to adding constraints. If this logic for determining a single constraint is executed and a call for adding a constraint is done, then only one constraint is added at a time.

Let’s look a little more closely.

/**

*

* @param constraintVariables: variables that are in constraint equation

* int[constraint Number][variable][varriableAttributes]

* @param coefficients : variable coefficients

* double[constraint Number][coefficient]

* @param constraintType : constraint type as LESS_THAN_OR_EQUAL, GREATER_THAN_OR_EQUAL or EQUAL

* @param constraintRightHandSide: right hand side value for constraints

*/

mipWrapper.addConstraints(constraintVariables, constraintVarcoefficient, constraintType, constraintRightHandSide);

ConstraintVariables and constraingVarCoefficient describe the monomials that make up the constraints. In order to match values from one structure to another, we have to be sure we are talking about the same constraint (if creating more than one at a time), the position the variable is in within the constraint (is it the first variable or second?), then finally the integer array that describes the variable itself.

Let’s look at the flowing constraint.

2x1 + x2 <= 1000

Because we are passing only 1 constraint, the constraint number is always 1. The variable x1 is in position 1. The variable x2 is in position 2. There would be a set of attributes that describe X1 and X2. The constraintVariable would have an entry for x1 that would be 1 (constraint), 1 (position), and attribute array describing x1. The constraintVarCoefficient would also have the constraint and position but then it would just be a value. The coefficient for x1 would be 1 (constraint), 1 (position), 2 value.

constraintVariable

constraintVarCoefficient

Constrainttype and constraintRightHand side work the same way in regards to an index for the constraint. But there is no position; there is only one type (equality/inequality) and only one right hand side.

constraintType

constraintRightHandSide

Because there can be hundreds of thousands of constraints, constraint creation often finds itself in a loop. Let’s take a look at a sample…

for (int taskIndex: taskIndexes) {

int taskId = taskIndex;

List<int[]> eachResWithSameTaskList = mapAssignmentArrayToDriveTimeToTotalTime.keySet().stream()

.filter(k -> k[1] == taskId)

.collect(Collectors.toList());

if (eachResWithSameTaskList.size()>0) {

int resSize = (int) eachResWithSameTaskList.size();

int[][][] constraintVariables = new int[tasks.size()][][];

double[][] constraintVarcoefficient = new double[tasks.size()][];

ConstraintTypeEnum constraintType[] = new ConstraintTypeEnum[tasks.size()];

double[] constraintRightHandSide = new double[tasks.size()];

constraintVariables[taskIndex] = new int[resSize][];

constraintVarcoefficient[taskIndex] = new double[resSize];

int locationIndex=0;

for(int[] assignmentKeyArray : eachResWithSameTaskList){

constraintVariables[taskIndex][locationIndex] = assignmentKeyArray;

constraintVarcoefficient[taskIndex][locationIndex] = 1.0;

locationIndex++;

}

constraintType[taskIndex] = ConstraintTypeEnum.LESS_THAN_OR_EQUAL;

constraintRightHandSide[taskIndex] = 1.0;

mipWrapper.addConstraints(constraintVariables, constraintVarcoefficient, constraintType, constraintRightHandSide);

}

}

From this you can get an idea of what’s going on. At the time of this writing, it appears there may be a mistake in this code – in that the first index is being sized to the number of tasks but there is only one. But this sample should be good enough to see how the MipWrapper can be used to automate constraint construction through reference of variables via their attributes.

Adding Objective

MIPWrapper provides ability to define an objective. This is similar to the Constraint but more straightforward in that there is only one for any given problem. Note that in previous sections we discussed multiple objectives. That is referring to creation of a problem, adding objective, solving and then adding another constraint, next objective, and solving. There are two programs being solved – not just one.

mipWrapper.addObjective(objectiveGoalVariable, goalcoefficient, ObjectiveTypeEnum.MAXIMIZE);

ObjectiveGoalVaraible and goalCoefficeint work like their compatriots in addConstraint. They have one fewer dimension in that there is only one objective.

Consider the following objective: Max (X1 + X2)

objectiveVariable

objectiveCoefficient

Objective type is Maximize. And that’s it. Same logic with the Attributes mapping the variable.

Solving

MIPWrapper provides a solve method. The variables, constraints, and objectives loaded prior to this step along with the MIPConfig are all that is needed.

if (mipWrapper.solve()) { // solve MIP model

if (isInfo) {

LOG.info("MIP solved");

}

mipSuccess = true;

double objectiveValue = mipWrapper.getObjectiveValue();

if (isInfo) {

LOG.info("objectiveValue: " + objectiveValue);

}

}

else {

LOG.info("Failed to solve MIP model for goal: " + goal);

break; // Failed to solve MIP model no need to execute for any other goal

}

The only real question is what to do in the event of an exception. Solve returns a Boolean – if it is false then this code is simply writing a log statement. Clearly, reading about GUROBI and the possible exit conditions and how you want your application to behave is critical. For example, we had one engine that we set a short time out. Then detect if it timed out and then simplified the problem and reran. This ensured we always got a result – but tried, as much as we were willing to wait, to get the most optimal response.

Parsing the Result

MIPWrapper provides several methods to get variable values. The value of the variables is the value that was required to get the optimal result. MipWrapper also provides getObjectvieValue that gets the maximized or minimized result. Often users don’t particularly care for these values, but it is interesting for logging or debugging purpose.

double objectiveValue = mipWrapper.getObjectiveValue();

In the following example, the developer decided they wanted all of the selection variables. They are trying to decide which combination the solver chose. In this case, they saved the set of attributes describing all of these variables in an external object (mapAssignmentArrayToIndex). This is a bit excessive. It shows that perhaps we need to extend the MipMap to track something like Selection Variable so that we can simply ask MipWrapper to return the variables used as selection criteria.

Map<int[], List<Double>> mapAssignmentArrayToIndex = mipProcessData.getMapAssignmentArrayToDriveTimeToTotalTime();

for (int[] assignmentKeyArray : mapAssignmentArrayToIndex.keySet()) {

double variableValue = mipWrapper.getVariableValue(assignmentKeyArray);

if (variableValue > 0) {

selectedAssignmentArrays.add(assignmentKeyArray);

}

}

LP Files

There are many standard file formats solvers use to describe the Linear and Integer Programs that they can solve. The tools at One Network take advantage of the LP (Linear Program). The solvers support a feature to export their problems in this format. Most engines created at One Network have an engine option that request the solver to export this format and save it the shared folder.

This LP File is a valuable debugging tool that can be provided to the OR guys in the AI team or even be passed to Gurobi technical support. Gurobi technical support is actually quite impressive in their ability to help in creating programs, debugging programs, and configuring Gurobi to best solve programs. This LP file can be used to help leverage their support.