Optimizing a function to find the upper limit of a summation
AnsweredHi,
I am trying to minimize a summation function under a specific condition to give me the minimum upper limit of the summation that actually meets the condition.
For example:
if I have a list consists of numbers
list = [1,2,3,4,5,6,7,8,9,10,11,12,13,...etc]
And I have the function which is ∑list[x] where x starts from 1 to X,
I want to find minimum X that makes the function meets the condition ∑list[x] ≥ 55
for this example X should equal 10.
is there a way to write this function in a general way?
-
Official comment
-
Gurobi Staff
This post is more than three years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum. Or why not try our AI Gurobot?. -
-
-
Using Gurobi for this would be an overkill, as this can be answered in constant time (O(1)). Recall that the sum of the first n positive integers (starting from 1) is given by n*(n+1)/2. Let val be a parameter that specifies the requirement on the summation, so that:
∑list[n] = n*(n+1)/2 = 1/2*n^2 + 1/2*n ≥ Val
Then, we can get the answer to your problem by applying the positive part of the quadratic formula:
n = CEIL(-0.5 + SQRT(0.25 + 2*Val))
0 -
-
Thank you Juan for your answer.
The problem upthere was just an example as I am looking for an answer of such a problem where there is no relation between the numbers that you can get their summation to follow a formula. Do you think using Gurobi would be as expensive as enumeration?
0 -
-
-
If you can solve the problem by iterating through the list, tracking the cumulative sum of visited elements, and stopping once this sum is at least as large as some value \( k \), I would recommend doing that. Just building a model for Gurobi to solve would require at least as much time.
1 -
Post is closed for comments.
Comments
4 comments