Solving Constrained Black-Box Optimization Problems

Tutorial Simulation Optimization

Emeline Senior Optimization Scientist March 29, 2021

In this post, we present the model and results obtained by LocalSolver on a simulation optimization problem arising in the field of Revenue Management.

In the revenue management problem, a businessman wants to maximize revenue from selling a product over a time horizon divided into several periods. At the beginning of the time horizon, he decides how much product to buy to have sufficient inventory for all periods. He chooses the number of units to sell in each period, provided that the total number of units sold over the time horizon does not exceed the initial amount purchased. The product price increases over the periods, which means that the businessman needs to determine the number of units reserved for customers who arrive later because they will pay more. He must therefore consider later demands to make a wise decision in each period. Since demand for the product is stochastic, the businessman simulates it many times to obtain a robust estimate of his revenue.

To solve this problem, we rely on the external function‘s capabilities of LocalSolver. Black-box optimization, also known as surrogate modeling, is useful to optimize a function that is computationally expensive to evaluate or difficult to write analytically (hence the name “black-box”). In this problem, a Monte Carlo method is used: the demand is simulated a large number of times (1,000,000 simulations). For allocating units, each revenue is calculated according to each demand, and the mean revenue is then calculated. This simulation can take several seconds and thus is considered a black-box function. In LocalSolver, a black-box function is estimated by a surrogate adjusted on the previously evaluated points. This surrogate model, much faster to evaluate than the actual function, is optimized using the techniques basically available in LocalSolver.

The LocalSolver model presented here is implemented in Python. Each decision variable is an integer representing the number of units available for the current and future periods. There are as many variables as there are periods, and all variables are defined between 0 and the store’s capacity. With this definition, the first variable represents the number of units purchased at the beginning of the time horizon.

# Integer variables: available_units[i] is the number of units available for periods i to nb_periods
available_units = [model.int(0, capacity) for i in range(nb_periods)]

A black-box function is used to compute the total revenue, which is then maximized.

# The function compute_total_revenue takes an array of nb_periods integers as parameters and returns the mean revenue calculated
bb_function = model.create_double_blackbox_function(compute_total_revenue)
bb_call = model.call(bb_function)
bb_call.add_operands(available_units)

model.maximize(bb_call)

To ensure the model’s feasibility, each variable must be less than or equal to the previous one because the availability of units decreases over periods. Since version 10.0 of LocalSolver, it is possible to add analytical constraints to a black-box model as in a classical model.

for i in range(1, nb_periods):
    model.constraint(available_units[i] <= available_units[i-1])

Since the black-box function is computationally expensive, we define the maximum number of calls to this function beyond which the solver must stop its resolution.

bb_function.blackbox_context.evaluation_limit = evaluation_limit

We ran the problem with 3 periods on different evaluation limits and several seeds. No solution is known for this problem since the demand is stochastic, so to compare the results obtained by LocalSolver, we ran this problem with three other methods:

• NOMAD, an open-source black-box solver;
• RBFOpt, another open-source black-box solver;
• Random search, which randomly takes integers in the range and evaluates the function only if the constraints are satisfied.

All methods start from the same solution. Among all the runs, the best solution found is first obtained by LocalSolver. The mean absolute gap to this solution for different evaluation limits and all methods is presented in the table below.

Note that the two open-source solvers use a different approach than LocalSolver to handle analytical constraints. NOMAD considers these constraints as black-box ones and therefore does not use their structure. RBFOpt cannot handle any constraint, so a penalty is added to the objective function to ensure the solutions’ feasibility. The figure below shows the average objective value obtained in 10 runs as a function of the number of evaluations for each method.

You can find the complete model of the Revenue Management Problem in Python, Java, C#, and C++ in our Example Tour.

To demonstrate the surrogate modeling feature’s usefulness when the function is computationally expensive, we ran the same benchmark using external functions. External functions are basically called by LocalSolver, without using surrogate modeling, which is efficient enough for simple and fast functions. The figure below shows that using the black-box feature allows finding better solutions with fewer calls to the simulator.

We are at your disposal to accompany you in the discovery of LocalSolver. Just ask for your free trial license by registering here. In the meantime, don’t hesitate to contact us for any further information or support.