Build Your First Mathematical Model with LocalSolver for Dummies

Consider the following problem:

300 boxes need to be loaded and shipped to a warehouse from a factory.

The logistics planner may rent trucks that can accommodate 40 boxes and 30 boxes, for $500 and $400 respectively.

How many trucks of each type to minimise the cost?

Our goal is to minimise the cost of shipping these boxes by selecting the right amount of the different trucks.

This is a simple optimisation problem.

However, we don’t usually think in mathematical term while solving it.

For many people, the answer is simple, even trivial.

A box costs $12.50 for 40-boxes-truck and $13.33 for 30-boxes-truck.

So we should prefer 40-boxes-truck to 30-boxes-truck.

We first put 280 boxes into 7 40-boxes-trucks for $3500 (7 x $500).

Then we add an eighth 30-boxes-truck for $400 for the remaining 20 boxes.

Total cost is $3900 for 8 trucks.

This looks fine.

But this is not the best solution.

With 6 trucks of 40 boxes (240 boxes and $3000) and 2 trucks with 30 seats (60 boxes and $800), we can ship the boxes and pay only $3800).

We can save $100!

The best decision is not that obvious.

Read more about the full background story at Integer Linear Programming with Graphical Method article.

This problem is a very simple example with only 2 variables, which are 2 kinds of trucks.

In reality, real business problems in real companies can contain up to thousands or more variables.

Solving it using your brain purely or graphically is totally impossible.

With modern tools, like LocalSolver, companies can tackle more complex real-world problems and the return of investment would not be just $100 as in our toy truck problem but millions of dollars.

Read: LocalSolver Intro: My Notes on the All-in-one Mathematical Programming Solver for Large-scale Mixed-variable Optimisation

Solve this Truckload Problem with LocalSolver

Please install LocalSolver before proceed, refer this article LocalSolver Setup: Download, Install & License (MacOS).

The first step to solve optimisation problems with LocalSolver is to create a LocalSolver Program (LSP).

Starting up any code editor software (personally I use Sublime Text).

I used test1 as our model name, save into /test1.lsp under folder /lsp.

LocalSolver Program (LSP)

Writing a model in LocalSolver is similar to building models in other programming languages.

You first declare the variables and then define functions for those variables.

LSP is a language for building optimisation models, so it is not surprising that it is structured to set up mathematical optimisation problems.

In addition to mathematical operators, LSP has all characteristics of a scripting language but is dedicated to problem modelling and solving.

Our Truckload Toy Problem

Going back to our truckload toy problem.

2 types of trucks with capacities of 30, 40 respectively and costs of 400, 500 respectively.

The total amount of boxes must not exceed 300.

Here is the mathematical formulation:

Minimise: Cost = 400 x nTruck30 + 500 x nTruck40

Subject to:

1. Boxes: 30 x nTruck30 + 40 x nTruck40 >= 300
2. truck30 >= 0
3. truck40 >= 0

This can be translated to the following LSP model file (.lsp):

/lsp/test1.lsp

 function model() {
  nTruck30 <- int(0,10);
  nTruck40 <- int(0,10);
  
  capacityBox <- 30 * nTruck30 + 40 * nTruck40;
  constraint capacityBox >= 300;
  
  totalCost <- 400 * nTruck30 + 500 * nTruck40;
  minimize totalCost; 
 }
  
 function output() {
  println(nTruck30.value);
  println(nTruck40.value);
 }

Solve the Model

Once we have completed the model, be sure to save our file.

Open our terminal

Go to our file directory

 cd lsp

and write this line

 $ localsolver test1.lsp

