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
|
# Copyright (c) 1997-2018
# Ewgenij Gawrilow, Michael Joswig (Technische Universitaet Berlin, Germany)
# http://www.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.
#-------------------------------------------------------------------------------
CREDIT tosimplex
Dual simplex algorithm implemented by Thomas Opfer
# @category Optimization
# Dual simplex algorithm implemented by Thomas Opfer
label to
object Polytope {
sub run_to_solve {
my ($this, $sense)=@_;
my %opts;
if (defined( my $ov=$this->lookup("ONE_VERTEX") )) {
my $ineq=$this->give("FACETS | INEQUALITIES");
if (defined( my $eq=$this->lookup("AFFINE_HULL | EQUATIONS") )) {
$ineq = $ineq / $eq;
}
my $s = new SparseVector<Scalar>($ineq*$ov);
my $set = sequence(0, $ineq->rows())-indices($s);
my $ind = basis_rows($ineq->minor($set, All));
if ($ineq->cols()-1 == $ind->size()) {
my $basis = new Set();
my $i = 0;
foreach (@$set) {
if ($ind->contains($i)) {
$basis+=$_;
}
++$i;
}
$opts{initial_basis}=$basis;
}
}
to_solve_lp($this, $this->LP, $sense, \%opts);
}
rule to.simplex: LP.MAXIMAL_VALUE, LP.MAXIMAL_VERTEX, FEASIBLE : LP.LINEAR_OBJECTIVE, FACETS | INEQUALITIES {
run_to_solve($this, 1);
}
weight 3.30;
rule to.simplex: LP.MINIMAL_VALUE, LP.MINIMAL_VERTEX, FEASIBLE : LP.LINEAR_OBJECTIVE, FACETS | INEQUALITIES {
run_to_solve($this, 0);
}
weight 3.30;
}
# this is overridden in bundled:cdd for Rational and Float coordinate types
function H_input_is_bounded(Polytope) {
to_input_bounded($_[0]);
}
# Local Variables:
# mode: perl
# cperl-indent-level:3
# indent-tabs-mode:nil
# End:
|
