6
$\begingroup$

EDIT #2 5/17/2020: I re-phrased my question once more. My original question is still at the end. Thanks for the feedback.

I want to know if it's possible to maximize the sum of cumulative distribution functions for independent normal distributions in Excel using OpenSolver.

$$\text{maximize } \Phi(\sum_i x_ip_i) + \Phi(\sum_i x_iq_i)$$ $$\text{ s.t.} \sum_ix_i=3 $$ $$x_i=1 \text{ or } 0$$

where $\Phi(\cdot)$ is the standard normal cdf (or NORM.DIST in Excel).

ORIGINAL:

Here is a snapshot of the workbook: https://i.stack.imgur.com/QqIKC.jpg

Here are the formulas: https://i.stack.imgur.com/4x6X0.jpg

I'd like to maximize a cell that is the sum of other cells that are not linear. I have Z scores for categories I and II (I hardcoded in a mean of 30, and stdev of 15 for category I and 40 and 20 for category II).

I want to maximize the sum of their normdist values in Row 13 (G13 and H13). Clearly, solver won't find a linear solution since the normdist function isn't linear. I have heard there was a way to get around this by doing piecewise-linear approximation.

Other notes:

  • Columns B and C contains raw data - no formulas
  • Column E is made up of 1s and 0s that are the variable cells determined by Solver
  • G2:H6 will return the raw data found in columns B and C if column E displays a 1
  • The sum of E2:E6 must equal 3
  • This is very scaled down from the real problem I'm trying to solve, so no brute force methods will suffice.
Improve this question
$\endgroup$
2
  • 3
    $\begingroup$ Welcome to OR.SE. Is there any mathematical formulation on your problem? $\endgroup$
    – A.Omidi
    Apr 16, 2020 at 10:01
  • $\begingroup$ It would help if you put the images directly into your post, so that we don't have to click on external links to view them. Also, as @A.Omidi said, please provide a mathematical (algebraic) formulation of your problem, using MathJax. Thanks! $\endgroup$
    – LarrySnyder610
    Apr 16, 2020 at 12:43

2 Answers 2

Reset to default
5
$\begingroup$

You can approximate any nonlinear function via a piecewise-linear function using binary variables (or, if your solver supports them, type 2 special ordered sets). I have an old blog post explaining how to do this with SOS2. As to how accurate it is, your mileage will vary.

The version of Solver in Excel is fairly limited. You might want to consider the OpenSolver or SolverStudio add-ins for Excel (both open source), which can handle larger models and tend to be more powerful. At least some of the solvers they support can handle SOS2 constraints, but I don't know if their interfaces have provisions for specifying SOS2. If not, you could definitely fall back to using binary variables.

Improve this answer
$\endgroup$
1
$\begingroup$

NOTE: This answer was written to respond to an earlier version of the question, which used a different form of the objective function. This answer is incorrect for the new version but I’m leaving it here in case it’s useful to anyone.

I think this problem can be reformulated in a much simpler way. You are trying to

$$\text{maximize} \quad \sum_i \left[ \Phi\left(\frac{x_ip_i-30}{15}\right) + \Phi\left(\frac{x_iq_i-40}{20}\right)\right] $$

where $\Phi(\cdot)$ is the standard normal cdf (or NORM.DIST in Excel).

Why not just calculate these terms for each $i$ and then use the result as the coefficients for $x_i$? What I mean is, let

$$a_i = \Phi\left(\frac{p_i-30}{15}\right)+ \Phi\left(\frac{q_i-40}{20}\right).$$

Then your objective function is just

$$\text{maximize} \quad \sum_i a_ix_i$$

and the constraints remain as you formulated them originally.

Note that this approach only works because the $x_i$ are binary. If they were continuous (or general integer, for that matter) it would not work.

Improve this answer
$\endgroup$
14
  • $\begingroup$ Hi Larry, I am indeed trying to evaluate the Φ of the sum of each i's values for $p_i$ and $q_i$, not the sum of individual Φ functions. Therefore calculating Φ can't come until we've selected 3 $x_i$ values. And then on top of that we want to maximize the sum of two Φ functions. $\endgroup$
    – Jack Ries
    May 8, 2020 at 3:04
  • $\begingroup$ Your formulation says you want to max $\sum_i \Phi(x_i)$ but it sounds like you're saying you actually want to max $\Phi\left(\sum_i x_i\right)$? (I'm omitting coefficients.) $\endgroup$
    – LarrySnyder610
    May 8, 2020 at 12:56
  • $\begingroup$ I think I mis-read your original question of "Why not just calculate these terms for each i and then use the result as the coefficients for $x_i$?" It's because this is a simplified model for a much larger problem where pre-calculating the terms would be unfeasible for how many combinations would need calculating. I'm hoping I can avoid that route. $\endgroup$
    – Jack Ries
    May 11, 2020 at 3:13
  • $\begingroup$ As your question is currently written, my suggestion does not require you to pre-calculate terms for combinations of variables, only one per variable. $\endgroup$
    – LarrySnyder610
    May 11, 2020 at 3:40
  • $\begingroup$ Or do you mean that the $x_i$ themselves are really more complicated terms, but you simplified them to $x_i$ for your question? $\endgroup$
    – LarrySnyder610
    May 11, 2020 at 3:41

Your Answer

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

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