CGAL Quadratic Programming Package Finds Incorrect Solution

Question

I am using CGAL QP package to solve the following quadratic problem:

I am using the following MPS file to define the problem (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

Note that I am using QUADOBJ to define the D matrix. In case of QUADOBJ, only the entries of 2D on or below the diagonal must be specified, entries above the diagonal are deduced from symmetry. I then feed this file to the solver (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;
}

The project compiles and the executable file runs and returns the solution vector (0 1 0 0 0 0 0 0 0) and the value of the objective function is 0. I know this is not correct. The solution vector does not satisfy the upper bound constraint. The objective function evaluated at this solution vector cannot be equal to 0.

Am I making a mistake in specifying the MPS file for my quadratic programming problem, or is there something I need to adjust in the way the solver searches for a solution? Could my problem be related to the exact type that CGAL uses?

For instance, I have tried changing <int> to <double> in the following line

typedef CGAL::Quadratic_program_from_mps<int> Program;

The program compiled, but when I ran the executable the solver returned that no solution was feasible. But I know there is a feasible solution - I have found one using the solver in Excel.

Answer 1

You should indeed use instead of in the Program type. But on top of that, ET should be typedef'd as CGAL::Gmpzf (exact floating point type), and not CGAL::Gmpz (exact integral type).