# Integer Programming problem

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!

• Must they all be positive, or else non-negative? – Empy2 Nov 5 '13 at 7:16
• 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 ). – Felix Marin Nov 5 '13 at 21:37
• @FelixMarin - thanks for your help and availability! looking forward to the new answer ;D – Matteo Nov 6 '13 at 2:13
• 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. – Satish Ramanathan Nov 6 '13 at 6:21

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$.
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$.
• 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? – Matteo Nov 5 '13 at 20:16