How we managed to speed up the solution of the NBO optimization problem at Alfa-Bank by 100 times

In this article we, Advanced Analytics GlowBytewe will tell you how we managed to speed up the solution of the NBO problem on the open source CBC solver by about 100 times and achieve an increase in the optimal value of the objective function by 0.5%.

Introduction

The task of NBO in our case is to draw up an optimal communication plan with the client base for the next week in various channels (call, SMS, etc.). We talked in more detail about setting such a task and its solution in the article and at the seminar in our NoML community.

Let us briefly recall the meaning of the problem and its mathematical formulation. We have a database of N bank clients. We want to offer them certain products – a loan, a deposit, etc. To do this, we can contact them through certain channels: we can call, send an SMS, etc. Let's say that for each client we have estimated the probability of this client's response to the offer of this product through this channel. By response we mean the discovery of the product by the client within a certain time after we offer this product to the client. We want to draw up a communications plan for the week, i.e. answer the question of which clients, which products through which channels to offer in order to maximize the expected number of responses, and to meet a number of business requirements:

  • you can communicate with a client no more than once;

  • customers may have prohibited products or channels through which communication is not allowed

  • There are limits on the total number of communications for product-channel pairs.

This problem can be formulated as an integer linear problem

programming:

\begin{equation*}\begin{array}{ll@{}ll}\text{maximize} & \displaystyle\sum\limits_{i}\displaystyle\sum\limits_{g \in G_{i}} C_{ i,g}\ x_{i,g} \\\text{subject to} & \displaystyle\sum\limits_{g \in G_{i}} x_{i,g} <= 1, & \quad \forall i\\ & m_{g} <= \displaystyle\sum\limits_{i: g \in G_{i}} x_{i,g} <= M_{g}, & \quad \forall g\\ & x_ {i,g} \in \{0, 1\}, & \quad \forall i,\ \forall g \in G_{i}\\\end{array}\end{equation*}

i — client index.

g — index of the product-channel pair. Further, the product-channel pair will be called a callgroup.

x_{i,g} — variables of the task. They are binary if x_{i,g} = 1,then with the client i need to contact via call group g.If x_{i,g} = 0, that is unnecessary.

C_{i,g}— probability of customer response i for communication via a channel corresponding to the call group g.

G_{i} — a set of callgroup indices g, through which you can communicate with the client i.

m_g, M_g — min. and max. permissible volume of communications (capacity) for a call group g.

Next, using any solver to solve such problems, we will get an optimal communications plan that meets our requirements. In our case, the solver is used CBC.

Difficulties and their current solutions

The number of clients for whom we want to create communication plans is tens of millions. The number of variables and constraints in the optimization problem is hundreds of millions. At this size, this problem takes a day and a half to solve, which is too long. We have a time requirement for solving the problem – about 20 minutes.

To solve this problem, the following approximation was made. The entire client base was divided into small groups – chunks. For each chunk, the same optimization task was set as described in the previous section, only m_g And M_g are divided by the number of chunks. Then the problems are solved separately.

m_{g} = \frac{m_g^{total}}{N_{chunks}}, \quad M_{g} = \frac{M_g^{total}}{N_{chunks}},

N_{chunks}— the number of chunks.m_g, M_g — min. and max. capacity for a call group g for one chunk. m_g^{total}, M_g^{total} – min. and max. capacity for a call group g for the entire customer base.

Many “small” problems are solved faster than one large one, since the time it takes to solve a problem increases nonlinearly with the number of variables. In addition, by breaking a large problem into many smaller ones, we can parallelize the process and significantly speed up the calculations. However, such acceleration has its price: there is a risk of getting a non-optimal communications plan. Breaking up a problem imposes separate restrictions on the number of communications within each subtask, which may be stricter than in the original task. This leads to the fact that some feasible solutions, including optimal ones, may be missed. As a result, the final communications plan, compiled on the basis of subtask solutions, may be suboptimal.

The goal of our experiment is to increase the size of chunks (subtasks), thereby reducing their number, and evaluate how this will affect the growth of the objective function. It is important that the solution time does not increase. The main challenge is to optimize the solution time. Therefore, before increasing the size of chunks, we must speed up the problem solving process.

Editing CBC settings

Changing the settings gave a significant speed boost on our task. Below are the settings we overridden and an explanation of why we did it.

preprocess=off. This setting disables the task transformations related to integer conditions. These transformations are optional, their purpose is to speed up the task solution. In our task, these transformations are of little use, and they take a lot of time. In the end, disabling preprocessing turns out to be more profitable.

hear=off, rens=on. This pair of settings tells CBC to use only one heuristic – RENS. In our problem, relaxation immediately finds an integer solution. But CBC still spends time calling heuristics. So we leave only one, which works quickly. In principle, it was possible to disable heuristics altogether, but this does not make a difference in time. We left one heuristic just in case.

zero=off. This setting disables one of the cutoff methods. In our task, this is not necessary, because we find a good solution without them. But this method takes a noticeable amount of time.

