3

我正在使用 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 使用的确切类型有关吗？

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

typedef CGAL::Quadratic_program_from_mps<int> Program;

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

4

1 回答 1

0

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

于 2015-09-14T10:33:55.460 回答