0:41

The techniques for solving problems with continuous variables are such that

they can tackle very large models.

The same cannot be said about solution methods for models with integer variables.

This is why researchers have developed alternative methodologies to

deal with integer problems.

These methodologies are capable of finding very good solutions but

they cannot guarantee for these solutions to be optimal.

The solution procedures based on these methodologies are designed to search for

improved solutions, however, at some point they give up.

And they return the best solution that they find,

the best solution that they found could be optimal, but we don't know.

These methodologies are known as Metaheuristics, and

the solutions that they find are known as heuristic solutions.

Metaheuristics provide great flexibility.

The modeling of the problem is not limited to linear functions.

An Excel model to be solved with Metaheuristics can have anything you want.

For example, nonlinear functions, such as logarithmic or exponential functions.

Non-smooth functions, such as IF or LOOKUP functions.

Let's take a look at an example.

Market basket analysis is a technique to generate practical rules.

That the store can apply in order to maximize its cross-selling opportunities.

The objective of the analysis is to establish rules that state if

x is purchased, then y is also likely to be purchased.

The analyses also produces statistical evidence that the rules

are the result of some systematic behavior and not just pure chance.

To measure the strength of the relationship between two items,

market basket analysis uses the so called Lift Ratio.

If we have items x and

y then the Lift Ratio tells us how much more likely it is for

item y to be purchased given that item x has been purchased.

For example, a Lift Ratio of two tells us that the moment

x is purchased then the probability that y is also purchased doubles.

A common assumption is that maximizing cross-selling opportunities is equivalent

to maximizing the total lift ratios of products that are close to each other.

Proximity depends on the context,

in e-commerce proximity means showing related products on a web page.

For example, proximity is to show an ad for

a toner cartridge on a web page that advertises a laser printer.

In physical spaces,

proximity is achieved by placing related products near each other.

Let's see how Heuristic Optimization can help with this problem.

Assume that a market basket analysis for a chain of grocery stores

produces the Lift Ratios for six product categories shown in this table.

The store will like to figure out the optimal placement of the products

in order to maximize the total lift ratio

of product categories that are close to each other.

The lift of a location is a sum of for the lift ratios for

the immediately adjacent locations.

In this example the lift for Produce is the sum of the lift ratios of Produce and

Dairy, Produce and Meat, and Produce and Soft Drinks.

Let's take a look at the special mold for this problem.

Locate and open the Excel file Store Layout Optimization.

There are three tables in this spreadsheet.

The first one contains the Lift Ratios produced by the market basket analysis.

The second table contains the decision variables.

The variables consist of the index of the product category

that is placed in each position of the Store Layout.

The placement shown here is arbitrary,

it follows the order of the product categories.

We have 1, 2, and 3 in the first row, and then 4, 5, and 6 in the second row.

The next table calculates the lift values for each position in the layout.

For instance, product category 1, which is Produce, is assigned to position A1.

5:13

The lift for position of A1 is the sum of the Lift Ratios between Produce and

Dairy, which is assigned to position A2 and

Produce and Soft Drinks, which are assigned to position B1.

That is 1.2 plus 0.9, which equals 2.1.

Note that the model uses the INDEX Function to calculate all the Lift values.

The use of this function is not allowed in Linear or

into your programming formulations.

This is why we are not going to be able the standard LP solver for this problem.

The Total lift is the sum of all the lift values.

Click on the ASP tab to access the Optimization Mode.

You can see that the objective is to maximize the Total lift.

The variables are the product category

placements in the light gold cells from C14 to E15.

ASP includes the all different Constraints.

This constraint type is only available in heuristic optimization.

It indicates that the values of the decision variables must be integer and

all different.

This is exactly what we need for this model.

The metaheuristic solver in ASP is called evolutionary engine.

We can either click on the Engine tab and choose Standard Evolutionary Engine

from the drop-down menu or let ASP choose the engine automatically.

We're going to let ASP choose an engine.

Click on the Mall tab, and then on the Play Button,

to start the optimization process.

6:53

ASP finds a solution, and reports that the solver has converged.

Note, that this message is different from me stating that the optimal solution has

been found.

ASP uses green as an indicator that it has found and confirmed the optimal solution.

Click on the Output tab,

ASP runs a diagnosis to figure out what engine to use.

During this process you found out that the model includes a non-smooth operation,

the INDEX function.

The model is diagnosed as NSP, non-smooth problem.

This is why ASP selected the Standard Evolutionary Engine.

The rest of the output shows some information about the search

that we're not going to discuss.

As you can see from this example,

metaheuristic optimization allows you to develop very flexible models.

With this technology, we are not restricted to linear functions or

to the three standard types of constraints.

The application of metaheuristic optimization to problems

in industry has increased exponentially since the early 1990s.