find one interior point of a polyhedron

savecancel

Hi,

I have a bunch of inequations and I would like to know if there is a solution. What is the simplest way to achieve this in Sage ? I tried using MILP with success... but the point returned is not very fancy (often on the boundary). In an ideal world, I would like to optimize some quadratic function in order for the solution to be the nicest possible.

Here is a sample and simple example with only one inequality (other constraints are equalities) where I reproduced the output of MILP:

Constraints:
  2.0 <= x_0 + x_7 + x_8 <= 2.0
  2.0 <= x_1 + x_2 <= 2.0
  2.0 <= x_3 + x_5 + x_9 <= 2.0
  2.0 <= x_4 + x_6 <= 2.0
  1.0 <= x_0 + x_2 + x_9 <= 1.0
  1.0 <= x_5 + x_6 + x_8 <= 1.0
  0.0 <= x_2 + x_6 <= 1.0
Variables:
  x_0 is a continuous variable (min=0.0, max=2.0)
  x_1 is a continuous variable (min=0.0, max=2.0)
  x_2 is a continuous variable (min=0.0, max=2.0)
  x_3 is a continuous variable (min=0.0, max=2.0)
  x_4 is a continuous variable (min=0.0, max=2.0)
  x_5 is a continuous variable (min=0.0, max=2.0)
  x_6 is a continuous variable (min=0.0, max=2.0)
  x_7 is a continuous variable (min=0.0, max=2.0)
  x_8 is a continuous variable (min=0.0, max=2.0)
  x_9 is a continuous variable (min=0.0, max=2.0)

There are plenty of nice solutions, one is

x0 = x2 = x5 = x6 = x8 = 1/3
x1 = x4 = 5/3
x3 = x7 = 4/3

But with the solver I got:

sage: p.solve()
sage: p.get_values(p[1],p[2],p[3],p[4],p[5],p[6],p[7],p[8],p[9])
[1, 2, 0, 2, 2, 0, 0, 0, 1]

Thanks