what is inhomog_var ?

Questions and problems about using polymake go here.
kisas
Posts: 12
Joined: 03 Oct 2014, 21:22

what is inhomog_var ?

Postby kisas » 17 Oct 2014, 22:57

This inhomog_var shows up when I was computing the facets using the following standard code:
$f=lp2poly('2.lp');
$p = new Polytope<Rational>($f);
$p->LATTICE_POINTS;
$s=new Polytope(POINTS=>$p->LATTICE_POINTS, COORDINATE_LABELS=>$p->COORDINATE_LABELS);
print_constraints($s);


In facets I got, there are such inequalities

2inhomog_var - f11 + 2u44 + y34 >= 0
-inhomog_var - f11 - f21 + 2f24 + 2y14 + y41 >= 3



Is the inhomog_var a slack var? From my textbook integer programming knowledge, I couldn't think of what any slack var is needed for representing facets. Does this has anything to do with Polymake's coordinate system? Is this var positive? what's the value range?

Thanks in advance!


Here is my LP model used to describe the polyhedron:

Minimize
obj:1000 u11 + 10000 u14 + 10000 u21 + 10000 u24 +
10000 u31 + 10000 u34 + 10000 u41 + 10000 u44

Subject To
flow_bal_middle21:
-f11 + f21 - u21 = 0

flow_bal_middle24:
-f14 + f24 - u24 = 0

flow_bal_middle31:
-f21 + f31 - u31 = 0

flow_bal_middle34:
-f24 + f34 - u34 = 0

flow_bal_sink1:
-f11 + f41 - u21 - u31 = 0

flow_bal_sink4:
f34 - f44 - u24 - u34 = 0

unit_selection_12:
u21 + u24 = 1

unit_selection_13:
u31 + u34 = 1

unit_selection_21:
u11 + u14 <= 1

unit_selection_24:
u41 + u44 <= 1

line_occupation111:
f11 - 2 y11 <= 0

line_occupation112:
f21 - 2 y21 <= 0

line_occupation113:
f31 - 2 y31 <= 0

line_occupation114:
f41 - 2 y41 <= 0

line_occupation141:
f14 - 2 y14 <= 0

line_occupation142:
f24 - 2 y24 <= 0

line_occupation143:
f34 - 2 y34 <= 0

line_occupation144:
f44 - 2 y44 <= 0

line_occupation211:
f11 + 2 y11 >= 0

line_occupation212:
f21 + 2 y21 >= 0

line_occupation213:
f31 + 2 y31 >= 0

line_occupation214:
f41 + 2 y41 >= 0

line_occupation241:
f14 + 2 y14 >= 0

line_occupation242:
f24 + 2 y24 >= 0

line_occupation243:
f34 + 2 y34 >= 0

line_occupation244:
f44 + 2 y44 >= 0

node_disjoint11:
y11 + y41 - 2 u11 <= 0

node_disjoint12:
y11 + y21 - 2 u21 <= 0

node_disjoint13:
y21 + y31 - 2 u31 <= 0

node_disjoint14:
y31 + y41 - 2 u41 <= 0

node_disjoint41:
y14 + y44 - 2 u14 <= 0

node_disjoint42:
y14 + y24 - 2 u24 <= 0

node_disjoint43:
y24 + y34 - 2 u34 <= 0

node_disjoint44:
y34 + y44 - 2 u44 <= 0

Bounds
0<=y11<=1
0<=y14<=1
0<= y21<=1
0<= y24<=1
0<=y31<=1
0<=y34<=1
0<=y41<=1
0<=y44<=1
0<=u11<=1
0<=u14<=1
0<=u21<=1
0<=u24<=1
0<=u31<=1
0<=u34<=1
0<=u41<=1
0<=u44<=1
-2<=f11<=2
-2<=f14<=2
-2<=f21<=2
-2<=f24<=2
-2<=f31<=2
-2<=f34<=2
-2<=f41<=2
-2<=f44<=2

Binaries
y11 y14 y21 y24 y31 y34 y41 y44 u11 u14 u21 u24 u31 u34 u41 u44

Generals
f11 f14 f21 f24 f31 f34 f41 f44

End

kisas
Posts: 12
Joined: 03 Oct 2014, 21:22

Re: what is inhomog_var ?

Postby kisas » 22 Oct 2014, 16:53

does anyone have any idea about this? Any input is highly appreciated.

User avatar
assarf
Developer
Posts: 74
Joined: 12 Oct 2011, 15:52

Re: what is inhomog_var ?

Postby assarf » 22 Oct 2014, 18:18

Hi there,

we talked about it and found some inconsistencies in our code. In the meantime, you might want to do the following as a workaround:

Code: Select all

