Lines Matching refs:simplex
23 void addInequality(SimplexBase &simplex, ArrayRef<int64_t> coeffs) { in addInequality() argument
24 simplex.addInequality(getDynamicAPIntVec(coeffs)); in addInequality()
26 void addEquality(SimplexBase &simplex, ArrayRef<int64_t> coeffs) { in addEquality() argument
27 simplex.addEquality(getDynamicAPIntVec(coeffs)); in addEquality()
29 bool isRedundantInequality(Simplex &simplex, ArrayRef<int64_t> coeffs) { in isRedundantInequality() argument
30 return simplex.isRedundantInequality(getDynamicAPIntVec(coeffs)); in isRedundantInequality()
32 bool isRedundantInequality(LexSimplex &simplex, ArrayRef<int64_t> coeffs) { in isRedundantInequality() argument
33 return simplex.isRedundantInequality(getDynamicAPIntVec(coeffs)); in isRedundantInequality()
35 bool isRedundantEquality(Simplex &simplex, ArrayRef<int64_t> coeffs) { in isRedundantEquality() argument
36 return simplex.isRedundantEquality(getDynamicAPIntVec(coeffs)); in isRedundantEquality()
38 bool isSeparateInequality(LexSimplex &simplex, ArrayRef<int64_t> coeffs) { in isSeparateInequality() argument
39 return simplex.isSeparateInequality(getDynamicAPIntVec(coeffs)); in isSeparateInequality()
42 Simplex::IneqType findIneqType(Simplex &simplex, ArrayRef<int64_t> coeffs) { in findIneqType() argument
43 return simplex.findIneqType(getDynamicAPIntVec(coeffs)); in findIneqType()
52 Simplex simplex(2); in TEST() local
54 addInequality(simplex, {1, -1, 0}); in TEST()
55 ASSERT_FALSE(simplex.isEmpty()); in TEST()
57 unsigned snapshot = simplex.getSnapshot(); in TEST()
59 addInequality(simplex, {-1, 1, -1}); in TEST()
60 ASSERT_TRUE(simplex.isEmpty()); in TEST()
62 unsigned snapshot2 = simplex.getSnapshot(); in TEST()
64 addInequality(simplex, {-1, 1, -3}); in TEST()
65 ASSERT_TRUE(simplex.isEmpty()); in TEST()
67 simplex.rollback(snapshot2); in TEST()
68 ASSERT_TRUE(simplex.isEmpty()); in TEST()
70 simplex.rollback(snapshot); in TEST()
71 ASSERT_FALSE(simplex.isEmpty()); in TEST()
77 Simplex simplex(1); in TEST() local
78 addInequality(simplex, {1, -1}); // x >= 1. in TEST()
79 ASSERT_FALSE(simplex.isEmpty()); in TEST()
80 addEquality(simplex, {1, 0}); // x == 0. in TEST()
81 EXPECT_TRUE(simplex.isEmpty()); in TEST()
84 void expectInequalityMakesSetEmpty(Simplex &simplex, ArrayRef<int64_t> coeffs, in expectInequalityMakesSetEmpty() argument
86 ASSERT_FALSE(simplex.isEmpty()); in expectInequalityMakesSetEmpty()
87 unsigned snapshot = simplex.getSnapshot(); in expectInequalityMakesSetEmpty()
88 addInequality(simplex, coeffs); in expectInequalityMakesSetEmpty()
89 EXPECT_EQ(simplex.isEmpty(), expect); in expectInequalityMakesSetEmpty()
90 simplex.rollback(snapshot); in expectInequalityMakesSetEmpty()
94 Simplex simplex(3); in TEST() local
105 unsigned snapshot = simplex.getSnapshot(); in TEST()
107 expectInequalityMakesSetEmpty(simplex, checkCoeffs[0], false); in TEST()
108 expectInequalityMakesSetEmpty(simplex, checkCoeffs[1], false); in TEST()
111 addInequality(simplex, coeffs[(run + i) % 4]); in TEST()
113 expectInequalityMakesSetEmpty(simplex, checkCoeffs[0], true); in TEST()
114 expectInequalityMakesSetEmpty(simplex, checkCoeffs[1], true); in TEST()
116 simplex.rollback(snapshot); in TEST()
117 EXPECT_EQ(simplex.getNumConstraints(), 0u); in TEST()
119 expectInequalityMakesSetEmpty(simplex, checkCoeffs[0], false); in TEST()
120 expectInequalityMakesSetEmpty(simplex, checkCoeffs[1], false); in TEST()
127 Simplex simplex(nDim); in simplexFromConstraints() local
129 addInequality(simplex, ineq); in simplexFromConstraints()
131 addEquality(simplex, eq); in simplexFromConstraints()
132 return simplex; in simplexFromConstraints()
263 Simplex simplex(0); in TEST() local
264 addInequality(simplex, {0}); // 0 >= 0. in TEST()
266 simplex.detectRedundant(); in TEST()
267 ASSERT_FALSE(simplex.isEmpty()); in TEST()
268 EXPECT_TRUE(simplex.isMarkedRedundant(0)); in TEST()
272 Simplex simplex(0); in TEST() local
273 addEquality(simplex, {0}); // 0 == 0. in TEST()
274 simplex.detectRedundant(); in TEST()
275 ASSERT_FALSE(simplex.isEmpty()); in TEST()
276 EXPECT_TRUE(simplex.isMarkedRedundant(0)); in TEST()
280 Simplex simplex(1); in TEST() local
281 addEquality(simplex, {1, 0}); // x == 0. in TEST()
283 simplex.detectRedundant(); in TEST()
284 ASSERT_FALSE(simplex.isEmpty()); in TEST()
285 EXPECT_FALSE(simplex.isMarkedRedundant(0)); in TEST()
289 Simplex simplex(1); in TEST() local
290 addEquality(simplex, {0, 0}); // 0x == 0. in TEST()
291 simplex.detectRedundant(); in TEST()
292 ASSERT_FALSE(simplex.isEmpty()); in TEST()
293 EXPECT_TRUE(simplex.isMarkedRedundant(0)); in TEST()
297 Simplex simplex(1); in TEST() local
298 addEquality(simplex, {-1, 0}); // -x == 0. in TEST()
299 simplex.detectRedundant(); in TEST()
300 ASSERT_FALSE(simplex.isEmpty()); in TEST()
301 EXPECT_FALSE(simplex.isMarkedRedundant(0)); in TEST()
305 Simplex simplex(1); in TEST() local
306 addInequality(simplex, {1, 0}); // x >= 0. in TEST()
307 simplex.detectRedundant(); in TEST()
308 ASSERT_FALSE(simplex.isEmpty()); in TEST()
309 EXPECT_FALSE(simplex.isMarkedRedundant(0)); in TEST()
313 Simplex simplex(1); in TEST() local
314 addInequality(simplex, {0, 0}); // 0x >= 0. in TEST()
315 simplex.detectRedundant(); in TEST()
316 ASSERT_FALSE(simplex.isEmpty()); in TEST()
317 EXPECT_TRUE(simplex.isMarkedRedundant(0)); in TEST()
321 Simplex simplex(1); in TEST() local
322 addInequality(simplex, {-1, 0}); // x <= 0. in TEST()
323 simplex.detectRedundant(); in TEST()
324 ASSERT_FALSE(simplex.isEmpty()); in TEST()
325 EXPECT_FALSE(simplex.isMarkedRedundant(0)); in TEST()
331 Simplex simplex(3); in TEST() local
333 addEquality(simplex, {-1, 0, 1, 0}); // u = w. in TEST()
334 addInequality(simplex, {-1, 16, 0, 15}); // 15 - (u - 16v) >= 0. in TEST()
335 addInequality(simplex, {1, -16, 0, 0}); // (u - 16v) >= 0. in TEST()
337 simplex.detectRedundant(); in TEST()
338 ASSERT_FALSE(simplex.isEmpty()); in TEST()
340 for (unsigned i = 0; i < simplex.getNumConstraints(); ++i) in TEST()
341 EXPECT_FALSE(simplex.isMarkedRedundant(i)) << "i = " << i << "\n"; in TEST()
345 Simplex simplex(3); in TEST() local
348 addInequality(simplex, {0, -1, 0, 1}); // [0]: y <= 1. in TEST()
349 addInequality(simplex, {-1, 0, 8, 7}); // [1]: 8z >= x - 7. in TEST()
350 addInequality(simplex, {1, 0, -8, 0}); // [2]: 8z <= x. in TEST()
351 addInequality(simplex, {0, 1, 0, 0}); // [3]: y >= 0. in TEST()
352 addInequality(simplex, {-1, 0, 8, 7}); // [4]: 8z >= 7 - x. in TEST()
353 addInequality(simplex, {1, 0, -8, 0}); // [5]: 8z <= x. in TEST()
354 addInequality(simplex, {0, 1, 0, 0}); // [6]: y >= 0. in TEST()
355 addInequality(simplex, {0, -1, 0, 1}); // [7]: y <= 1. in TEST()
357 simplex.detectRedundant(); in TEST()
358 ASSERT_FALSE(simplex.isEmpty()); in TEST()
360 EXPECT_EQ(simplex.isMarkedRedundant(0), true); in TEST()
361 EXPECT_EQ(simplex.isMarkedRedundant(1), true); in TEST()
362 EXPECT_EQ(simplex.isMarkedRedundant(2), true); in TEST()
363 EXPECT_EQ(simplex.isMarkedRedundant(3), true); in TEST()
364 EXPECT_EQ(simplex.isMarkedRedundant(4), false); in TEST()
365 EXPECT_EQ(simplex.isMarkedRedundant(5), false); in TEST()
366 EXPECT_EQ(simplex.isMarkedRedundant(6), false); in TEST()
367 EXPECT_EQ(simplex.isMarkedRedundant(7), false); in TEST()
371 Simplex simplex(3); in TEST() local
372 addInequality(simplex, {0, -1, 0, 1}); // [0]: y <= 1. in TEST()
373 addInequality(simplex, {1, 0, 0, -1}); // [1]: x >= 1. in TEST()
374 addInequality(simplex, {-1, 0, 0, 2}); // [2]: x <= 2. in TEST()
375 addInequality(simplex, {-1, 0, 2, 7}); // [3]: 2z >= x - 7. in TEST()
376 addInequality(simplex, {1, 0, -2, 0}); // [4]: 2z <= x. in TEST()
377 addInequality(simplex, {0, 1, 0, 0}); // [5]: y >= 0. in TEST()
378 addInequality(simplex, {0, 1, -2, 1}); // [6]: y >= 2z - 1. in TEST()
379 addInequality(simplex, {-1, 1, 0, 1}); // [7]: y >= x - 1. in TEST()
381 simplex.detectRedundant(); in TEST()
382 ASSERT_FALSE(simplex.isEmpty()); in TEST()
389 EXPECT_FALSE(simplex.isMarkedRedundant(0)); in TEST()
390 EXPECT_FALSE(simplex.isMarkedRedundant(1)); in TEST()
391 EXPECT_TRUE(simplex.isMarkedRedundant(2)); in TEST()
392 EXPECT_FALSE(simplex.isMarkedRedundant(3)); in TEST()
393 EXPECT_FALSE(simplex.isMarkedRedundant(4)); in TEST()
394 EXPECT_TRUE(simplex.isMarkedRedundant(5)); in TEST()
395 EXPECT_TRUE(simplex.isMarkedRedundant(6)); in TEST()
396 EXPECT_FALSE(simplex.isMarkedRedundant(7)); in TEST()
400 Simplex simplex(3); // Variables are x, y, N. in TEST() local
401 addInequality(simplex, {1, 0, 0, 0}); // [0]: x >= 0. in TEST()
402 addInequality(simplex, {-32, 0, 1, -1}); // [1]: 32x <= N - 1. in TEST()
403 addInequality(simplex, {0, 1, 0, 0}); // [2]: y >= 0. in TEST()
404 addInequality(simplex, {-32, 1, 0, 0}); // [3]: y >= 32x. in TEST()
405 addInequality(simplex, {32, -1, 0, 31}); // [4]: y <= 32x + 31. in TEST()
406 addInequality(simplex, {0, -1, 1, -1}); // [5]: y <= N - 1. in TEST()
409 simplex.detectRedundant(); in TEST()
410 EXPECT_FALSE(simplex.isMarkedRedundant(0)); in TEST()
411 EXPECT_TRUE(simplex.isMarkedRedundant(1)); in TEST()
412 EXPECT_TRUE(simplex.isMarkedRedundant(2)); in TEST()
413 EXPECT_FALSE(simplex.isMarkedRedundant(3)); in TEST()
414 EXPECT_FALSE(simplex.isMarkedRedundant(4)); in TEST()
415 EXPECT_FALSE(simplex.isMarkedRedundant(5)); in TEST()
419 Simplex simplex(2); in TEST() local
420 addInequality(simplex, {-1, 0, -1}); // x <= -1. in TEST()
421 unsigned snapshot = simplex.getSnapshot(); in TEST()
423 addInequality(simplex, {-1, 0, -2}); // x <= -2. in TEST()
424 addInequality(simplex, {-3, 0, -6}); in TEST()
431 simplex.detectRedundant(); in TEST()
435 simplex.rollback(snapshot); in TEST()
436 MaybeOptimum<Fraction> maxX = simplex.computeOptimum( in TEST()
442 Simplex simplex(1); in TEST() local
443 addInequality(simplex, {1, -1}); // x >= 1. in TEST()
444 addInequality(simplex, {1, 0}); // x >= 0. in TEST()
445 simplex.detectRedundant(); in TEST()
446 ASSERT_FALSE(simplex.isEmpty()); in TEST()
447 EXPECT_FALSE(simplex.isMarkedRedundant(0)); in TEST()
448 EXPECT_TRUE(simplex.isMarkedRedundant(1)); in TEST()
452 Simplex simplex(1); in TEST() local
454 unsigned snapshot1 = simplex.getSnapshot(); in TEST()
455 simplex.appendVariable(); in TEST()
456 simplex.appendVariable(0); in TEST()
457 EXPECT_EQ(simplex.getNumVariables(), 2u); in TEST()
460 addInequality(simplex, {0, 1, -yMin}); // y >= 2. in TEST()
461 addInequality(simplex, {0, -1, yMax}); // y <= 5. in TEST()
463 unsigned snapshot2 = simplex.getSnapshot(); in TEST()
464 simplex.appendVariable(2); in TEST()
465 EXPECT_EQ(simplex.getNumVariables(), 4u); in TEST()
466 simplex.rollback(snapshot2); in TEST()
468 EXPECT_EQ(simplex.getNumVariables(), 2u); in TEST()
469 EXPECT_EQ(simplex.getNumConstraints(), 2u); in TEST()
470 EXPECT_EQ(simplex.computeIntegerBounds(getDynamicAPIntVec({0, 1, 0})), in TEST()
474 simplex.rollback(snapshot1); in TEST()
475 EXPECT_EQ(simplex.getNumVariables(), 1u); in TEST()
476 EXPECT_EQ(simplex.getNumConstraints(), 0u); in TEST()
480 Simplex simplex(2); in TEST() local
481 addInequality(simplex, {0, -1, 2}); // y <= 2. in TEST()
482 addInequality(simplex, {1, 0, 0}); // x >= 0. in TEST()
483 addEquality(simplex, {-1, 1, 0}); // y = x. in TEST()
485 EXPECT_TRUE(isRedundantInequality(simplex, {-1, 0, 2})); // x <= 2. in TEST()
486 EXPECT_TRUE(isRedundantInequality(simplex, {0, 1, 0})); // y >= 0. in TEST()
488 EXPECT_FALSE(isRedundantInequality(simplex, {-1, 0, -1})); // x <= -1. in TEST()
489 EXPECT_FALSE(isRedundantInequality(simplex, {0, 1, -2})); // y >= 2. in TEST()
490 EXPECT_FALSE(isRedundantInequality(simplex, {0, 1, -1})); // y >= 1. in TEST()
494 Simplex simplex(2); in TEST() local
495 addInequality(simplex, {0, -1, 2}); // y <= 2. in TEST()
496 addInequality(simplex, {1, 0, 0}); // x >= 0. in TEST()
497 addEquality(simplex, {-1, 1, 0}); // y = x. in TEST()
499 EXPECT_EQ(findIneqType(simplex, {-1, 0, 2}), in TEST()
501 EXPECT_EQ(findIneqType(simplex, {0, 1, 0}), in TEST()
504 EXPECT_EQ(findIneqType(simplex, {0, 1, -1}), in TEST()
506 EXPECT_EQ(findIneqType(simplex, {-1, 0, 1}), in TEST()
508 EXPECT_EQ(findIneqType(simplex, {0, 1, -2}), in TEST()
511 EXPECT_EQ(findIneqType(simplex, {-1, 0, -1}), in TEST()
516 Simplex simplex(2); in TEST() local
517 addInequality(simplex, {0, -1, 2}); // y <= 2. in TEST()
518 addInequality(simplex, {1, 0, 0}); // x >= 0. in TEST()
519 addEquality(simplex, {-1, 1, 0}); // y = x. in TEST()
521 EXPECT_TRUE(isRedundantEquality(simplex, {-1, 1, 0})); // y = x. in TEST()
522 EXPECT_TRUE(isRedundantEquality(simplex, {1, -1, 0})); // x = y. in TEST()
524 EXPECT_FALSE(isRedundantEquality(simplex, {0, 1, -1})); // y = 1. in TEST()
526 addEquality(simplex, {0, -1, 2}); // y = 2. in TEST()
528 EXPECT_TRUE(isRedundantEquality(simplex, {-1, 0, 2})); // x = 2. in TEST()
571 Simplex simplex(/*nVar=*/1); in TEST() local
572 simplex.addDivisionVariable(getDynamicAPIntVec({1, 0}), DynamicAPInt(2)); in TEST()
573 addInequality(simplex, {1, 0, -3}); // x >= 3. in TEST()
574 addInequality(simplex, {-1, 0, 9}); // x <= 9. in TEST()
576 simplex.findIntegerSample(); in TEST()
582 LexSimplex simplex(/*nVar=*/1); in TEST() local
583 addInequality(simplex, {2, -1}); // x >= 1/2. in TEST()
586 EXPECT_TRUE(isRedundantInequality(simplex, {3, -2})); in TEST()
587 EXPECT_FALSE(isSeparateInequality(simplex, {3, -2})); in TEST()
590 EXPECT_FALSE(isRedundantInequality(simplex, {-3, 2})); in TEST()
591 EXPECT_TRUE(isSeparateInequality(simplex, {-3, 2})); in TEST()
594 EXPECT_FALSE(isRedundantInequality(simplex, {-1, 1})); in TEST()
595 EXPECT_FALSE(isSeparateInequality(simplex, {-1, 1})); in TEST()