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$ Commented Mar 11, 2018 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$ Commented Mar 11, 2018 at 18:13
  • $\begingroup$ How large large is the subset? $\endgroup$ Commented Mar 11, 2018 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$ Commented Mar 11, 2018 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
    Commented Mar 11, 2018 at 18:18

2 Answers 2

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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .