How to migrate from MIP to LSP?¶

Note

It is important to understand that Hexaly Optimizer is not a MIP solver. More precisely Hexaly Optimizer is more than a MIP solver. Similarly to a MIP solver, Hexaly Optimizer searches for feasible or optimal solutions, computes lower bounds and optimality proofs and can prove the inconsistency of an optimization model. But Hexaly Optimizer not only achieves this on linear models but also on highly non linear and combinatorial models, involving high-level expressions like collection variables, arrays, or even external functions.

Since Hexaly Optimizer offers operators sum, product and arithmetic comparisons, any integer linear program can be directly written in the Hexaly modeling language. However, such a model does not take advantage of all the simple high level operators of Hexaly Optimizer. A set of simple rules is given here to help you reach the best possible performance with Hexaly Optimizer.

Let us consider the facility location problem detailed in our example tour. Here is the standard integer program for this problem, written in Hexaly syntax:

// A MIP-like model for the facility location problem
x[i in 0...N] <- bool();
y[i in 0...N][j in 0...N] <- bool();

constraint sum[i in 0...N](x[i]) <= p;

for [i in 0...N]
  constraint sum[j in 0...N](y[i][j]) == 1;

for [i in 0...N][j in 0...N]
  constraint y[i][j] <= x[j];

cost[i in 0...N] <- sum[j in 0...N](y[i][j] * w[i][j]);

totalCost <- sum[i in 0...N](cost[i]);
minimize totalCost;

Decision variables and intermediate expressions¶

As explained in our Modeling principles, the most crucial modeling decision is the choice of the set of decision variables. Here, the set of y[i][i] could be a good set of decision variables since the values of x[i] variables can be inferred from the values of y[i][j]. Let’s see how to express the rest of the model based on these decisions.

Using non-linear operators instead of linearizations¶

x[i] variables can be inferred from y[i][j]: indeed, if we choose to link location j to facility i, then necessarily i is a facility. This relation is expressed linearly with the constraint y[i][j] <= x[j]. With Hexaly Optimizer, this can be directly written with non-linear operator or, as follows: x[i] <- or[j in 0...N](y[i][j]).

Alternatively, we can notice that in this problem the optimal solution always links a location to its nearest facility, meaning that we can omit the y[i][i] variables and keep only the x[i] instead, thus reducing the number of variables to N instead of N².

The cost between location i and facility j corresponds to the distance between the two only if j is effectively a facility. To ignore the distances with locations that are not facilities, we can simply use an arbitrary huge value to stand for the infinity. Such conditions can be expressed with a iif operator, also written in Hexaly with the ternary operator ?:. To obtain the minimum cost, we can then use the min operator to choose among the potential distances.

Similarly, all linearizations of a maximum, a product or a conjunction should be translated into their direct Hexaly Optimizer formulation with operators max, prod, and and. Piecewise linear functions can be simply written as well. If your MIP contains a piecewise linear function (possibly with associated binary variables) making Y equal to f(X) such that on any interval [c[i-1],c[i]] we have Y = a[i] * X + b[i] with i in (0…4), then you will directly define Y as follows: Y <- X < c[1] ? a[1]*X+b[1] : (X < c[2] ? a[2]*X+b[2] : a[3]*X+b[3]);

After these transformations we obtain the following model:

function model() {
  x[i in 0...N] <- bool();
  constraint sum[i in 0...N](x[i]) <= p;

  costs[i in 0...N][j in 0...N] <- x[j] ? w[i][j] : wmax;
  cost[i in 0...N] <- min[j in 0...N](costs[i][j]);

  totalCost <- sum[i in 0...N](cost[i]);
  minimize totalCost;
}

Remove useless constraints¶

If your model contains valid inequalities they can (and should) be removed. Since Hexaly Optimizer does not rely on a relaxation of the model, these inequalities would only burden the model.

You must omit symmetry-breaking constraints as well: since Hexaly Optimizer does not rely on tree-based search, breaking symmetries would just make it harder to move from a feasible solution to another one. Typically it could prevent Hexaly Optimizer from considering a nearby improving solution.