寻求多变量最小最大值范围求解最大PnL的高效算法

问题描述 #

给定一张含N列的表格，除最后一列外均为变量（取值为0≤v<20的整数），最后一列为PnL（盈亏）。实际数据集最多包含40个变量、30000行。需为每个变量确定最小最大值范围，使得符合所有范围的行的PnL总和最大。

当前采用暴力枚举法实现，但当变量数超过3个时，算法运行效率极低，需寻求高效解决方案。

示例数据与最优解 #

示例表格 #

最优范围与结果 #

(1 <= v1 <= 2) && (4 <= v2 <= 5)，对应的PnL总和为6（3.5 + 2.5）

暴力枚举法的Java实现 #

暴力法通过枚举所有变量的可能范围组合，计算每个组合对应的PnL总和，最终保留最大值。但变量数超过3时，枚举量呈指数级增长，效率急剧下降。

import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/*
 * Brute Force Solution
 */
public class VariableOptimizer {

    double maxPnL = Double.NEGATIVE_INFINITY;
    int[][] optimalMinMax = null;
    double[][] varMinMax = null;

    public static void main(String[] args) {

        /*
            Constraints:
            Variables are whole Numbers (no fractions, decimals) and range between 0 to 19;
            i.e. variable v >= 0 and <= 19
         */
        double[][] data = {
              //{v1, v2, v3, PnL}
                {7, 8, 12, 100.50},
                {6, 9, 14, -200.10},
                {5, 10, 13, 150.25},
                {8, 11, 15, -510.35},
        };

        //data = loadCsv("./Optimize-MinMax.csv"); //or load data from file

        VariableOptimizer variableOptimizer = new VariableOptimizer();

        variableOptimizer.findOptimalMinMax(data, 0, null);

        System.out.println("maxPnL: " + variableOptimizer.maxPnL);

        for (int i = 0; i < variableOptimizer.optimalMinMax.length; i++){
            System.out.println("v" +i + " Min: " + variableOptimizer.optimalMinMax[i][0] + ", Max: " + variableOptimizer.optimalMinMax[i][1]);
        }
    }

    public void findOptimalMinMax(double[][] data, int varIdx, int[][] varMinMaxConditions){

        int noOfVars = data[0].length-1;

        if (varMinMaxConditions == null) {
            varMinMaxConditions = new int[noOfVars][2];
        }

        if (varIdx == noOfVars) {

            double pnl = calculatePnl(data, varMinMaxConditions);

            if (pnl >= maxPnL) {
                maxPnL = pnl;
                optimalMinMax = java.util.Arrays.stream(varMinMaxConditions)
                        .map(a ->  java.util.Arrays.copyOf(a, a.length))
                        .toArray(int[][]::new);
            }
            return;
        }

        double[][] varMinMax = getVarMinMax(data);
        int varMin = (int)varMinMax[varIdx][0];
        int varMax = (int)varMinMax[varIdx][1];

        for (int i = varMin; i <= varMax; i++) {
            for (int j = i; j <= varMax; j++ ) {

                varMinMaxConditions[varIdx][0] = i;
                varMinMaxConditions[varIdx][1] = j;

                findOptimalMinMax(data, varIdx + 1, varMinMaxConditions);
            }
        }
    }

    public static double calculatePnl(double[][] data, int[][] varMinMaxConditions){

        double pnl = 0;

        for (int i = 0; i < data.length; i++) {

            double[] row = data[i];
            double rowPnl = row[row.length-1];

            boolean includeRow = true;
            for (int j = 0; j < varMinMaxConditions.length; j++){

                double varMin = varMinMaxConditions[j][0];
                double varMax = varMinMaxConditions[j][1];

                if (varMin > row[j] || row[j] > varMax){
                    includeRow = false;
                }
            }

            if (includeRow) {
                pnl += rowPnl;
            }
        }

        return pnl;
    }

    public double[][] getVarMinMax(double[][] data){

        if (varMinMax == null) {
            int noOfVars = data[0].length - 1;

            varMinMax = new double[noOfVars][2];

            for (int rowIdx = 0; rowIdx < data.length; rowIdx++) {
                for (int varIdx = 0; varIdx < noOfVars; varIdx++) {
                    if (rowIdx > 0) {
                        varMinMax[varIdx][0] = Math.min(data[rowIdx][varIdx], varMinMax[varIdx][0]);
                        varMinMax[varIdx][1] = (int)Math.max(data[rowIdx][varIdx], varMinMax[varIdx][1]);
                    } else {
                        varMinMax[varIdx][0] = data[rowIdx][varIdx];
                        varMinMax[varIdx][1] = data[rowIdx][varIdx];
                    }
                }
            }
        }

        return varMinMax;
    }

    public static double[][] loadCsv(String file){
        List<double[]> rows = new ArrayList<>();
        try {
            Files.lines(Paths.get(file)).forEach(s -> {
                if (!java.lang.Character.isDigit(s.charAt(0))) return;
                String[] line = s.split(",");
                double[] row = Arrays.stream(line)
                        .mapToDouble(Double::parseDouble)
                        .toArray();
                rows.add(row);
            });
        } catch (Exception e) {
            throw new RuntimeException(e);
        }

        double[][] result = new double[rows.size()][];
        for (int i = 0; i < rows.size(); i++) {
            result[i] = rows.get(i);
        }
        return result;
    }
}

