7
$\begingroup$

I have an integer programming problem with $L$ variables $x_1, x_2, x_{L}$ which all assume integer values and the following constraints must stand:

  • $x_i \geq 0$
  • $x_1 = 10$
  • $x_2 + x_3 + ... + x_{L} = 36$

how can I find the max and min of the following quantity?

  • $\displaystyle{\sum_{l = 1}^{L-1} x_{l}\,x_{l + 1}}$

My question is more oriented towards finding out the algorithm used to solve this problem that the exact number of max and min value but obviously if you can come up with an answer without using integer programming that is still more than welcome!

$\endgroup$
6
  • $\begingroup$ Must they all be positive, or else non-negative? $\endgroup$ Commented Nov 5, 2013 at 7:16
  • $\begingroup$ Wit the new condition $\large x_{i} \geq 0$, I have to check my answer. Also, I found a typo I have to check it. For the time being, I'll delete it. It will return tomorrow ( with the new condition ). $\endgroup$ Commented Nov 5, 2013 at 21:37
  • $\begingroup$ @FelixMarin - thanks for your help and availability! looking forward to the new answer ;D $\endgroup$ Commented Nov 6, 2013 at 2:13
  • $\begingroup$ The question has been edited a couple of times and my answer was to the original question. Initially you had the constraints X1+...+Xl-1 = 36 and x0=10. In the first constraint, if all took the values of 1, the minimum besides 0, then L-1=36, L = 37(including x0). If you included 0, then there are infinitely many is not so desirable and beats the purpose of the question. After looking at the answer,you will realize that it does not matter what the maximum value of L could be. The maximum of the objective function is always achieved with x0,x1,x2 taking the values of 10,23,13. $\endgroup$ Commented Nov 6, 2013 at 6:21
  • $\begingroup$ As far as setting up in EXCEL. give me your email address, I shall email it to you. $\endgroup$ Commented Nov 6, 2013 at 6:21

3 Answers 3

Reset to default
2
+50
$\begingroup$

When $L=2$, there is only one feasible solution and the unique minimiser/maximiser is $(x_1,x_2)=(10,36)$, which gives a function value $360$.

When $L\ge3$, the global minimum value is obvious: it is $0$ and a minimiser is given by $(x_1,x_2,x_3,x_4,\ldots,x_L)=(10,0,36,0,...,0)$. For global maximum, it is always true that $$ x_{k-3}x_{k-2} + x_{k-2}x_{k-1} + x_{k-1}x_k \le x_{k-3}(x_{k-2}+1) + (x_{k-2}+1)x_{k-1} + x_{k-1}(x_k-1) $$ for all $k\ge4$. Therefore we can always assume that $x_L=x_{L-1}=\cdots=x_4=0$. The objective function then becomes $10x_2+x_2(36-x_2)=x_2(46-x_2)$ and its maximum occurs when $x_2=\frac{46}{2}=23$ and $x_3=36-x_2=13$. Hence the maximum value is $529$.

$\endgroup$
2
$\begingroup$

If they don't need to be greater than 0, then you can use very large positive and negative numbers to either increase or decrease the sum as far as you like.
Suppose the numbers must all be greater than or equal to 0. To make the sum as low as possible, spread out the weight. Don't put two large numbers next to each other. To make it as large as possible, collect all the weight in just a few neighbouring $x_i$.

$\endgroup$
1
  • 1
    $\begingroup$ thks for the answer! I've updated my question, would you please mind being a little bit more specific about spreading out the weight? $\endgroup$ Commented Nov 5, 2013 at 20:13
2
$\begingroup$

Assuming that all are non-negative, the maximum value that L can take is 37(from x0 to x36). Any combination of these variables that could lead to a sum of 36 will amount to lagged sumproduct less than 529 ( which is the maximum). This happens with x0=10,x1=23,x2=13. Then for the same set of variables, x0=10,x1=0,x2=0, the minimum is 0. The problem will be different if you included negative values. You can set it up in EXCEL with the above logic and find the maximum, and minimum

$\endgroup$
1
  • 1
    $\begingroup$ Thanks for your answer! I'm not sure about a couple things, would you mind helping me to understand them better? Why do you say that maximum value of $L$ is 37 (consider that there are 36 variables and the first one $x_1$ is fixed)? And could you please explain how to solve the problem using excel? $\endgroup$ Commented Nov 5, 2013 at 20:16

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.