Integer Programming problem

Question

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!

Answer 1

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$.

Answer 2

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$.

Answer 3

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