where test1.lsp is our model file name that we named previously.

 Kais-MacBook:~ kafechew$ cd lsp
 Kais-MacBook:lsp kafechew$ localsolver test1.lsp
 LocalSolver 9.0.20191219-MacOS64. All rights reserved.
 Load test1.lsp...
 Run model...
 Preprocess model 100% ...
 Run solver...
 Initialize solver 100% ...
 Push initial solutions 100% ...
  
 Model: expressions = 16, decisions = 2, constraints = 1, objectives = 1
 Param: no time limit, no iteration limit
  
 [ optimization direction ]    minimize
  
 [ 0 sec,   0 itr]: No feasible solution found (infeas = 2)
 [ 0 sec, 4048 itr]: obj =    3800
  
 4048 iterations performed in 0 seconds
  
 Optimal solution:
  obj =    3800
  gap =     0%
  bounds =    3800
 Run output...
 2
 6

The trace in console starts with the key figures of the model: number of expressions, decisions, constraints and objectives.

Once the search is finished, the total number of iterations and the elapsed time are displayed, as well as the status and the value of the best solution found.

The solution status can be Inconsistent, Infeasible, Feasible or Optimal.

In our case, the value of the objective function is shown under Optimal solution, which is 3800.

So, we actually need two (2) 30-boxes-trucks and six (6) 40-boxes-trucks to get the lowest $3800 cost.

Model Explanation

L1-10 We begin with function model() {} and write the model inside.

One of the most important step when modelling an optimisation problem with the LSP language is to define what are the decisions to be taken.

These are the values we want to calculate. For example, production quantities, inventory quantities, or transport shipment quantities.

These decisions are such that instantiating them allows evaluating all other expressions of your model (in particular, the constraints and the objectives).

L2-3 Declaring the decision variables

All the variables of the model, called expressions, are declared using left arrows <-.

The decision variables are the best values to solve a problem, still unknown, the optimisation engine will determine the values for these variables and return them as outputs.

We give these variables readable names to help making our code more understandable, which are nTruck3 and nTruck40, the amount of the respective trucks as integer decisions.

Decision variables can be of type

• integer: int()

Integer decisions are used to model integer quantitative decisions taking values in a given range.

• real: float()

Floating-point decisions are used to model continuous quantitative decisions taking values in a given range.

• boolean: bool()

Boolean decisions can take two values 0 or 1. Booleans enables you to model any problem where a binary decision is involved. Most of combinatorial optimization problems (assignment, allocation, packing, covering, partitioning, routing, scheduling, etc.) can be simply expressed as pure 0-1 models.

• list: list()

Ordered collection of integers within a range [0, n - 1]

• set: set()

Unordered collection of integers within a range [0, n - 1]

We set both of these variables to integer int(), declaring a non-negative integer for each decision variable.

Since from the early heuristic, we need maximum 8 trucks to load all boxes.

To be safe, we set the values of boxes for each truck range from zero (because it is not realistic to be zero boxes) to ten.

Each line is always terminated by a semicolon ; called Statement Terminator.

L5-6 Defining the constraints.

These are the elements in the supply chain that limit or restrict the decision variables in some way. Some constraints are related to technical limitations. For example, the capacity of a machine may be a production constraint and the capacity of a truck or train may be a logistical constraint. There can also be managerial constraints. For example, a company may not want to invest more than a certain amount on a particular channel. There can be legal constraints and personnel constraints as well. Generally speaking, constraints act as limitations for the decision variables.

Defining the constraints of your model is another important modelling task. Generally speaking, constraints should be limited to strictly necessary requirements.

Limiting the use of constraints is especially important in local-search modelling because it defines the search space and the ability to move from one solution to another.

A constraint is a kind of tag put on an expression that enforces it to be true (1).

We named the constraint as capacityBox for minimum capacity for boxes needed.

In LocalSolver, any variable or intermediate expression that has a boolean value (0, 1) can be constrained. Thus, "all" expressions involving relational operators (<, <=, >, >=, ==, !=) but also logical and (&&), or (||), xor or immediate if (iif) can be constrained without limitation on the type of the problem. In particular, LocalSolver is not limited to linear constraints but can also handle highly-nonlinear models.

