Possible bug in linprog

[cbullo]

Describe the bug

Running this test:

TEST(SliceTests, LinProg) {
  const double d0 = -0.62374404235647007;
  const double d1 = -3.0454022949824036;

  const double rp0 = 0.0;
  const double rp1 = 1.0;

  const double lw = 2.0 * 0.1;

  Eigen::MatrixXd(8, 2);

  Eigen::VectorXd f(2);
  f(0) = 1.0;
  f(1) = 1.0;

  Eigen::MatrixXd A(8, 2);
  A(0, 0) = -d0;
  A(1, 0) = d0;
  A(2, 0) = -d1;
  A(3, 0) = d1;
  A(4, 0) = 0.0;
  A(5, 0) = 0.0;
  A(6, 0) = 0.0;
  A(7, 0) = 0.0;

  A(0, 1) = 0.0;
  A(1, 1) = 0.0;
  A(2, 1) = 0.0;
  A(3, 1) = 0.0;
  A(4, 1) = -d0;
  A(5, 1) = d0;
  A(6, 1) = -d1;
  A(7, 1) = d1;

  Eigen::VectorXd b(8);
  b(0) = rp0;
  b(1) = 1.0 - rp0;
  b(2) = rp1;
  b(3) = 1.0 - rp1;
  b(4) = rp0;
  b(5) = 1.0 - rp0;
  b(6) = rp1;
  b(7) = 1.0 - rp1;

  Eigen::MatrixXd B(1, 2);
  B(0, 0) = -1.0;
  B(0, 1) = 1.0;

  Eigen::VectorXd c(1);
  c(0) = lw;

  Eigen::VectorXd x;
  bool solved = igl::linprog(f, A, b, B, c, x);
  EXPECT_TRUE(solved);

  
  auto constraints = b - A * x;
  std::cout << solved;
  std::cout << std::endl;
  std::cout << constraints;
  std::cout << std::endl;
}

Gives following output:

1
-0.0800662
   1.08007
   0.60908
   0.39092
 -0.204815
   1.20481
         0
         1

Meaning the function returns success, but the returned values don't fulfill the specified constraints.

Platform

• Windows
• macOS
• Linux

[alecjacobson]

oof.

The provided example is infeasible . The constraints are contradictory and there is no valid solution.

linprog probably shouldn't be returning true or the return value should be documented to mean something like returns false on failure or detected infeasibility, returns true on termination.

I'm not planning to dig into the algorithm now to figure out whether it will always correctly determine infeasibility. So for now I'm going to "fix" this with documentation.