Я использую пакет 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.
