1
$\begingroup$

Ok so we have set of $n$ random numbers $a_1,a_2,...,a_n$ where $a_i \in \Re$ and and we want to find the subset with the maximum sum (example 3,-2.5, 2, 6, 1,-10 max subset is: $a_3,a_4,a_5$ etc).I want to create an integer linear program that describes this problem. My idea so far is this:

Objective function : $max\sum_1^nx_ia_i$

subject to: $x_i\in(0,1)$ ($x_i$ represents if $a_i$ will be part of the maximum subset)

but i simply can't find a way to create a constrain about numbers being consecutive ..

$\endgroup$
7
  • $\begingroup$ It´s not very kindful to delete a question without giving a reply. $\endgroup$
    – callculus
    Mar 11 '18 at 18:11
  • $\begingroup$ i deleted the question because it was asked the wrong way, now i have asked it the right way. sorry for deleting the last question. Any help you can provide here would be much appreciated! $\endgroup$ Mar 11 '18 at 18:13
  • $\begingroup$ How large large is the subset? $\endgroup$
    – callculus
    Mar 11 '18 at 18:16
  • $\begingroup$ we cant know that, could be a single $a_i$ or it could be all the numbers , thats what we are trying to find $\endgroup$ Mar 11 '18 at 18:18
  • 1
    $\begingroup$ What is the constraint about consecutive numbers? I don't see anything about that in the problem statement. Also, why can't you just take all the positive $a_i?$ You must have left out part of the problem statement. $\endgroup$
    – saulspatz
    Mar 11 '18 at 18:18
2
$\begingroup$

I'm going to assume that you are looking for a selection of consecutive values. There are multiple ways to model this, including the following. Start with binary variables $s_i\in\{0,1\}$ and $e_i\in\{0,1\}$ for $i=1,\dots,n$. $s_i$ signals the start of the selection and $e_i$ signals the end. Add the constraints$$\sum_{i=1}^n s_i=1$$and$$\sum_{i=1}^n e_i=1$$to ensure a single start and end to the sequence. Next, mainly for convenience, we'll introduce some (continuous) auxiliary variables:$$y_i=\sum_{j=1}^i s_j$$and$$z_i=\sum_{j=i}^n e_j.$$ They also help with sparsity of the constraint matrix. Finally, we introduce continuous variables $x_i\in [0,1],\, i=1,\dots,n$, signaling whether a term is in the selection. The objective is, as you wrote, $\sum_{i=1}^n a_i x_i$.

Now we need to add constraints to make sure the $x$ variables contain a single contiguous block of ones. Those constraints are:$$x_i \le y_i\, \forall i,$$$$x_i \le z_i\, \forall i,$$and$$x_i \ge y_i + z_i - 1\, \forall i.$$The first two constraints say that, in order for $x_i$ to be positive, the block must start at or before position $i$ and end at or after position $i$. The final constraint says that if both those things happen, $x_i$ must be 1 (cannot be 0).

$\endgroup$
2
$\begingroup$

This can be easily done with an efficient implementation of a complete enumeration.

First compute $A_n = \sum_{i \le n} a_i$ for all $n$. Also set $A_0 = 0$. To find the subset of $m$ consecutive numbers that have the largest sum, determine the maximum of the quantities $C_k = A_{k+m} - A_k$ for $k = 0, \dots, n-m$.

The overall computational effort is $O(n)$.

It's easy to modify this so that it also works in an online mode (if the $a_i$ arrived one at a time).

$\endgroup$

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.