$s=new Polytope(POINTS=>$p->LATTICE_POINTS, COORDINATE_LABELS=>[splice([@{$p->COORDINATE_LABELS}],1)]);
problem is that print_constraints thinks that the first coordinate has no label but the lp-parser produces such a label
no signature

kisas
Posts: 12
Joined: 03 Oct 2014, 21:22

Re: what is inhomog_var ?

Postby kisas » 22 Oct 2014, 21:17

Hi Assarf,
Thanks for your solution. But when I copied your code to polymake, it has the following error. The code seems too advance to me. I couldn't figure out what is wrong here. Can you please check if I missed anything?

Thanks!

polytope > $s=new Polytope(POINTS=>$p->LATTICE_POINTS, COORDINATE_LABELS=>[splice([@{$p->COORDINATE_LABELS}],1)]);

polymake: ERROR: Type of arg 1 to splice must be array (not anonymous list ([])) at input line 1, near "1)"





Hi there,

we talked about it and found some inconsistencies in our code. In the meantime, you might want to do the following as a workaround:

Code: Select all

$s=new Polytope(POINTS=>$p->LATTICE_POINTS, COORDINATE_LABELS=>[splice([@{$p->COORDINATE_LABELS}],1)]);
problem is that print_constraints thinks that the first coordinate has no label but the lp-parser produces such a label

User avatar
gawrilow
Main Author
Posts: 423
Joined: 25 Dec 2010, 17:40

Re: what is inhomog_var ?

Postby gawrilow » 22 Oct 2014, 22:15

There are too many brackets for my taste.
Let's make it simpler:

my @labels=@{$p->COORDINATE_LABELS};
shift @labels; # get rid of the wrong leading one
$s=new Polytope(POINTS=>$p->LATTICE_POINTS, COORDINATE_LABELS=>\@labels);

Please remove 'my' in the first command if you enter this snippet in the interactive shell line by line.

kisas
Posts: 12
Joined: 03 Oct 2014, 21:22

Re: what is inhomog_var ?

Postby kisas » 22 Oct 2014, 22:50

Thank you! Gawrilow. It works. However, I found that the facets I got this time is different from the previous one with inhomog_var. I was expecting, with the modified code, the inequalities I got won't change much, except the inhomog_var gone. So it seems that this bug has messed up all the facets. The affine hull seems to shifted by one column. Here attached are the two set of facets I got with the original code and the modified code.

polytope > print_constraints($s);
Facets:
0: 2inhomog_var - f11 + 2u44 + y34 >= 0
1: f11 - 2f24 + y34 + 2y21 >= 0
2: f11 - 2f24 + 2y11 + y34 >= 0
3: -inhomog_var + f11 + f21 + y41 + 2y24 >= 1
4: -inhomog_var + f11 + f21 + 2y31 + y41 >= 1
5: u21 - y24 >= 0
6: -inhomog_var - f11 - f21 + 2f24 + 2y14 + y41 >= 3
7: u21 - y31 >= 0
8: u34 - y21 >= 0
9: u34 - y11 >= 0
10: -u34 - u41 >= -1
11: -inhomog_var + 2f11 - f24 >= 0
12: f11 - f24 - y14 >= -1
13: inhomog_var - f11 - y41 >= -1
14: -f11 + f24 - y34 >= 0
15: inhomog_var - f11 + f44 >= 0
16: -f44 - u21 >= -1
17: -f11 + f24 + u41 >= 1
18: -inhomog_var + f11 - u44 >= 0

Affine hull:
0: -inhomog_var + f11 - f21 + f14 = 1
1: -1/2inhomog_var - 1/2f11 - 1/2f21 - 1/2f14 + f24 + f31 = 3/2
2: -1/6inhomog_var - 1/6f11 - 1/6f21 - 1/6f14 - 2/3f24 + 1/3f31 + f34 = 1/2
3: 7/20inhomog_var - 3/20f11 - 13/20f21 - 3/20f14 - 1/10f24 - 1/5f31 - 1/10f34 + f41 = -11/20
4: 13/33inhomog_var - 5/11f11 - 10/33f21 + 6/11f14 + 1/33f24 + 2/33f31 + 1/33f34 - 10/33f41 + u11 = 2/3
5: -13/61inhomog_var + 15/61f11 + 10/61f21 - 18/61f14 - 1/61f24 - 2/61f31 - 1/61f34 + 10/61f41 + 28/61u11 + u14 = 39/61
6: 18/89inhomog_var + 34/89f11 - 7/89f21 - 23/89f14 - 26/89f24 + 37/89f31 - 26/89f34 - 7/89f41 + 16/89u11 - 16/89u14 + u24 = 35/89
7: -18/149inhomog_var - 34/149f11 + 7/149f21 + 23/149f14 + 26/149f24 - 37/149f31 + 26/149f34 + 7/149f41 - 16/149u11 + 16/149u14 + 60/149u24 + u31 = 114/149


With modified code

