CGAL二次規劃套餐查找不正確的解決方案

Question

我使用CGAL QP包解決以下問題二次方程：

我使用下面的MPS文件來定義問題（first_qp.mps）：

NAME first_qp 
ROWS 
E c0 
COLUMNS 
x0 c0 1 
x1 c0 1 
x2 c0 1 
x3 c0 1 
x4 c0 1 
x5 c0 1 
x6 c0 1 
x7 c0 1 
x8 c0 1 
RHS 
rhs c0 1 
BOUNDS 
UP BND x0 0.2 
UP BND x1 0.2 
UP BND x2 0.2 
UP BND x3 0.2 
UP BND x4 0.2 
UP BND x5 0.2 
UP BND x6 0.2 
UP BND x7 0.2 
UP BND x8 0.2 
QUADOBJ 
x0 x0 39.07 
x1 x0 25.54 
x2 x0 27.29 
x3 x0 28.56 
x4 x0 24.38 
x5 x0 10.23 
x6 x0 11.12 
x7 x0 15.26 
x8 x0 25.17 
x1 x1 38.82 
x2 x1 18.11 
x3 x1 20.67 
x4 x1 17.20 
x5 x1 8.10 
x6 x1 12.41 
x7 x1 9.82 
x8 x1 14.69 
x2 x2 39.97 
x3 x2 26.82 
x4 x2 22.55 
x5 x2 12.81 
x6 x2 10.90 
x7 x2 16.17 
x8 x2 26.42 
x3 x3 29.00 
x4 x3 24.61 
x5 x3 10.37 
x6 x3 10.65 
x7 x3 14.93 
x8 x3 23.61 
x4 x4 49.71 
x5 x4 7.04 
x6 x4 6.20 
x7 x4 17.41 
x8 x4 25.87 
x5 x5 12.47 
x6 x5 8.21 
x7 x5 7.53 
x8 x5 9.73 
x6 x6 19.02 
x7 x6 7.47 
x8 x6 7.87 
x7 x7 16.04 
x8 x7 14.95 
x8 x8 28.90 
ENDATA 

請注意，我使用QUADOBJ來定義D矩陣。在QUADOBJ的情況下，只需要指定對角線上或下方的2D條目，則從對稱性推斷出對角線上方的條目。然後我喂此文件以解算器（first_qp_from_mps.cpp）：

// example: read quadratic program in MPS format from file 
// the QP below is the first quadratic program example in the user manual 
#include <iostream> 
#include <fstream> 
#include <CGAL/basic.h> 
#include <CGAL/QP_models.h> 
#include <CGAL/QP_functions.h> 

// choose exact integral type 
#ifdef CGAL_USE_GMP 
#include <CGAL/Gmpz.h> 
typedef CGAL::Gmpz ET; 
#else 
#include <CGAL/MP_Float.h> 
typedef CGAL::MP_Float ET; 
#endif 

// program and solution types 
typedef CGAL::Quadratic_program_from_mps<int> Program; 
typedef CGAL::Quadratic_program_solution<ET> Solution; 

int main() { 
    std::ifstream in ("first_qp.mps"); 
    Program qp(in);   // read program from file 
    assert (qp.is_valid()); // we should have a valid mps file 

    // solve the program, using ET as the exact type 
    Solution s = CGAL::solve_quadratic_program(qp, ET()); 

    // output solution 
    std::cout << s; 
    return 0; 
} 

的項目編譯和可執行文件運行並返回溶液矢量（0 1 0 0 0 0 0 0 0）和的值目標函數爲0.我知道這是不正確的。解矢量不滿足上限約束。在這個解決方案矢量評估的目標函數不能等於0.

我是在爲我的二次規劃問題指定MPS文件時出錯，還是我需要在解算器搜索解？我的問題可能與CGAL使用的確切類型有關嗎？

例如，我曾嘗試在下面的行

typedef CGAL::Quadratic_program_from_mps<int> Program; 

所編譯的程序改變<int>到<double>，但是當我跑了可執行的求解器返回無解是可行的。但我知道有一個可行的解決方案 - 我在Excel中找到了一個使用解算器的解決方案。

Answer 1

你應該確實使用，而不是在程序類型。但最重要的是，ET應該被定義爲CGAL :: Gmpzf（確切的浮點類型），而不是CGAL :: Gmpz（確切的整型）。