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.

Â