# Revision history [back]

### find one interior point of a polyhedron

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 and Polyhedron without success... In an ideal world, I would also like to optimize some quadratic function (in order for the solution to be nicer).

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=1.0)
x_1 is a continuous variable (min=0.0, max=1.0)
x_2 is a continuous variable (min=0.0, max=1.0)
x_3 is a continuous variable (min=0.0, max=1.0)
x_4 is a continuous variable (min=0.0, max=1.0)
x_5 is a continuous variable (min=0.0, max=1.0)
x_6 is a continuous variable (min=0.0, max=1.0)
x_7 is a continuous variable (min=0.0, max=1.0)
x_8 is a continuous variable (min=0.0, max=1.0)
x_9 is a continuous variable (min=0.0, max=1.0)


There are plenty of solutions, one is

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


Thanks

### find one interior point of a polyhedron

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 and Polyhedron without success... In an ideal world, I would also like to optimize some quadratic function (in order for the solution to be nicer).

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=1.0)
x_1 is a continuous variable (min=0.0, max=1.0)
x_2 is a continuous variable (min=0.0, max=1.0)
x_3 is a continuous variable (min=0.0, max=1.0)
x_4 is a continuous variable (min=0.0, max=1.0)
x_5 is a continuous variable (min=0.0, max=1.0)
x_6 is a continuous variable (min=0.0, max=1.0)
x_7 is a continuous variable (min=0.0, max=1.0)
x_8 is a continuous variable (min=0.0, max=1.0)
x_9 is a continuous variable (min=0.0, max=1.0)


There are plenty of solutions, one is

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


But both with solver="glpk" and solver="ppl" I got error messages after p.solve() and more precisely:

MIPSolverException: 'GLPK : Solution is undefined'


or

MIPSolverException: 'PPL : There is no feasible solution'


even if I add an arbitrary objective.

Thanks

### find one interior point of a polyhedron

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 and Polyhedron without with success... but the point returned is not very fancy (often on the boundary). In an ideal world, I would also like to optimize some quadratic function (in in order for the solution to be nicer).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=1.0)
max=2.0)
x_1 is a continuous variable (min=0.0, max=1.0)
max=2.0)
x_2 is a continuous variable (min=0.0, max=1.0)
max=2.0)
x_3 is a continuous variable (min=0.0, max=1.0)
max=2.0)
x_4 is a continuous variable (min=0.0, max=1.0)
max=2.0)
x_5 is a continuous variable (min=0.0, max=1.0)
max=2.0)
x_6 is a continuous variable (min=0.0, max=1.0)
max=2.0)
x_7 is a continuous variable (min=0.0, max=1.0)
max=2.0)
x_8 is a continuous variable (min=0.0, max=1.0)
max=2.0)
x_9 is a continuous variable (min=0.0, max=1.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 both with solver="glpk" and solver="ppl" I got error messages after p.solve() and more precisely:the solver I got:

MIPSolverException: 'GLPK : Solution is undefined'
sage: p.solve()
sage: p.get_values(p,p,p,p,p,p,p,p,p)
[1, 2, 0, 2, 2, 0, 0, 0, 1]


or

MIPSolverException: 'PPL : There is no feasible solution'


even if I add an arbitrary objective.

Thanks 4 retagged FrédéricC 2539 ●3 ●28 ●53

### find one interior point of a polyhedron

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,p,p,p,p,p,p,p,p)
[1, 2, 0, 2, 2, 0, 0, 0, 1]


Thanks