presolve=off. This setting disables general task transformations (not necessarily related to integers). Their purpose is to simplify the task statement with equivalent transformations. For example, to reduce the number of variables or constraints. It is difficult to predict for sure how this will affect the further course of the solution, but usually reducing the size of the task speeds up the solution. However, in our task, presolve does not help. Without it, the task is solved much faster

slog=0. This disables some logs that we are not interested in. We do this to avoid cluttering the logs in Airflow. This does not affect performance.

Overriding Pyomo's CBC call

Pyomo — is a Python library for setting optimization problems. This section describes some steps that had to be taken to get around a couple of problems with CBC and Pyomo. This resulted in a significant speedup.

Pyomo always calls CBC with the setting -stat=1which tells it to collect statistics about the task and write it to the log. We don't need this, because it doesn't affect the solution in any way. In our case, collecting these statistics takes much more time than the solution itself. There is no option in the Pyomo interface not to pass this setting. We reported this in github repo Pyomo. The authors agreed to take this into work, but it is unknown when this will be done. In the meantime, we made a hack so as not to transfer this setting to CBC.

Usually, to solve a problem in CBC, its command is used solve. When Pyomo calls CBC it uses this. We noticed that the setting presolve=off has no effect if you call this command. But if instead solve use two consecutive CBC commands – initialSolve, branchesthen the setting has an effect. In essence, these two commands do the same thing as one command solve. Apparently CBC has a problem with applying this setting from the command solve. In order to apply presolve=off setup, we made a hack so that Pyomo would use a couple of commands when calling CBC initialSolve, branch instead of solve.

We introduce auxiliary variables into the problem

The following approach gave a significant acceleration when increasing the chunk size. We introduce new variables as sums of the original variables x with the same coefficients of the objective function and the same collage. And we will rewrite the objective function and capacity constraints through these variables. We will make up a set of unique coefficients of the objective function in the problem and number them with an index p.

\begin{equation*} \begin{array}{ll@{}ll} \text{maximize} & \displaystyle\sum\limits_{p,g} C_{p}\ n_{p,g} \\ \text {subject to} & \displaystyle\sum\limits_{g \in G_{i}} x_{i,g} <= 1, & \quad \forall i\\ & m_{g} <= \displaystyle\sum\ limits_{p} n_{p,g} <= M_{g}, \quad \forall g\\ & n_{p,g} = \sum\limits_{i: C_{i,g}=C_{p} } x_{i,g}, & \quad \forall p, \forall g\\ & x_{i,g} \in \{0, 1\}, & \quad \forall i,\ \forall g \in G_{i}\\ \end{array} \end{equation*}

p — index of the unique coefficient of the objective function.

C_{p} — unique values ​​of coefficients C_{i,g}.

The remaining notations are the same as in the original problem.

Results

We compared the time it took to solve the problem before and after the changes. We tried different chunk sizes and measured the relative speed gain. The result is shown in the graph below.

Fig 1. The size of chunks (subtasks) is plotted along the x-axis. Meaning "chunk size = 1" — this is the original chunking (which was used before our changes). It is equal to 30. The value "chunk size = 3" — increasing the chunk size by 3 times, i.e. we have 10 chunks for the same client base. The time for calculating the client base was measured. The chunks were counted sequentially.

Fig. 1. The size of chunks (subtasks) is plotted along the x-axis. The value “chunk size = 1” is the original split into chunks (used before our changes). It is 30. The value “chunk size = 3” is a three-fold increase in the chunk size, i.e. we have 10 chunks for the same client base. The time for calculating the client base was measured. The chunks were calculated sequentially.

As you can see, the larger the task size, the greater the speedup. We achieved speedups of up to 80x.

Now that we have managed to speed up the process significantly, we can solve larger subproblems in the same amount of time. This allows us to increase the size of the chunks (reduce the number of subproblems) into which the original problem is divided. The question is how much does it make sense to increase the size? To answer this question, we measured the growth of the objective function with increasing chunk size (Figure 2).

Fig. 2. The graph shows how much the objective function increases with increasing chunk size (decreasing the number of subtasks). The meaning of the x-axis is the same as in Fig. 1.

Fig. 2. The graph shows how much the objective function increases with increasing chunk size (decreasing the number of subtasks). The meaning of the x-axis is the same as in Fig. 1.

The gain was measured relative to the partition into 150 subproblems (the point with “chunk size=1”), so for this point the gain is zero. The maximum gain was about 0.5%. Increasing the chunk size by more than 30 times does not provide a significant gain. However, the solution time increases significantly with the increase in chunk size. Therefore, we stopped at increasing the chunk size by 30 times, which corresponds to reducing their number from 150 to 5.

The article was written by @Lazarev_Adrian@anikonorov@vagonoff

P.S. We talked about how we speed up optimization open source solvers on one of the seminars our community NoML.

Similar Posts

Leave a Reply

Your email address will not be published. Required fields are marked *