c++ - 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;
}

项目编译和可执行文件运行并返回解 vector (0 1 0 0 0 0 0 0 0)和目标函数的值为0。我知道这是不正确的。解 vector 不满足上限约束。在此解 vector 处求得的目标函数不能为0。

我在为我的二次规划问题指定 MPS 文件时犯了错误，还是我需要在求解器搜索解决方案的方式中进行调整？我的问题可能与 CGAL 使用的确切类型有关吗？

例如，我尝试更改 <int>至 <double>在下一行

typedef CGAL::Quadratic_program_from_mps<int> Program;

程序已编译，但当我运行可执行文件时，求解器返回没有可行的解决方案。但我知道有一个可行的解决方案 - 我找到了一个使用 Excel 中的求解器的方法。

Answer 1

您确实应该在程序类型中使用而不是。但最重要的是，ET 应该被定义为 CGAL::Gmpzf(精确浮点类型)，而不是 CGAL::Gmpz(精确整数类型)。