Grouping Algorithm for Temperature Range [Revised]

Question

Note that this is a more detailed version of a previous, closed question.

I have a scenario where I have N items (N is a large number), and each item has a minimum allowable temperature (min_temp) and a maximum allowable temperature (max_temp).

I need to find a setpoint temperature that maximizes the number of items where that setpoint is between their min_temp and max_temp values. Ideally, it finds the value that also gives the greatest buffer between the setpoint and the closest min/max value of the compatible items (i.e. the safest setpoint in case of fluctuations).

A brute-force approach would be to loop through possible temperatures at a certain step size, such as:

float best_temp;
size_t best_num_items = 0;
for(float t = -60; t < 100; t += 0.1) {
    size_t num_items = 0;
    for(auto item: items) {
        if(t >= item.min_temp && t <= item.max_temp) {
            num_items++;
        }
    }
    if(num_items > best_num_items) {
        best_num_items = num_items;
        best_temp      = t;
    }
}

This would give me the best setpoint, but (a) it's obviously wildly inefficient, (b) it doesn't account for finding the value with the greatest buffer as detailed above, and (c) it negates all possible values that may be between step sizes.

Is there a non-brute-force approach that I should consider for this?

Answer 1

The problem of choosing a set point temperature between given minimum and maximum values that maximizes the number of items for which the chosen set point falls between each item's minimum and maximum value can be modelled as an integer linear programming problem and solved with an ILP software package.

The formulation of the model follows.

Data

• SP_l : minimum set point temperature

• SP_h : maximum set point temperature

• X_il : minimum temperature for item i

• X_ih : maximum temperature for item i

Variables

• sp : a continuous variable equal to the set point

• x_i : = 1 if item i is selected as part of the group; else = 0

Mixed integer program

max Σ_ix_i

subject to:

sp + (SP_h-X_ih)x_i ≤ SP_h for all i

-sp + (SP_l+X_il)x_i ≤ SP_l for all i

sp ≤ SP_h

-sp ≤ -SP_l

---

Note that the first two groups of constraints are derived from the following, respectively.

sp ≤ X_ihx_i + SP_h(1-x_i)

which reduces to:

sp ≤ X_ih if x_i = 1

sp ≤ SP_h if x_i = 0

Similarly,

sp ≥ X_ilx_i - SP_l(1-x_i)

which reduces to:

sp ≥ X_il if x_i = 1

sp ≥ SP_l if x_i = 0

---

See @havish's answer here for an example of using an ILP solver with Python.