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

项目编译，可执行文件运行，returns解向量（0 1 0 0 0 0 0 0 0）和objective函数的值为0。我知道这个是不正确的。解向量不满足上限约束。 objective 在此解向量处计算的函数不能等于 0。

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

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

typedef CGAL::Quadratic_program_from_mps<int> Program;

程序已编译，但是当我运行可执行文件时，求解器返回没有可行的解决方案。但我知道有一个可行的解决方案 - 我在 Excel.

中找到了一个使用求解器的解决方案

Answer 1

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

CGAL 二次规划包找到不正确的解决方案

CGAL Quadratic Programming Package Finds Incorrect Solution

c++

cgal

mps-format

quadratic-programming