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
|
# 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
#
# Script to generate the integer hull arising from a given LP file,
# i.e., the convex hull of all lattice points in the polytope given by
# the file is computed.
#
# More precisely, the following is done:
# - a linear system is read from an LP file
# - the integer points (lattice points) in the LP-relaxation are generated
# - the facets of the convex hull of these integer points are computed
# - the corresponding polytope is returned
#
# 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. Furthermore, the
# input needs to be bounded.
#
#
# @synopsis integer_hull <lp file>
#
# @reading <lp-file>
# @writing FACETS AFFINE_HULL
#
# @author Marc Pfetsch
# @date 02/2012
use application 'polytope';
die "usage: polymake --script integer_hull <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 $p = new Polytope<Rational>($f);
# 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");
# create new polytope that has the lattice points as points
my $q=new Polytope(POINTS=>$lp, COORDINATE_LABELS=>$p->COORDINATE_LABELS);
# output facets of integer hull
print "Number of facets: ";
print $q->N_FACETS;
print "\n";
# print_constraints($i);
return $q;
|