Try to avoid hard constraints as much as possible, because LocalSolver (and more generally local search) is not suited for solving hardly constrained problems. In particular, banish constraints that are not surely satisfied in practice. Ideally, only combinatorial constraints (that is, the ones which induce the combinatorial structure of your problem) have to be set. All the other constraints can be relaxed as primary objectives in order to be “softly” satisfied (goal programming). LocalSolver offers a feature making this easy to do: lexicographic objectives.

L8-9 Defining the Objective function.

These are the Key Performance Indicators (KPIs) that we would like to improve upon. For example, your company may want to minimise costs, maximise profits, or increase customer satisfaction.

At least one objective must be defined with the keyword of either minimize or maximize.

The formulas can be complicated, sometimes we will write the objective function over several lines, to make it readable.

Any expression can be used as objective.

L12-15 Output the solution

You can define an output() function that will be called by LocalSolver at the end of the search. We can output the best solution values for our decision variables with the usual print and println functions.

Comment

The comments start with a /* and end with a */.

// can also be used for single row comment.

It is always a good practice to add comments to help us remember what the model is meant to do.

/lsp/test1.lsp

 /* Declares the optimization model. */
 function model() {
  // Decision Variables
  nTruck30 <- int(0,10);
  nTruck40 <- int(0,10);
  
  // Constraints
  capacityBox <- 30 * nTruck30 + 40 * nTruck40;
  constraint capacityBox >= 300;
  
  // Objective Function
  totalCost <- 400 * nTruck30 + 500 * nTruck40;
  minimize totalCost; 
 }
  
 function output() {
  println(nTruck30.value);
  println(nTruck40.value);
 }

Infeasibility and inconsistency

When submitting a model to LocalSolver (calling method solve), the expected result is to obtain a feasible solution, and even sometimes an optimal solution. However in some cases the returned solution can be infeasible in the sense that the current assignment of values to variables violates some of the constraints of the problem. Two solution statuses are defined for these infeasibility cases:

• infeasible means that no feasible solution was found to the submitted problem but it could not be proven that no such solution exists. Maybe running a longer search would have produced a feasible solution.
• inconsistent means that the solver was able to prove that no feasible solution exists. In this case, LocalSolver offers a functionality for analysing the causes of this inconsistency.

Note that both statuses infeasible and inconsistent can also be encountered on problems where no constraint was defined. Indeed, a solution where an objective takes an invalid value is considered infeasible. For instance minimize sqrt(x) implicitly requires that x takes a non-negative value.

Parameter: Time Limit

Some parameters can be defined in the param() function in order to control the local search.

Some of the control parameters can be set in command line, instead of being defined in the LSP file.

If no time limit is set, the search will continue until optimality is proven (Optimal solution message) or until we force the stop of the program by pressing Ctrl+C.

/lsp/test1.lsp

 /* Declares the optimization model. */
 function model() {
  // Decision Variables
  nTruck30 <- int(0,10);
  nTruck40 <- int(0,10);
  
  // Constraints
  capacityBox <- 30 * nTruck30 + 40 * nTruck40;
  constraint capacityBox >= 300;
  
  // Objective Function
  totalCost <- 400 * nTruck30 + 500 * nTruck40;
  minimize totalCost; 
 }
  
 function output() {
  println(nTruck30.value);
  println(nTruck40.value);
 }
  
 /* Parameterises the solver. */
 function param() {
  lsTimeLimit = 10;
 }

Parameter: lsTimeBetweenDisplays

 if (lsTimeBetweenDisplays == nil) lsTimeBetweenDisplays = 5;

You can disable all displays by setting lsVerbosity to 0.

Each 5th second (in accordance with parameter lsTimeBetweenDisplays), a brief report of the current state of the search is displayed: the number of elapsed seconds and the number of iterations performed, the value of objective functions are given in lexicographic order (separated with |).

Spoiler

For the next tutorials, we will discuss about separating data from the model, pulling data from external data sources, such as an Excel spreadsheet or an Access database.