0
$\begingroup$

I am trying to find all the combination of options trades that make the highest profit. Each trade has a maximum profit and maximum loss. I have a list of maximum losses e.g. [5298, 1100, 500]. Each number corresponds to a trade. The combination of maximum losses must be under the money I have in my account, for example, 9000. I'm trying to subtract each number in the maximum loss array from the money in my account and repeatimg it until it gets to 0 or a negative number. It then advances to the next number. This will miss many combinations because it doesn't try the first AND second AND third at the same time. Does anyone know of an algorithm or know how to find and algorithm to find such combinations or have a better idea than mine? This is the pseudocode I have come up with:

for loop through max loss array
find difference between moneyInAccount and max loss[0]
if difference > maxLoss[0] then
difference = difference - maxLoss[0]
or else index to next maxLoss
if maxLoss[1] > difference
then difference - difference - maxLoss[1]
and so on
Improve this question
$\endgroup$
4
  • $\begingroup$ Welcome to Computer Science! This looks like a nice problem. Can you raise a specific question for people to answer instead of asking people to do something? (Trivia: one question mark is required.) Can you show a simple non-trivial example? If this problem comes from an online source such as a programming contest or coding camp, can you provide a URL? If it comes from a book or a paper, a reference? All those information motivate and help people answer the question faster and better. Please add those information in the question since people and search engine are not expected to look at comments. $\endgroup$
    – John L.
    Oct 11, 2018 at 21:11
  • $\begingroup$ Can you state your problem more formally? $\endgroup$
    – Yuval Filmus
    Oct 11, 2018 at 21:58
  • $\begingroup$ I edited it, but I don't know how formal it is. $\endgroup$
    – J Borchonne
    Oct 12, 2018 at 3:02
  • $\begingroup$ Searching for "find all combinations" yields dozens of results. That should show you two things: a) you might have found your answer searching; b) your title is not very helpful. $\endgroup$
    – Raphael ♦
    Oct 12, 2018 at 11:43

1 Answer 1

Reset to default
1
$\begingroup$

This might be a bit advanced for your level (I'm not sure where you're coming from), but this is technically a Knapsack problem. If you're unfamiliar, I suggest first reading a bit from Wiki: https://en.wikipedia.org/wiki/Knapsack_problem

Each of your options has a maximum loss, and some value to you. (I'm not quite sure what your value function here is -- is it the maximum profit? Or maybe $(max\,\,profit - max\,\,loss)/2$?) You have a cap on how much loss you'll assume as risk: your available money. Given that cap, you want to maximize your value.

If you think of the Knapsack as carrying options, then you have a "weight" on each option that is its maximum loss, and your max "weight" you bear is the money you have to risk. You want to maximize the value of your knapsack.

Now, the Knapsack problem is in general NP-hard: this means that no one has a solution to always find the true optimum quickly, and it's unlikely there ever will be. But, there are algorithms that do extremely well for most problems, or give approximate solutions. The Wikipedia article discusses a few.

From a practical perspective, one of the best options is running this as an "Integer Linear Programming" problem, or ILP. Writing your own ILP solver is hard, but there are good software libraries for it. There are also lots of tutorials online about tackling stock portfolio problems with ILP libraries. For instance, a minute of googling "Integer linear progrmaming stock option" took me to https://www.mathworks.com/help/optim/ug/maximize-long-term-investments-using-linear-programming.html, which talks about doing it in MATLAB. You can find many more, probably for Python and Java and R, to name a few likely candidates.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you very much. "Combinatorial optimization" is just what I need. I would have never have searched for that term on my own. $\endgroup$
    – J Borchonne
    Oct 13, 2018 at 2:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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