polytope > print_constraints($s);
Facets:
0: 2f11 - f21 + 2y11 + y21 >= 0
1: f21 - 2f31 + y21 + 2y41 >= 0
2: f21 - 2f31 + 2y31 + y21 >= 0
3: -f11 + f21 + f14 + y24 + 2y44 >= 1
4: -f11 + f21 + f14 + 2y14 + y24 >= 1
5: u14 - y44 >= 0
6: -f11 - f21 - f14 + 2f31 + 2y34 + y24 >= 3
7: u14 - y14 >= 0
8: u41 - y41 >= 0
9: u41 - y31 >= 0
10: -u41 - u44 >= -1
11: -f11 + 2f21 - f31 >= 0
12: f21 - f31 - y34 >= -1
13: f11 - f21 - y24 >= -1
14: -f21 + f31 - y21 >= 0
15: f11 - f21 + u11 >= 0
16: -u11 - u14 >= -1
17: -f21 + f31 + u44 >= 1
18: -f11 + f21 - y11 >= 0

Affine hull:
0: -f11 + f21 - f14 + f24 = 1
1: -1/2f11 - 1/2f21 - 1/2f14 - 1/2f24 + f31 + f34 = 3/2
2: -1/6f11 - 1/6f21 - 1/6f14 - 1/6f24 - 2/3f31 + 1/3f34 + f41 = 1/2
3: 7/20f11 - 3/20f21 - 13/20f14 - 3/20f24 - 1/10f31 - 1/5f34 - 1/10f41 + f44 = -11/20
4: 13/33f11 - 5/11f21 - 10/33f14 + 6/11f24 + 1/33f31 + 2/33f34 + 1/33f41 - 10/33f44 + u21 = 2/3
5: -13/61f11 + 15/61f21 + 10/61f14 - 18/61f24 - 1/61f31 - 2/61f34 - 1/61f41 + 10/61f44 + 28/61u21 + u24 = 39/61
6: 18/89f11 + 34/89f21 - 7/89f14 - 23/89f24 - 26/89f31 + 37/89f34 - 26/89f41 - 7/89f44 + 16/89u21 - 16/89u24 + u31 = 35/89
7: -18/149f11 - 34/149f21 + 7/149f14 + 23/149f24 + 26/149f31 - 37/149f34 + 26/149f41 + 7/149f44 - 16/149u21 + 16/149u24 + 60/149u31 + u34 = 114/149






There are too many brackets for my taste.
Let's make it simpler:

my @labels=@{$p->COORDINATE_LABELS};
shift @labels; # get rid of the wrong leading one
$s=new Polytope(POINTS=>$p->LATTICE_POINTS, COORDINATE_LABELS=>\@labels);

Please remove 'my' in the first command if you enter this snippet in the interactive shell line by line.

User avatar
assarf
Developer
Posts: 74
Joined: 12 Oct 2011, 15:52

Re: what is inhomog_var ?

Postby assarf » 23 Oct 2014, 12:22

So it seems that this bug has messed up all the facets. The affine hull seems to shifted by one column. Here attached are the two set of facets I got with the original code and the modified code.
please note that this bug, did actually not mess up all the facets. Internally they still work as they should. The only thing what was messed up is the print out with "print_constraints". Only the variable names got shifted by one, but not the actual variable.
no signature

kisas
Posts: 12
Joined: 03 Oct 2014, 21:22

Re: what is inhomog_var ?

Postby kisas » 23 Oct 2014, 21:09

Thanks for your reply. I might have missed something. If you compare the facets and the affine hulls: for the affine hulls, you can observe that the variable names are shifted by one column; but for the facets, there is not a clear pattern of name shifting. Why the print_constraints function has different consequences for facets and affine hulls? I'm just curious.

So it seems that this bug has messed up all the facets. The affine hull seems to shifted by one column. Here attached are the two set of facets I got with the original code and the modified code.
please note that this bug, did actually not mess up all the facets. Internally they still work as they should. The only thing what was messed up is the print out with "print_constraints". Only the variable names got shifted by one, but not the actual variable.

User avatar
assarf
Developer
Posts: 74
Joined: 12 Oct 2011, 15:52

Re: what is inhomog_var ?

Postby assarf » 27 Oct 2014, 09:42

When I look at the code, I suspect that if you look at the order property 'COORDINATE_LABELS' you will see that the facets are also shifted by one.
no signature

kisas
Posts: 12
Joined: 03 Oct 2014, 21:22

Re: what is inhomog_var ?

Postby kisas » 28 Oct 2014, 17:29

Thank you for the confirmation.

Is there a perl IDE like MS Visual Studio for C++? You can follow into the functions, see the value of variables.
When I look at the code, I suspect that if you look at the order property 'COORDINATE_LABELS' you will see that the facets are also shifted by one.


Return to “Helpdesk”