Linearity condition not satisfied with Solver when including binary variables

[kthedead]

Hi, I'm trying to model a stock selection portfolio using binary variables for the selection of stocks and the variables for weighing the stocks themselves, but Solver refuses to solve my model when i use the simplex method and pops out the error of 'linearity condition by this solver LP is not satisfied'. I tried nonlinear model like GRG but it generated illegal variables like '1' in stock selection but 0% weight.
The linearity report states that the weight variables and the objective function are not linear but I'm not sure how they aren't.

Would much appreciate any help regarding this problem. Attached is my worksheet with the linearity report.

[curiouscat408]

@kthedead.... I cannot say that I understand the Solver error, either. And I cannot offer a specific remedy. Sorry.

But I do have a couple observations....


1. You say that with the GRG Nonlinear method, the solution includes "illegal variables" like 1 in E10:N10 and 0% in corresponding E11:N11.

But I see nothing in your model that precludes that as part of the solution. In particular, the condition J34:J43 <= L33:L43 is met for each row.

Ostensibly, I think you need a condition that ensures that E11:N11 > 0 (not >=0) when corresponding E10:N10 is 1. But I do not know how to express that without an IF function, which is discontinuous.


2. On the other hand, it seems that having both binary values in E10:N10 and percentages >= 0% in E11:N11 is redundant -- and potentially contradictory.

For example, note that J20 can sum to 100%, but SUMPRODUCT(E10:N10, E11:N11) does not. In other words, J20 can include nonzero percentages that are not included in the portfolio.

At a minimum, I think the formula in J20 should be =SUMPRODUCT(E10:N10,E11:N11).

But that does not solve the non-linearity problem.

I wonder if it is sufficient to vary just E11:N11 without relying on the binary variables E10:N10.

But again, I don't know how to satisfy your other requirements (constraints) without discontinuous conditional functions like IF and COUNTIF.

EDIT: On the other hand, such conditional functions are no more "discontinuous" than the SUM functions that you use in J22:J32, for example.


3. Finally, I hope your efforts to understand the "non-linearity" error led you to the following resources. Frankly, they do not help me. But they might help you.

https://www.solver.com/excel-solver-...ot-satisfied-7

Section "Linear Functions" in the Solver User Guide, which I find using a Google search

-----

Again, sorry if none of this is helpful. And good luck!

[kthedead]

Wow, that's a much more detailed answer than I expected, I guess I'll have to pass over modelling this case with binary variables since I'm not an excel or math expert to solve this problem. Thanks a lot for your answer curiouscat :D

[curiouscat408]

Wow, that's a much more detailed answer than I expected, I guess I'll have to pass over modelling this case with binary variables

You're welcome. And yes, I think it can be modeled without binary variables.

However, when I tried that with the GRG Nonlinear method, it failed to find a solution.

(ERRATA: The following is wrong!) By the way, I think some of your constraint functions are incorrect. [...elided...]

I wish I could be more helpful. Hopefully, someone else will jump in with better guidance.

Be that as it may, I suspect that the problem is nonlinear. Consequently, Solver cannot guarantee that any "solution" is indeed "globally" maximum. Instead, at best, it might find a local maximum.

That is wild speculation. Just a head's-up to the possibility.

[Alf]

Perhaps something like this if I understood you setup properly.

Alf

[curiouscat408]

Perhaps something like this if I understood you setup properly.

I don't think so, for both clauses.

Your method finds the qualifying combination of 7 assets out of 10 that has the largest sum of individual returns, which is 10.1186675859166%.

