2
$\begingroup$

Consider the notation and objective below for this sequential resource allocation problem:

Allocation channels $i \in (1, 2)$

Spend/Cost timestep i channel j: $C_{i, j}$

Total resource: $B$

Horizon: $H$

Max allocation jump between time-steps: $1.5$

Minimum allocation: $min\_total\_channel_i$

target ROI: $targetvalue$

planned spend over horizon: $P = (C_{1, 1}, C_{1, 2}.....C_{H, 1}, C_{H, 2})$

We have a time-variant predictor for the amount of sales on a specific day. For a certain timestep it takes the following form:

$sales_{i, j} = coeff_{i, j} * spend_{i, j}^{saturation_{{i, j}}}$

where as $i$ denotes the timestep and $j$ denotes the channel.

The following holds: $0 \le saturation_{i ,j} \le 1$ , notice that this curve exhibits diminishing marginal returns and is concave when minimizing thus convex when maximizing.

The total sales over the horizon can then be expressed as:

$totalsales(P) = \sum_{i}\sum_{j} coeff_{i, j} * spend_{i, j}^{saturation_{{i, j}}}$

The aim of this optimization task is to maximize the spend whilst maintaining a target ROI (return on investment). We also have some constraints we want our solution to adhere to such as minimum spend per channel, total budget constraint, max jump between the budgeting between one day and another.

We construct the following optimization problem:

\begin{align} \max_{C_{i, j}}\sum_{i}\sum_{j}C_{i, j} \\ s.t \sum_{i}\sum_{j} C_{i, j} &\le B \quad (Total-budget) \\ C_{i, j} & \ge 0.4 * C_{i - 1, j} \quad (Max-increment) \\ C_{i, j} & \ge 0.4 * C_{i + 1, j} \quad (Max-decrement) \\ \sum_{i}C_{i, j} & \ge min\_total\_spend\_channel_j \quad (Channel-budget) \\ \frac{totalsales(P)}{\sum_{i}\sum_{j}C_{i, j}} & \ge targetvalue \quad (ROI) \end{align}

This is a toy example and not the real-life example I am working on. In the real example, the sales predictor has a more complex functional shape looking like this:

$sales_{i} = \sum_{j}coeff_{i, j}*hill\_saturation (adstock(C_{i, j}))$

where as $adstock(C_{i, j}) = C_{i, j} + \lambda C_{i - 1, j}$ where $0 <= \lambda <= 1$

and

$hill\_saturation(C_{i, j}) = \frac{C_{i, j}^{\alpha}}{C_{i, j}^{\alpha} + \gamma^{\alpha}}$

Thus it exhibits a hill-type of function introducing all sorts of possible local minima. However, in the general case for my datasets, this function will be convex considering a maximization problem.

What I am wondering is if this is a good way of formulating this type of problem, particularly the formulation of the objective being maximizing the cost and putting the ROI objective as a constraint. I assume this could lead to some issues when picking up a solver. Maybe maximizing sales as an objective and keeping the constraint would be better.

I have been playing around with some python solvers without a good deal of luck(CPLEX doesn't work(DCP-violated), SLSQP and trust-constr gets stuck in local minima, and the random search takes ages. what would be a good solver for this type of problem - plus point for one with implementations that are free in python/API?

$\endgroup$
4
  • $\begingroup$ Perhaps a rigorous global optimization solver could be used. What is thew value of H for your "real" problem(s)? $\endgroup$ Feb 20, 2023 at 17:28
  • $\begingroup$ Write an AMPL or GAMS model and try out the bunch of solvers available on the NEOS server: neos-server.org/neos/solvers/index.html $\endgroup$ Feb 21, 2023 at 11:49
  • $\begingroup$ @Mark The maximum of H in my real problems is 31. $\endgroup$ Feb 24, 2023 at 7:45
  • 1
    $\begingroup$ @CharlieVanaret will do, thanks for the tip! $\endgroup$ Feb 24, 2023 at 7:45

1 Answer 1

2
$\begingroup$

Yes, there are quite a few good global NLP solvers. That would be my first thing to try out. (Always start experiments with the easiest/cheapest thing to do; do more complex things only when not happy yet).

Gurobi has a global quadratic solver. It is not too difficult to reformulate into a non-convex quadratic model. That would be another quick thing to try. (Note: something like $y=x^{2/3}$ can be written as $y\cdot y^2=x^2$.)

The nonlinearities are somewhat mild, so an alternative is to use a piecewise linear approximation. The resulting model is linear, I believe (after rearranging the last constraint in the model). That would also give global solutions.

Finally, we can discretize the $C_{i,j}$. That would give you additional solvers, such as Cplex CP solver, or OR-Tools CP-SAT tools. (Note: HillSaturation can be precomputed then, so the nonlinearity and con-convexity is gone. That would make things even linear.).

I can't imagine that all these approaches would fail terribly.

Note that math is confusing. E.g. $totalSales(P)$ does not depend on $P$ (or on $C_{i,j}$). Writing down a clean optimization model (in math) is also a good first step. A clean model allows better reasoning about it, so that is always a good idea.

$\endgroup$
1
  • $\begingroup$ great answer - accepted, thanks for your input.. will try the proposed techniques and update my question afterwards. Ill look into fixing the math aswell. $\endgroup$ Feb 24, 2023 at 7:46

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.