Finding the greatest sum of 10 integers with a given set of constraints.

Question

This is a problem that comes up often in my job. Not as transparently as this (it's not a heavily-math focused job, haha), but at a fundamental level it does, and I was wondering if it can be generalised in any way.

I'm not a very math-savvy person, so please bear with my phrasing of this like a textbook question:

You have a linear sequence of 10 spaces labelled A through J. Into each space you may place 1 and only 1 counter. You have 4 types of counter: four counters marked "2", three counters marked "3", two counters marked "4", and two counters marked "5". You may place counters into each space as you see fit, as long as you respect the following rule:

• A counter marked with $x$ cannot be placed within $x$ spaces of another counter marked with $x$.

For example, if a "2" counter is placed in space A, no "2" counters can be placed in spaces B or C. If a "2" counter is placed in space C, no "2" counters can be placed in spaces A, B, D, or E.

Finally, you are not required to place a counter in every space.

Given the above constraints, what is the greatest possible value for the sum of the numbers marked on the counters placed in spaces A through J?

---

Like I said, the problem in practice is not usually that transparent, so I'm more interested in whether the answer can be generalised in some way (like into a formula of some kind), or if it's too complex for that. Thank you for your time, and apologies in advance if I've mis-tagged this question.

Answer 1

You can solve the problem via integer linear programming as follows. Let binary decision variable $x_{sc}$ indicate whether space $s$ contains counter $c$. Let $u_c$ be the upper bound on the number of times counter $c$ can appear (for your example, $u_2=4, u_3=3, u_4=u_5=2$). The problem is to maximize $\sum_{s,c} c x_{sc}$ subject to linear constraints \begin{align} \sum_c x_{sc} &\le 1 &&\text{for all $s$} \tag1\label1\\ \sum_s x_{sc} &\le u_c &&\text{for all $c$} \tag2\label2\\ x_{sc} + x_{tc} &\le 1 &&\text{for all $c$, $s$, $t$ such that $s<t$ and $|s-t| \le c$} \tag3\label3 \end{align}

Constraint \eqref{1} assigns at most one counter per space. Constraint \eqref{2} enforces the upper bound for each counter. Constraint \eqref{3} prevents assigning the same counter to spaces that are too close together.

The maximum is $31$, attained as follows:

5 3 4 . 2 3 5 4 2 3

It turns out that there are $36$ such optimal solutions.

---

Here is the SAS code I used:

proc optmodel;
   /* declare parameters */
   set SPACES = 1..10;
   set COUNTERS = 2..5;
   num u {COUNTERS} = [4,3,2,2];

   /* declare variables */
   var X {SPACES, COUNTERS} binary;

   /* declare objective */
   max Z = sum {s in SPACES, c in COUNTERS} c * X[s,c];

   /* declare constraints */
   con AtMostOneCounter {s in SPACES}:
      sum {c in COUNTERS} X[s,c] <= 1;
   con Cardinality {c in COUNTERS}:
      sum {s in SPACES} X[s,c] <= u[c];
   con Conflict {c in COUNTERS, s in SPACES, t in SPACES: s < t and abs(s-t) <= c}:
      X[s,c] + X[t,c] <= 1;

   /* call MILP solver */
   solve;

   /* report solution */
   num sol {SPACES} init .;
   for {s in SPACES} do;
      for {c in COUNTERS: X[s,c].sol > 0.5} do;
         sol[s] = c;
         leave; 
      end;
   end;
   put sol[*];
quit;

Answer 2

Since you have $(11)$ counters total, and $(10)$ spaces, the best that you can do is to use $(10)$ of the counters, if possible. So, you have two simultaneous goals to strive for:

• Maximize the number of counters used, attempting to use $(10)$ of the $(11)$ counters.

• Minimize the omitted counter(s). For example, if you can use $(10)$ of the counters, with a $(2)$ omitted, that is automatically an optimal solution.

Consider the partial sequence:
$54----54--.$

One way of continuing this sequence is:

$$5423-25423. \tag1 $$

Omitted numbers in (1) above: one $(2)$, one $(3)$.

Because of the sequence in (1) above, in striving for a better sequence, you can automatically assume that both $(5)$'s must be used. The defect of the sequence in (1) above is that the leading $(54)$ specifically occupied positions A and B. However, this was balanced by the other $(54)$ occupying positions G and H.

So, the next try is:
$-54----54-.$

My instinct is to extend this to:

$$354-3--543 \tag2 .$$

This leads to:

$$35423-2543. \tag3 $$

Omitted numbers in (3) above: two $(2)$'s.

Absent brute force, I suspect that this is optimal. However, I also suspect that actually proving it analytically may be very cumbersome.

In (2) above, the difficulty in reversing the order of the first $54$ in the sequence, so that the second $(4)$ may be placed in position G, instead of position I, is that it makes the two $(5)$'s too close together.

Answer 3

In its current form / extent, the problem is small enough to be "solved" by brute-force. There are 5 possible values to be placed in an array of length 10, which are $5^{10}\approx 10^7$ settings, only $\approx 150\,000$ of which are legal due to the constraints.

As language I chose C99 because it executes swiftly and no high-level algorithms or data structures are needed. The only advantage over Linear Programming etc. is that a C-compiler is usually more accessible. For example, the code below can be compiled using gcc or clang which produces executable count.x:

gcc -std=c99 count.c -o count.x -O3

The program iterates over all solutions, but only prints a solution when its score is higher than that of all previos solutions. It will print

sol: [ 5 4 3 2 0 0 5 4 3 2 ] = 28
sol: [ 5 4 2 3 0 2 5 4 3 2 ] = 30
sol: [ 5 3 4 2 0 3 5 4 2 3 ] = 31

Execution time is in the order of milliseconds. One critical value is the size of the array, N_VALUES in the code. When set to 17, the execution time will already grow to some seconds, and it will increase exponentially with N_VALUES.

#include <stdio.h>
#include <stdbool.h>

#define ARRAY_SIZE(X) ((int) (sizeof (X) / sizeof (*X)))

#define EMPTY 0

#define N_VALUES 10

int value[N_VALUES];

typedef struct
{
    // Multiplicity of this item.
    int count;

    // Value and range of this item.
    const int value;
} item_t;

// What items we have available to fill value[] with.
item_t item[] =
{
    // List items with a high .value first.
    { 2, 5 },
    { 2, 4 },
    { 3, 3 },
    { 4, 2 },
    { 0, EMPTY }
};

static const int N_ITEMS = ARRAY_SIZE (item);

int max_score = -1;

static inline int min (int a, int b) { return a < b ? a : b; }

// Try to set value[v] = item[i].value.
static bool set (int v, int i)
{
    const int ival = item[i].value;

    if (ival != EMPTY)
    {
        // Are there still instances of this item available?
        if (item[i].count == 0)
            return false; // ...no.

        // Check neighborhood for same items.  As search works from value[0]
        // up to value[N_VALUES - 1], only check values to the left.
        for (int i = min (ival, v); i >= 1; --i)
            if (value[v - i] == ival)
                return false;

        // No same items in neighborhood: Register this item.
        item[i].count -= 1;
    }

    value[v] = ival;

    return true;
}

// Undo effect of set().
static void unset (int v, int i)
{
    if (item[i].value != EMPTY)
        item[i].count += 1;
}

// Score is sum over value[].
static int score (void)
{
    int sum = 0;
    for (int v = 0; v < N_VALUES; ++v)
        sum += value[v];
    return sum;
}

static void do_solution (void)
{
    const int sc = score();

    // Only print solution if it performs better than all solutions
    // seen so far.

    if (sc <= max_score)
        return;

    max_score = sc;

    printf ("sol: [");
    for (int v = 0; v < N_VALUES; ++v)
        printf (" %d", value[v]);

    printf (" ] = %d\n", sc);
}

// Iterate value[v] over available items.
static void do_search (int v)
{
    if (v == N_VALUES)
    {
        // value[] is completely set and contains a legal solution.
        do_solution();
        return;
    }

    for (int i = 0; i < N_ITEMS; ++i)
    {
        if (set (v, i))
        {
            // Setting value[v] = item[i].value was successful. Now try to
            // set value[v+1] etc. until all of value[] is set.
            do_search (v + 1);
            // Undo effect of set (v, i).
            unset (v, i);
        }
    }
}

int main()
{
    do_search (0);

    return 0;
}