Hey there, let's work through how to add that linear constraint you need for your binary price selection problem. You've got binary decision variables DV₁ to DV₁₀ (each marking whether you pick the $i price point), already have the ΣDVᵢ ≤ 4 limit on selections, and now need to make sure the gap between the highest and lowest chosen prices doesn't exceed a variable value M (from your input cell). No nonlinear functions like MAX(), MIN(), or IF() allowed—no problem, we can pull this off with pure linear constraints.

Core Intuition #

The key here is simple: if two price points are more than M apart, you can't select both of them. Translating that rule into linear inequalities gives us a straightforward set of constraints that your solver can handle.

Step-by-Step Implementation #

First, let's define some basics:

• Let pᵢ be the numerical value of the i-th price point (so p₁=1, p₂=2, ..., p₁₀=10)
• Let M be your maximum allowed spread (e.g., 4 or 5 from your examples)

1. Flag conflicting price pairs: For every pair of indices (i,j) where |pᵢ - pⱼ| > M, add this linear constraint:

   DVᵢ + DVⱼ ≤ 1
   

   This ensures you can't select both of these price points at the same time—exactly what we need to prevent spreads larger than M.

   For example, if M=4:

   • p₁=1 and p₆=6 have a gap of 5 (which is >4), so we add DV₁ + DV₆ ≤ 1
   • p₁=1 and p₇=7 have a gap of 6 (>4), so add DV₁ + DV₇ ≤ 1
   • Repeat this for every pair where the price difference exceeds M.

2. Why this works: By blocking every pair that would create an invalid spread, any valid selection of price points will automatically have their highest and lowest values within M of each other. There's no way to pick a set where the max-min gap exceeds M—we've eliminated all possible conflicting combinations.

Example Checks #

Let's verify with your test cases:

• Valid selection: DV = [1,0,1,1,1,0,0,0,0,0] (chosen prices: $1, $3, $4, $5). The spread is 5-1=4, which is ≤ M=5. None of the selected pairs have a gap larger than 5, so none of our pairwise constraints are violated—perfect.
• Invalid selection: DV = [1,0,1,0,0,0,0,0,1,0] (chosen prices: $1, $3, $9). The spread is 9-1=8 >5. The pair (1,9) has a gap of 8, so our constraint DV₁ + DV₉ ≤1 would be violated (both are 1), correctly marking this as invalid.

Scalable Alternative (For Larger Price Sets) #

If you ever have way more than 10 price points, the pairwise constraints could get lengthy. Here's a more scalable approach using auxiliary variables:

• Define two continuous variables: L (the lowest selected price) and H (the highest selected price)
• Add these constraints:
  • For all i: L ≤ pᵢ + (max_p) * (1 - DVᵢ)
    (If DVᵢ=1, this forces L ≤ pᵢ; if DVᵢ=0, the right-hand side becomes huge, so the constraint doesn't affect L)
  • For all i: H ≥ pᵢ - (max_p) * (1 - DVᵢ)
    (If DVᵢ=1, this forces H ≥ pᵢ; irrelevant if DVᵢ=0)
  • Final constraint: H - L ≤ M

This approach uses fewer constraints when you have a large number of price points, but for your 10-point use case, the pairwise method is simpler and easier to implement without extra variables.

内容的提问来源于stack exchange，提问作者Wibble