(By "qualifying" I mean: the combination meets all the constraints in J22:J30 in kthedead's original file.)

That does not take weighting into account; that is, the percentage of the portfolio that is allocated to each asset.

If we assume equal weights (1/7), the portfolio return is 1.44552394084523%.

That is not the max portfolio return for that combination.

I believe the max is 1.93497303456631% if we assume a minimum allocation of 0.1% for all selected assets, but 99.4% for the selected asset with the largest return.

(An absurd allocation. But I believe it represents the max allocation for any combination, based on the arbitrary minimum.)

On the other hand, the portfolio return for that combination is 0.206413795901833% if we choose a minimum allocation of 0.1% for all selected assets, but 99.4% for the selected asset with the smallest return.

Thus, the combination that your method finds is not necessarily the qualifying combination with the max portfolio return, when weighting is taken into account.

(I'll have more to say about that in my next response to kthedead, time permitting.)

[curiouscat408]

Sorry for the incessant responses, but....

I guess I'll have to pass over modelling this case with binary variables

As I mentioned, I also believe that the binary variables are not necessary for a Solver solution for your example. I believe I have seen or helped people design similar Solver solutions without them. I wish I could find one of those solutions; it might even be in another forum. But I cannot. Sigh.

However, I think the binary variables might be necessary not so much for the Solver solution, but to distinguish an asset's zero return (albeit unlikely) from an unselected asset, which is also represented by a "zero return" in the calculations.

-----

Be that as it may, I suspect that you are missing some critical constraints in order to derive a reasonable solution -- that is, of course, if you ever resolve the problem with using Solver, which I still do not understand.

In particular, I think you want to specify minimum allocations, and perhaps also maximum allocations, either for each asset or at least for all assets.

In real-life portfolio management, we usually have a target asset allocation in order to meet certain objectives.

-----

The following might be TMI.

Without such additional constraints, I have been working with an alternative method of finding an optimal set of assets and weighting factors.

See the attached image and Excel file.

This is just a "proof of concept", not necessarily (nor likely) an approach to solving the problem, in general.

(Moreover, if you are working on a class assignment that requires a Solver solution, the following might be irrelevant and useless.)

It occurred to me that since you want exactly 7 assets in the solution, there are only 120 combinations of 7 out of 10 assets.

And there are even fewer qualifying combinations -- just 26(!) -- that meet the additional constraints in J22:J30 in your original file.

If we assume a minimum allocation for each selected asset (I chose 0.1% arbitrarily), we might assign the maximum remaining allocation to the selected asset(s) with the largest return.

If there is only one such asset, the maximum remaining allocation is 99.4% (1 - 0.1%*6).

Then the optimal portfolio return is the qualifying combination with the maximum weighted return.

(Of course, that is an absurd portfolio allocation in real life. But again, this is just a demonstration.)

-----

It is not difficult to design such a solution.

I used a VBA macro to derive the qualifying combinations, which are represented by the binary variables in columns R:AA starting in row 15.

Those binary variables are used to select asset returns from E4:N4 and put them into columns AB:AK.

The maximum return for each combination is calculated in column AL. The formula is not a simple MAX expression because the maximum might be negative, in which case zeros should be ignored, or it might be zero, in which zeros should not be ignored.

In columns AO:AX, the maximum weight (column AN) is assigned to each selected asset whose return matches the maximum return.

In your example, there is only one matching asset for each combination, despite appearances to the contrary, because your asset returns are calculated to the precision of 15 significant digits, although you display only 2 percentage decimal places.

And the arbitrary minimum weight is assigned to the remaining selected assets.

Finally, the weighted portfolio return is calculated in column AY, and the combination(s) that match the maximum weighted portfolio returns is flagged in column AZ.

In this example, there is only one maximum weighted portfolio return, based on the exact precision of the calculation in column AY, despite appearances of the values that display only 2 percentage decimal places.

-----

I think this approach finds the maximum "optimal" asset allocation, since it is based on an extreme and arbitrary weighting of the assets.

With very different (and "reasonable") weights, another qualifying combination might prove to be optimal.

If you provide tables of minimum and maximum allocations for each asset, I wonder if Solver can be used to find an optimal asset allocation among the 26 qualifying combinations.

On the other hand, I might be over-complicating the solution, and this might be a misdirection.

Hopefully, someone else will jump in with better guidance.


-----

[Hydraulics]

The linearity report states that the weight variables and the objective function are not linear but I'm not sure how they aren't.

You multiply a binary variable by a real variable in your objective function, and this makes the model non-linear. Substituting the formula in E15 with

=SUMPRODUCT(E11:N11,E4:N4)

and adding a new constraint to Solver

E11:N11 <= E10:N10

will make the model linear and force the weights to be 0 when a stock is not selected.

However, as noted by curiouscat408, there may be stocks that are selected (because of the multiple constraints) but have a weight of zero.
Since your problem is linear after all, once we have two stocks that must be included, but one has a higher return, we maximize the total by setting the weights as 0%-100%.

If this is not a sensible solution for you, we must quantify what you mean by "once a stock has been selected (to satisfy the constraints), at least a small percentage must be included", and then add a new constraint that will force the real vars to be >= min_perc when a stock is chosen.
I have already setup a model with a new parameter in a copy of your original file (you can set it to 0%). Changing it's value you should find the same values of curiouscat408.

HTH,

Francesco

[kthedead]

Thanks you so much Hydraulics and curiouscat, I actually arrived at Hydraulics's solution today after fiddling around a bit more with the constraints (i added the minimum weights per selected asset constriant) but didn't think of removing the binary variables from the objective function, after I did that the model became linear and I could solve it with Simplex.

Cheers.

[curiouscat408]

You multiply a binary variable by a real variable in your objective function, and this makes the model non-linear. Substituting the formula in E15 with
=SUMPRODUCT(E11:N11,E4:N4)

You are right, of course. But I still don't understand.

Adding the term E10:N10 to the SUMPRODUCT is merely redundant, since E11:N11 is zero whenever E10:N10 is zero, and E11:N11*E10:N10 = E11:N11, notably whenever E10:N10 is nonzero.

It does not change the results. And I am quite sure that Solver only relies on the results of the objective formula, not its syntax.

Yet there is no doubt that removing the term E10:N10 satisfies Solver's "linearity" (continuous function?) requirement.

Thanks for solving the mystery.

-----

we must quantify what you mean by "once a stock has been selected (to satisfy the constraints), at least a small percentage must be included"

I am curious: where do you find that quote being mentioned anywhere, much less by kthedead?

I cannot find it anywhere in this webpage or in the Excel file that kthedead provided. I must be dense!

-----

Changing it's value you should find the same values of curiouscat408.

I don't believe that is feasible, since my "maximum" optimal values are based on the absurd allocation of 99.4% for one asset and 0.1% for the other 6 assets.

I think the "take away" from my "proof of concept" is: the idea of "optimal" allocation is in the eye of the beholder.

[Hydraulics]

And I am quite sure that Solver only relies on the results of the objective formula, not its syntax.

The Solver engine translates internally the objective formula as you would do by hand, and then substitutes each var with a value, so the syntax does indeed matter.

I am curious: where do you find that quote being mentioned anywhere, much less by kthedead?

I was just following a train of thought.

I don't believe that is feasible, since my "maximum" optimal values are based on the absurd allocation of 99.4% for one asset and 0.1% for the other 6 assets.

It is feasible as long as the minimum threshold is the same for each stock, because I have introduced only one parameter in J45.
There is nothing absurd in a constraint that forces a variable to be either zero, or a positive value in an interval [a,+inf]. Many real situations require such a modelling.

HTH,

Francesco

[curiouscat408]

@Hydraulics.... Thanks for your responses.

-----

The Solver engine translates internally the objective formula as you would do by hand, and then substitutes each var with a value, so the syntax does indeed matter.

You state that as fact, not conjecture. So, how to you know that?

What I mean is: If you read that somewhere "authoritative" (e.g. at solver.com), please provide a link for my edification.

-----

I don't believe that is feasible, since my "maximum" optimal values are based on the absurd allocation of 99.4% for one asset and 0.1% for the other 6 assets.

It is feasible as long as the minimum threshold is the same for each stock, because I have introduced only one parameter in J45.
There is nothing absurd in a constraint that forces a variable to be [any particular value]

I think you misunderstood my comment.

First, I agree with you that it is reasonable to set limits on individual values.

In fact, I wrote: ``I think you want to specify minimum allocations, and perhaps also maximum allocations, either for each asset or at least for all assets.``.

What I was labeling as "absurd" are __my__ choices for those limits, very specifically 99.4% and 0.1% as I described them.

What I mean is: it is not a "reasonable" allocation, IMHO.

-----

Second, what I was labeling as "not feasible" is to achieve the specific weighted returns in my "proof of concept"; for example, 1.93497303456631% for the "1110101110" combination (#5).

What I mean is: it is not reasonable to expect unless you choose the 99.4%/0.1% allocation, which I consider to be "unreasonable".

-----

That said, perhaps it is __I__ who misunderstood the purpose of the exercise.

When kthedead wrote ``I'm trying to model a stock selection portfolio``, I thought he is looking for a practical portfolio.

But if kthedead is looking for the upper limit on the optimal portfolio return, I agree with you that it is feasible to do by choosing an appropriate minimum allocation.

In fact, referring to my "proof of concept", I wrote: ``this approach finds the maximum "optimal" asset allocation, since it is based on an extreme and arbitrary weighting of the assets``.

And to that end, I would suggest a minimum allocation of 0.01% (not 0.1%), since kthedead displays allocations with 2 percentage decimal places.

Then, Solver should find that the optimal portfolio return is combination #5 ("1110101110") with 99.94% (1 - 0.01%*6) assigned to the asset with the largest return (K4) and 0.01% assigned to the other selected assets.

(And of course, the minimum allocation can be much smaller, subject to the limitations of 15 significant digits or internal binary precision.)