高效解决方案 #

核心思路分析 #

暴力法的时间复杂度为O((M²)^N * R)，其中M是变量取值数（20），N是变量数，R是行数。当N=40时，枚举量达到天文数字，完全不可行。针对该问题，可根据变量规模选择以下方案：

1. 贪心迭代算法（适合40个变量的大规模场景）

该算法通过逐个优化变量的范围，迭代收敛到最优解，时间复杂度为O(NM²R)，在40个变量、30000行的数据集上可快速完成计算。

实现步骤：

• 初始化所有变量范围为[0,19]，计算初始PnL总和。
• 遍历每个变量，固定其他变量的当前范围，枚举该变量的所有可能区间，找到使PnL总和最大的区间。
• 重复上述步骤，直到所有变量的范围不再变化（收敛）。

示例代码：

import java.util.Arrays;

public class EfficientVariableOptimizer {
    private double maxPnL;
    private int[][] optimalMinMax;
    private final int[][] variables; // 存储所有行的变量值（整数）
    private final double[] pnls;     // 存储每行的PnL
    private final int numVars;
    private final int numRows;

    public EfficientVariableOptimizer(double[][] data) {
        numRows = data.length;
        numVars = data[0].length - 1;
        variables = new int[numRows][numVars];
        pnls = new double[numRows];

        // 预处理数据，将变量转为整数，分离PnL
        for (int i = 0; i < numRows; i++) {
            for (int j = 0; j < numVars; j++) {
                variables[i][j] = (int) data[i][j];
            }
            pnls[i] = data[i][numVars];
        }
    }

    public void findOptimalMinMax() {
        // 初始化所有变量范围为[0,19]
        int[][] currentMinMax = new int[numVars][2];
        for (int i = 0; i < numVars; i++) {
            currentMinMax[i][0] = 0;
            currentMinMax[i][1] = 19;
        }
        maxPnL = calculatePnl(currentMinMax);
        optimalMinMax = Arrays.stream(currentMinMax)
                .map(Arrays::copyOf)
                .toArray(int[][]::new);

        boolean changed;
        do {
            changed = false;
            for (int varIdx = 0; varIdx < numVars; varIdx++) {
                double bestPnl = maxPnL;
                int[] bestRange = Arrays.copyOf(currentMinMax[varIdx], 2);

                // 枚举当前变量的所有可能区间
                for (int L = 0; L <= 19; L++) {
                    for (int R = L; R <= 19; R++) {
                        currentMinMax[varIdx][0] = L;
                        currentMinMax[varIdx][1] = R;
                        double currentPnl = calculatePnl(currentMinMax);
                        if (currentPnl > bestPnl) {
                            bestPnl = currentPnl;
                            bestRange[0] = L;
                            bestRange[1] = R;
                            changed = true;
                        }
                    }
                }
                // 更新当前变量的最优范围
                currentMinMax[varIdx][0] = bestRange[0];
                currentMinMax[varIdx][1] = bestRange[1];
                if (bestPnl > maxPnL) {
                    maxPnL = bestPnl;
                    optimalMinMax = Arrays.stream(currentMinMax)
                            .map(Arrays::copyOf)
                            .toArray(int[][]::new);
                }
            }
        } while (changed);
    }

    private double calculatePnl(int[][] minMax) {
        double sum = 0.0;
        for (int i = 0; i < numRows; i++) {
            boolean include = true;
            for (int j = 0; j < numVars; j++) {
                int val = variables[i][j];
                if (val < minMax[j][0] || val > minMax[j][1]) {
                    include = false;
                    break;
                }
            }
            if (include) {
                sum += pnls[i];
            }
        }
        return sum;
    }

    public static void main(String[] args) {
        double[][] data = {
                {1, 4, 3.5},
                {2, 5, 2.5},
                {2, 6, -11.0}
        };

        EfficientVariableOptimizer optimizer = new EfficientVariableOptimizer(data);
        optimizer.findOptimalMinMax();

        System.out.println("最大PnL总和: " + optimizer.maxPnL);
        for (int i = 0; i < optimizer.numVars; i++) {
            System.out.printf("v%d 范围: [%d, %d]%n", i+1, optimizer.optimalMinMax[i][0], optimizer.optimalMinMax[i][1]);
        }
    }
}

2. 分支定界法（适合变量数≤10的小规模场景）

通过枚举变量范围的分支，并计算每个分支的PnL上界，剪枝不可能超过当前最优解的分支，大幅减少枚举量。适合变量数较少的场景，可得到精确最优解。

3. 启发式算法（适合超大规模变量场景）

当变量数超过40或需要更快的近似解时，可采用遗传算法、模拟退火等启发式算法，通过迭代优化找到近似最优解，平衡计算时间与解的质量。

算法复杂度对比 #

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