1
$\begingroup$

I am working on a marketing optimization problem, where the goal is maximize profit by optimally allocating spend to different products. Constraint is getting at least 1 Million revenue.

As a first step, I built a model to predict the revenue using XGboost (which I can use to calculate profit given spend). Now, how can I use this xgboost model as the objective function to optimize overall profit ( allocating spend across different products) given the constraint on revenue. What are some methods for this optimization ?

The Xgboost model uses about 6-7 variables like spend, target population, product, month etc.I came across linear programming for optimization but noticed LP uses linear objective function. I am newbie to optimization. I am not sure if I can/how to use xgboost model as objective function in Nonlinear optimization.

My XGBoost predicts revenue from log(spend), log(population), target encoded product variable, and average of revenue obtained 2 - 4 weeks ago revenue for the product (2 to 4 weeks because of business implementation constraints while predicting with the model). Now, what I am aim is to optimize the spend for a given product (hae about 60 products) that gives maximum profit.

$\endgroup$
3
  • 2
    $\begingroup$ You talk little about the actual structure of your model that predicts your objective. Is your decision tree a piecewise linear (or piece wise constant) functions over its input? Is it differentiable with regard to its inputs? This information will be essential for recommending an approach. Could you also please give us an example of the variables that go into the model and what you aim to optimize in mathematical terms? Thank you and welcome. We are not experts on ML but if you can translate what you have in our language we can help! $\endgroup$ Commented Oct 17, 2021 at 18:48
  • $\begingroup$ @worldsmithhelper Thank you very much for your response. I am not sure how to determine if the decision tree is piecewise linear or constant function over its input (XGboost is a group of some 100 decision trees). How would I determine if the xgboost model (aggregation of 100 trees) is differentiable with regard to the inputs ? $\endgroup$
    – tjt
    Commented Oct 17, 2021 at 23:11
  • $\begingroup$ Rather than using your XGboost predictor directly in the optimization model, you could perhaps try fitting surrogate functions (using your XGboost predictions) that map spend to revenue (also, profit) for every valid combination of product, geography & month. These could then be used in the objective function and constraints to define coefficients for the spend variables that are indexed by product, geography & month. $\endgroup$
    – Samarth
    Commented Oct 18, 2021 at 4:43

1 Answer 1

2
$\begingroup$

As the boosted trees are too complex to be modeled as an explicit mathematical function - unless maybe one is prepared to spend a tremendous amount of effort - such an objective would be considered a black box optimization problem.

An optimization problem is called "black box" when an explicit formula for the objective function is not known, and this function is often slow to evaluate.

You will find references in the question linked above. The usual methods are surrogate modeling - fitting a faster model to the function to run the optimization model - or if the function is not too slow a direct search with local search or genetic algorithm variants.

In practice, I suggest trying a simple local search first. If this is not sufficient, you may develop your own solution with response surface, but it gets complicated quickly. Some industrial solvers (LocalSolver, Knitro, ...) have support for black box functions and will often do a good job with it.

$\endgroup$
6
  • $\begingroup$ I find your answer a bit premature given how little we know about the objective function so far. $\endgroup$ Commented Oct 17, 2021 at 19:57
  • 1
    $\begingroup$ An Xgboost objective seems quite specific to me $\endgroup$
    – Ggouvine
    Commented Oct 17, 2021 at 20:11
  • $\begingroup$ Could you then elaborate why you think they are to complicated to be modeled as MILP in general? Given that you can solve for decision trees using MILP? proceedings.neurips.cc/paper/2020/file/1373b284bc381890049e92d324f56de0-Paper.pdf $\endgroup$ Commented Oct 17, 2021 at 20:15
  • $\begingroup$ Xgboost uses a very complex algorihm, not a single decision tree: multiple randomized trees, feature selection, etc. It is likely possible to model it as a MILP, but certainly not practical. Even before we think of solving this monster $\endgroup$
    – Ggouvine
    Commented Oct 17, 2021 at 20:34
  • 2
    $\begingroup$ You are right it is - and the underlying algorithm to generate them is irrelevant, contrary to what I implied earlier. To me, it seems extremely complex - both to extract it and to solve the resulting huge model - while I am used to using black box models in similar situations. If you see a practical way to extract the Xgboost trees and solve the resulting model, please post an answer about it - I would be really interested to read it. $\endgroup$
    – Ggouvine
    Commented Oct 17, 2021 at 20:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.