This page is for an old version of Hexaly Optimizer. We recommend that you update your version and read the documentation for the latest stable release.

How to migrate from MIP to LSP?

Note

It is important to understand that LocalSolver is not a MIP solver. More precisely LocalSolver is more than a MIP solver. Similarly to a MIP solver, LocalSolver searches for feasible or optimal solutions, computes lower bounds and optimality proofs and can prove the inconsistency of an optimization model. But LocalSolver 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 LocalSolver offers operators sum, product and arithmetic comparisons, any integer linear program can be directly written in the LocalSolver modeling language. However, such a model does not take advantage of all the simple high level operators of LocalSolver. A set of simple rules is given here to help you reach the best possible performance with LocalSolver.

Let us consider the facility location problem detailed in our example tour. Here is the standard integer program for this problem, written in LocalSolver 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 LocalSolver, 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 LocalSolver 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 LocalSolver 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 LocalSolver 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 LocalSolver 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 LocalSolver from considering a nearby improving solution.