Frobby 0.9.5
OptimizeStrategyTest.cpp
Go to the documentation of this file.
1/* Frobby: Software for monomial ideal computations.
2 Copyright (C) 2009 Bjarke Hammersholt Roune (www.broune.com)
3
4 This program is free software; you can redistribute it and/or modify
5 it under the terms of the GNU General Public License as published by
6 the Free Software Foundation; either version 2 of the License, or
7 (at your option) any later version.
8
9 This program is distributed in the hope that it will be useful,
10 but WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 GNU General Public License for more details.
13
14 You should have received a copy of the GNU General Public License
15 along with this program. If not, see http://www.gnu.org/licenses/.
16*/
17#include "stdinc.h"
18#include "OptimizeStrategy.h"
19#include "tests.h"
20
21#include "IdealFactory.h"
22#include "Ideal.h"
23#include "TermTranslator.h"
24#include "TermGrader.h"
25#include "SplitStrategy.h"
26#include "Slice.h"
27
28#include <vector>
29
30// This whole thing was exceedingly hard to get right, which is why
31// there are so many tests here.
32
35
36namespace {
37 vector<mpz_class> makeVector(mpz_class a, mpz_class b, mpz_class c, mpz_class d) {
38 vector<mpz_class> vec(4);
39 vec[0] = a;
40 vec[1] = b;
41 vec[2] = c;
42 vec[3] = d;
43 return vec;
44 }
45}
46
48 Ideal ideal;
50 TermGrader grader(makeVector(0, 100, 10000, mpz_class("300000000000000007")), translator);
53 (grader, splitStrategy.get(), false,
55 strategy.run(ideal);
56
57 ASSERT_EQ(strategy.getMaximalSolutions(), Ideal(Term("1 1 2 1")));
58 ASSERT_EQ(strategy.getMaximalValue(), mpz_class("300000000000020107"));
59}
60
66 (grader, splitStrategy.get(), true,
68
69 // Case 1 from the documentation.
70 ASSERT_TRUE(opt.changedInWayRelevantToBound
71 (Term("0 0 0 0"), Term("0 2 0 0"),
72 Term("0 1 0 0"), Term("0 2 0 0")));
73
74 // Case 2 from the documentation.
75 ASSERT_TRUE(opt.changedInWayRelevantToBound
76 (Term("0 0 0 0"), Term("0 10 0 0"),
77 Term("0 0 0 0"), Term("0 9 0 0")));
78
79 // Case 3 from the documentation.
80 ASSERT_TRUE(opt.changedInWayRelevantToBound
81 (Term("0 0 0 0"), Term("9 0 0 0"),
82 Term("0 0 0 0"), Term("8 0 0 0")));
83
84 // Case 4 from the documentation.
85 ASSERT_TRUE(opt.changedInWayRelevantToBound
86 (Term(" 9 0 0 0"), Term("10 0 0 0"),
87 Term("10 0 0 0"), Term("10 0 0 0")));
88
89 // Nothing changed.
90 ASSERT_FALSE(opt.changedInWayRelevantToBound
91 (Term("0 0 0 0"), Term("0 0 0 0"),
92 Term("0 0 0 0"), Term("0 0 0 0")));
93
94 // No case applies.
95 ASSERT_FALSE(opt.changedInWayRelevantToBound
96 (Term("1 2 3 3"), Term("10 9 10 9"),
97 Term("1 2 4 4"), Term(" 9 5 9 4")));
98}
99
100#define INNER_SIMP_TEST(strat, div, dom, degree, expectPivot) \
101 { \
102 Term gotPivot(Term(expectPivot).getVarCount()); \
103 bool expectSimplify = !Term(expectPivot).isIdentity(); \
104 ASSERT_EQ(strat.getInnerSimplify \
105 (Term(div), Term(dom), degree, gotPivot), \
106 expectSimplify); \
107 if (expectSimplify) { \
108 ASSERT_EQ(gotPivot, Term(expectPivot)); \
109 } \
110 }
111
112#define OUTER_SIMP_TEST(strat, div, dom, degree, expectPivot) \
113 { \
114 Term gotPivot(Term(expectPivot).getVarCount()); \
115 bool expectSimplify = !Term(expectPivot).isIdentity(); \
116 ASSERT_EQ(strat.getOuterSimplify \
117 (Term(div), Term(dom), degree, gotPivot), \
118 expectSimplify); \
119 if (expectSimplify) { \
120 ASSERT_EQ(gotPivot, Term(expectPivot)); \
121 } \
122 }
123
126 TermGrader grader(makeVector(100, 10, 1, 0), translator);
128
129 OptimizeStrategy all // Report all optimal solutions.
130 (grader, splitStrategy.get(), true,
132 OptimizeStrategy one // Report one optimal solution.
133 (grader, splitStrategy.get(), false,
135
137 all.consume(Term("1 2 3 4"));
138 ASSERT_EQ(all.getMaximalValue(), mpz_class("123"));
139
140 one.beginConsuming();
141 one.consume(Term("1 2 3 4"));
142 ASSERT_EQ(one.getMaximalValue(), mpz_class("123"));
143
144 // No improvement.
145 INNER_SIMP_TEST(all, "1 2 3 4", "1 2 4 4", 124, "0 0 0 0");
146 INNER_SIMP_TEST(one, "1 2 4 4", "1 2 5 4", 125, "0 0 0 0");
147
148 // Improvement depends on reporting.
149 INNER_SIMP_TEST(all, "1 2 1 1", "1 2 5 1", 125, "0 0 2 0");
150 INNER_SIMP_TEST(one, "1 2 1 1", "1 2 5 1", 125, "0 0 3 0");
151
152 // Improvement in more than one variable, varying with reporting.
153 INNER_SIMP_TEST(all, "1 0 0 4", "1 2 4 8", 124, "0 2 3 0");
154 INNER_SIMP_TEST(one, "1 0 0 4", "1 2 4 9", 124, "0 2 4 0");
155
156 // Improvement due to 10 mapping to zero.
157 OUTER_SIMP_TEST(all, "1 2 3 4", "1 10 3 4", 193, "0 8 0 0");
158 OUTER_SIMP_TEST(one, "1 2 3 4", "1 10 3 4", 193, "0 8 0 0");
159
160 // No improvement as 10 to zero does not get below bound.
161 OUTER_SIMP_TEST(all, "2 2 3 4", "2 10 3 4", 293, "0 0 0 0");
162 OUTER_SIMP_TEST(one, "2 2 3 4", "2 10 3 4", 293, "0 0 0 0");
163
164 // Regressions, i.e. tests that capture past actual bugs.
165 INNER_SIMP_TEST(one, "1 2 0 1", "1 2 10 1", 129, "0 0 4 0");
166}
167
170 TermGrader grader(makeVector(-100, -10, -1, 0), translator);
172
173 OptimizeStrategy all // Report all optimal solutions.
174 (grader, splitStrategy.get(), true,
176 OptimizeStrategy one // Report one optimal solution.
177 (grader, splitStrategy.get(), false,
179
181 all.consume(Term("1 2 3 4"));
182 ASSERT_EQ(all.getMaximalValue(), mpz_class("-123"));
183
184 one.beginConsuming();
185 one.consume(Term("1 2 3 4"));
186 ASSERT_EQ(one.getMaximalValue(), mpz_class("-123"));
187
188 // No improvement.
189 OUTER_SIMP_TEST(all, "1 2 3 4", "1 2 3 4", -123, "0 0 0 0");
190 OUTER_SIMP_TEST(one, "1 2 2 4", "1 2 2 4", -122, "0 0 0 0");
191
192 // Improvement depends on reporting one or all.
193 OUTER_SIMP_TEST(all, "1 2 2 4", "1 2 3 5", -122, "0 0 0 0");
194 OUTER_SIMP_TEST(one, "1 2 2 4", "1 2 3 5", -122, "0 0 1 0");
195
196 // Improvement in more than one variable, only see the first.
197 OUTER_SIMP_TEST(all, "1 2 1 4", "1 5 5 7", -121, "0 1 0 0");
198 OUTER_SIMP_TEST(one, "1 2 1 4", "1 5 5 7", -121, "0 1 0 0");
199
200
201 // Improvement due to 10 mapping to zero.
202 INNER_SIMP_TEST(all, "1 5 3 4", "1 10 3 4", -103, "0 5 0 0");
203 INNER_SIMP_TEST(one, "1 5 2 4", "1 10 2 4", -103, "0 5 0 0");
204
205 // No improvement as 10 to zero is not necessary to get below bound.
206 INNER_SIMP_TEST(all, "10 5 3 4", "10 10 3 4", -3, "0 0 0 0");
207 INNER_SIMP_TEST(one, "10 5 2 4", "10 10 2 4", -3, "0 0 0 0");
208
209 // No improvement due to zero both at 0 and 10.
210 INNER_SIMP_TEST(all, "1 0 3 4", "1 10 3 4", -103, "0 0 0 0");
211 INNER_SIMP_TEST(one, "1 0 2 4", "1 10 2 4", -103, "0 0 0 0");
212}
void nameFactoryRegister(NameFactory< AbstractProduct > &factory)
Registers the string returned by ConcreteProduct::getStaticName() to a function that default-construc...
#define INNER_SIMP_TEST(strat, div, dom, degree, expectPivot)
#define OUTER_SIMP_TEST(strat, div, dom, degree, expectPivot)
#define ASSERT_TRUE(VALUE)
Definition asserts.h:72
#define ASSERT_EQ(A, B)
Definition asserts.h:147
#define ASSERT_FALSE(VALUE)
Definition asserts.h:119
static BigIdeal xx_yy_zz_t_xz_yz()
Returns .
Represents a monomial ideal with int exponents.
Definition Ideal.h:27
OptimizeStrategy optimizes a function on the maximal standard monomials of a monomial ideal using bra...
@ UseBoundToEliminateAndSimplify
Eliminate non-improving slices and simplify slices by trying to generate non-improving slices that ar...
virtual void beginConsuming()
Tell the consumer to begin consuming an ideal.
This class describes the interface of a strategy object for the Slice Algorithm.
static auto_ptr< SplitStrategy > createStrategy(const string &prefix)
Returns the strategy whose name has the given prefix.
A TermGrader assigns a value, the degree, to each monomial.
Definition TermGrader.h:27
TermTranslator handles translation between terms whose exponents are infinite precision integers and ...
Term represents a product of variables which does not include a coefficient.
Definition Term.h:49
#define TEST_SUITE2(PARENT, SUITE)
Definition macroes.h:28
#define TEST(SUITE, TEST_NAME)
Definition macroes.h:41
#define TEST_SUITE(SUITE)
Definition macroes.h:26