2
$\begingroup$

I'm trying to solve a very practical optimization problem and I think I hit a dead-end.

There are $N$ products ($N \sim 50$). Each product can have a price $p_i$ in range between 1 and 40 dollars. For each product there's a non-decreasing demand function $d_i(p)$, $a > b \Rightarrow d(a) >= d(b)$. Demand functions are produced by running Monte-Carlo simulations, represented by a table and from the look of it cannot be easily approximated by something analytical and differentiable.

Total cost of all products is what is being maximized.

$\max \sum_{i} p_i d_i(p_i)$

There's only one constraint, it's a non-linear constraint on average price:

$\frac{\sum_{i} p_i d_i(p_i))}{\sum_{i} v_i d_i(p_i)} \le C$

where $v_i$ is a constant specified in advance for each product.

Any suggestions? I tried some heuristics, but results are highly unstable. Small change in $C$ leads to very different results.

Any help would be highly appreciated.

$\endgroup$
2
  • $\begingroup$ What would constitute a "solution" for you? Do you want some method with some type of performance guarantee (hard if you can't tell us anything about the form of the $d_i$)? Or suggestions for other heuristics? Without knowing more, the question is not clearly appropriate for this site. $\endgroup$
    – Noah Stein
    Mar 8, 2013 at 22:12
  • $\begingroup$ Not much to tell about $d_i$, unfortunately. Monotonically non-decreasing, not necessarily convex. Any suggestions are welcome, even for other heuristics. I was wondering if that was the question for MathOverflow. Would highly appreciate if someone sends me in a right direction as well. $\endgroup$
    – Eugene
    Mar 8, 2013 at 22:48

1 Answer 1

0
$\begingroup$

I would recommend first thinking carefully about the trivial case $N=1$ and the nontrivial case $N=2$.

For $N=1$, the constraint is simply $pd(p) \le Cvd(p)$, so it's pretty clear that you'll maximize $pd(p)$ when $p=Cv$ (since $d$ is non-decreasing).

For $N=2$, the constraint is

$$pd_1(p) + qd_2(q) \le Cv_1d_1(p)+Cv_2d_2(q).$$

(I'm writing $p$ and $q$ for $p_1$ and $p_2$ here, to reduce the number of subscripts.) Now let $p=Cv_1+x$ and $q=Cv_2-y$. The constraint boils down to one relating $x$ and $y$:

$$xd_1(Cv_1+x) \le yd_2(Cv_2-y).$$

Given that the demand functions $d_1$ and $d_2$ are unspecified (beyond being non-decreasing), I don't see how you can hope to say much about where the max is achieved. But maybe I'm missing something.

$\endgroup$
1
  • $\begingroup$ Here's one example of what the demand function might look like: imgur.com/FFklmWW As you can see, that's pretty irregular. Clearly, there has to be some kind of a search algorithm involved. Maybe starting with $Cv_i$ price vector and searching around that point. I guess the question is how to make this search efficient. $\endgroup$
    – Eugene
    Mar 8, 2013 at 23:19

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.