Formulation of nonlinear nonconvex optimization problem and finding appropiate solver

Question

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?

Answer 1

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.