淺聊求解器

語言: 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,早日有所突破,能夠進行商用。