1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
|
# Copyright (c) 1997-2024
# Ewgenij Gawrilow, Michael Joswig, and the polymake team
# Technische Universität Berlin, Germany
# https://polymake.org
#
# This program is free software; you can redistribute it and/or modify it
# under the terms of the GNU General Public License as published by the
# Free Software Foundation; either version 2, or (at your option) any
# later version: http://www.gnu.org/licenses/gpl.txt.
#
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
# GNU General Public License for more details.
#-----------------------------------------------------------------------------
# @file integer_hull_unb
#
# Script to generate the integer hull arising from a given LP file
# that specifies a (possibly) unbounded polyhedron.
#
# More precisely, the following is done:
# - a linear system is read from an LP file
# - we compute the H-description of the corresponding polyhedron
# - the integer points (lattice points) in Minkowski sum of the finite
# part of the H-description plus the parallelotope given by the generators
# of the recession cone are generated
# - the facets of the convex hull of these integer points are computed
#
# The script is intended for people that want to see the facets for
# problems for which they know an LP-relaxation. Usually, the
# LP-relaxation can be generated by hand or a modelling language like
# ZIMPL. This script (and polymake) does the rest.
#
# Note that the script assumes that all variables are integer. To
# handle mixed-integer problems one needs to do a projection step
# first. This would be interesting to implement.
#
#
# @synopsis integer_hull_unb <lp file>
#
# @reading <lp-file>
# @writing FACETS AFFINE_HULL
#
# @author Marc Pfetsch
# @date 03/2012
use application 'polytope';
die "usage: polymake --script integer_hull_unb <lp file>\n" unless @ARGV;
# read file
my $f = lp2poly("$ARGV[0]", create_lp=>true);
printf("Read file <%s>.\n", $ARGV[0]);
# get bool array that indicates whether the variables are integer
my @a = $f->LP->get_attachment("INTEGER_VARIABLES");
# test whether all variables are integer
for (my $j = 0; $j <= $#a; ++$j)
{
if ( $a[$j] eq "false" )
{
print $a[$j]."\n";
warn_print("Not all variables are integer.\n");
exit;
}
}
printf("All variables are integral.\n");
# convert to rational polytope
my $pin = new Polytope<Rational>($f);
# ---------------------------------------------------
# treat unbounded part
# get rays, i.e., vertices that define unbounded part
my $rays = $pin->VERTICES->minor($pin->FAR_FACE, All);
print "\nRays of input:\n";
print $rays;
print "\n";
# loop through rays
my $zero = unit_vector<Rational>($pin->DIM + 1, 0);
my $B = new Polytope<Rational>(POINTS=>$zero);
foreach my $r (@$rays)
{
my $M = new Matrix<Rational>(primitive($r));
# convert ray to a point
$M->[0]->[0] = 1;
$M = $M / $zero;
my $ptemp = new Polytope<Rational>(POINTS=>$M);
$B = minkowski_sum($B, $ptemp);
}
print "\n[0,1] * rays:\n";
print $B->VERTICES;
print "\n";
# get bounded part
my $boundedvert = $pin->VERTICES->minor($pin->BOUNDED_VERTICES, All);
my $boundedpart = new Polytope<Rational>(POINTS=>$boundedvert);
# create new polytope
my $p = minkowski_sum($boundedpart, $B);
# compute integer points (uncomment to prefer client integer_points_bbox)
# prefer_now "bbox";
my $lp = $p->LATTICE_POINTS;
# get number of lattice points
print "Number of integer (lattice) points: ";
print $lp->rows;
print "\n";
printf("Creating new polytope based on lattice points.\n");
# put lattice points together with rays
my $newpoints = new Matrix<Rational>($lp) / $rays;
# create new polytope that has the lattice points as points
my $q=new Polytope(POINTS=>$newpoints, COORDINATE_LABELS=>$pin->COORDINATE_LABELS);
# output facets of integer hull
print "Number of facets: ";
print $q->N_FACETS;
print "\n";
# print_constraints($i);
return $q;
|
