淺聊求解器

語言: CN / TW / HK

對於從事工程的同學來説,求解器應該屬於比較陌生的一個領域。一是工程層面要解決的算法問題本身偏少;二是工程上涉及的算法問題相對簡單,還到不了要使用求解器的程度。我們項目最近剛好要進行工程算法的重構,我才瞭解到解決算法問題可以使用求解器,並感受到求解器解決問題不僅簡單易懂,而且高效穩定。

工程上的算法問題

對於衡量工程上算法性能的指標就兩個:時間複雜度和空間複雜度。現在雲計算的硬件資源配置已經越來越好,空間複雜度已經不是一個問題,所以算法的性能指標主要就是時間複雜度。

為了優化算法達到更好的性能,工程上設計了各種不同的數據存儲結構:數組,鏈表,哈希表,堆,隊列,樹,圖等等,並基於不同的數據結構設計了不同的算法:窮舉,二分法,遞歸,回溯,分治,深度優先,廣度優先,動態規劃等等。

要深入理解這些算法,並靈活運用到工作中,不是一朝一夕能夠達成,至少你要把《數據結構》《算法導論》相關的書籍重新再梳理一遍,這些底層知識都是比較難啃的骨頭。

求解器好像就為你打開了一扇門,不需要你再去深挖這些算法知識,它在底層把這些都進行了封裝,暴露給用户簡單易懂的上層應用接口,讓用户面向場景編程而不是算法編程。

Untitled Diagram.drawio.png

求解器作用和背景

求解器是用來求解數學規劃問題的軟件,廣泛應用於雲計算、金融、交通、製造、能源等領域,在大學生熟悉的數學建模比賽中經常會使用Matlab求解器。

對於求解器本身,其技術壁壘高,研發難度大,長期以來,高性能商用求解器的核心技術始終是由歐美企業主導的。目前國內求解器無論是從求解時間、所支持求解的模型還是所支持的語言來看,都與國外求解器有一定的差距。如下圖所示:

image.png

求解器使用實例

下面我使用工程算法和求解器Gurobi來解決同一個算法問題(KM)。

工程算法解決方案參考:https://juejin.cn/post/7071638920110276621

求解器解決方案如下: ``` import gurobi.*;

import java.util.Random;

public class KM {

public static void main(String[] args) throws GRBException {
    int orderNum = 3;
    int carNum = 2;
    double[][] orderCarMatrix = new double[orderNum][carNum];

    Random random = new Random();
    for(int orderIndex=0; orderIndex<orderNum; orderIndex++) {
        for (int carIndex=0; carIndex<carNum; carIndex++) {
            orderCarMatrix[orderIndex][carIndex] = random.nextInt(5);
            System.out.print(orderCarMatrix[orderIndex][carIndex]+" ");
        }
        System.out.println();
    }

    GRBEnv env = new GRBEnv();
    GRBModel model = new GRBModel(env);
    model.set(GRB.StringAttr.ModelName, "km");

    //定義求解器變量
    GRBVar[][] xArr = new GRBVar[orderNum][carNum];
    for(int orderIndex=0; orderIndex<orderNum; orderIndex++) {
        for (int carIndex=0; carIndex<carNum; carIndex++) {
            xArr[orderIndex][carIndex] = model.addVar(0.0, 1.0, 0.0, GRB.BINARY,"od-"+orderIndex+"-"+carIndex);
        }
    }

    //定義求解器的目標
    GRBLinExpr object = new GRBLinExpr();
    for(int orderIndex=0; orderIndex<orderNum; orderIndex++) {
        for (int carIndex=0; carIndex<carNum; carIndex++) {
            object.addTerm(orderCarMatrix[orderIndex][carIndex], xArr[orderIndex][carIndex]);
        }
    }
    model.setObjective(object, GRB.MAXIMIZE);//定義目標

    //定義求解器約束條件
    for(int orderIndex=0; orderIndex<orderNum; orderIndex++) {
        GRBLinExpr conStr1 = new GRBLinExpr();
        for (int carIndex=0; carIndex<carNum; carIndex++) {
            conStr1.addTerm(1,xArr[orderIndex][carIndex]);
        }
        model.addConstr(conStr1, GRB.LESS_EQUAL, 1.0, "order"+orderIndex); //確保一個訂單隻能被一個車匹配
    }


    for(int carIndex=0; carIndex<carNum; carIndex++) {
        GRBLinExpr conStr2 = new GRBLinExpr();
        for (int orderIndex=0; orderIndex<orderNum; orderIndex++) {
            conStr2.addTerm(1,xArr[orderIndex][carIndex]);
        }
        model.addConstr(conStr2, GRB.LESS_EQUAL, 1.0, "car"+carIndex); //確保一個車只能被一個訂單匹配
    }

    model.optimize(); //求解

    System.out.println("Obj: " + model.get(GRB.DoubleAttr.ObjVal)); //輸出目標值

    model.dispose();
    env.dispose();

}

} ``` 從兩種解決方案對比來看: 1. 求解器編寫的代碼簡單、易理解 2. 由於支持的算法較簡單、兩種解決方案的求解效率差不多 3. 求解器可擴展更好,求解問題就三個步驟,定義變量、定義目標數學模型、制定約束條件,每一個步驟都可以無限擴展。

雖然求解器使用非常方便並且高效,但是費用卻是相當昂貴,一般小企業可能都承受不起,基本都是按照服務器的數量進行收費的,一台服務器就得幾十萬。願我們國產的求解器CMIP,早日有所突破,能夠進行商用。