The Linearization box on the Model Generator tab:

page140axp

controls the linearization option in LINGO. Many nonlinear operations can be replaced by linear operations that are mathematically equivalent. The ultimate goal is to replace all the nonlinear operations in a model with equivalent linear ones, thereby allowing use of the faster and more robust linear solvers. We refer to this process as linearization. For more information on linearization, please refer to the section On Mathematical Modeling.

Degree determines the extent to which LINGO will attempt to linearize models. The available options are:

Solver Decides,
None,
Math Only, and
Math and Logic.

Under the None option, no linearization occurs. With the Math Only option, LINGO linearizes the mathematical functions: @ABS(), @FLOOR(), @IF(), @MAX(), @MIN(), @SIGN(). @SMAX(), and @SMIN() along with any products of binary and continuous variables. The Math and Logic option is equivalent to the Math option plus LINGO will linearize all logical operators (#LT#, #LE#, #EQ#, #GT#, #GE#, and #NE#). Under the Solver Decides option, LINGO will do maximum linearization if the number of variables is less-than-or-equal-to 12, otherwise, LINGO will not perform any linearization. LINGO defaults to the Solver Decides setting.

The Delta Coefficient is a tolerance indicating how closely you want the additional constraints added as part of linearization to be satisfied. Most models won’t require any changes to this parameter. However, some numerically challenging formulations may benefit from increasing Delta slightly. LINGO defaults to a Delta of 1.e-6.

When LINGO linearizes a model, it will add forcing constraints to the mathematical program generated to optimize your model. These forcing constraints are of the form:

f( x) ≤ M • y

where M is the BigM Coefficient and y is a 0/1 variable. The idea is that if some activity in the variables is occurring, then the forcing constraint will drive y to take on the value of 1. Given this, if we set the BigM value to be too small, we may end up with an infeasible model. Therefore, the astute reader might conclude that it would be smart to make BigM quite large, thereby minimizing the chance of an infeasible model. Unfortunately, setting BigM to a large number can lead to numerical stability problems in the solver resulting in infeasible or sub-optimal solutions. So, getting a good value for the BigM Coefficient may take some experimentation.

As an example of linearization, consider the following model:

model:

sets:

  projects: baths, sqft, beds, cost, est;

endsets

data:

projects, beds, baths,  sqft,         cost =

p1          5     4     6200        559608        

p2          2     1      820        151826        

p3          1     1      710        125943

p4          4     3     4300        420801        

p5          4     2     3800        374751

p6          3     1     2200        251674

p7          3     2     3400        332426        

;

enddata

min = @max( projects: @abs( cost - est));

@for( projects:

est = a0 + a1 * beds + a2 * baths + a3 * sqft

);

end

Model: COSTING

This model estimates the cost of home construction jobs based on historical data on the number of bedrooms, bathrooms, and square footage. The objective minimizes the maximum error over the sample project set. Both the @MAX() and @ABS() functions in the objective are non-smooth nonlinear functions, and, as a result, can present problems for LINGO’s default, local search NLP solver. Running the model under the default settings with linearization disabled, we get the following result:

  Local optimal solution found at step:             91

  Objective value:                            3997.347

        Variable           Value        Reduced Cost

              A0        37441.55            0.000000

              A1        27234.51            0.000000

              A2        23416.53            0.000000

              A3        47.77956            0.000000

Enabling linearization and re-optimizing yields the substantially better solution:

  Global optimal solution found at step:           186

  Objective value:                            1426.660

        Variable           Value        Reduced Cost

              A0        46814.64            0.000000

              A1        22824.18            0.000000

              A2        16717.33            0.000000

              A3        53.74674            0.000000

Note that the maximum error has been reduced from 3,997 to 1,426!

Linearization will substantially increase the size of your model. The sample model above, in un-linearized form, has a mere 8 rows and 11 continuous variables. On the other hand, the linearized version has 51 rows, 33 continuous variables, and 14 binary variables! Although linearization will cause your model to grow in size, you will tend to get much better solution results if the model can be converted entirely to an equivalent linear form.

Note:Linearization will be of most use when a nonlinear model can be 100% linearized. If LINGO can only linearize a portion of your model, then you may actually end up with a more difficult nonlinear model.

The linearization option is set to Solver Decides by default.