Lines Matching refs:simplex
26 Simplex simplex(2); in TEST() local
28 simplex.addInequality({1, -1, 0}); in TEST()
29 ASSERT_FALSE(simplex.isEmpty()); in TEST()
31 unsigned snapshot = simplex.getSnapshot(); in TEST()
33 simplex.addInequality({-1, 1, -1}); in TEST()
34 ASSERT_TRUE(simplex.isEmpty()); in TEST()
36 unsigned snapshot2 = simplex.getSnapshot(); in TEST()
38 simplex.addInequality({-1, 1, -3}); in TEST()
39 ASSERT_TRUE(simplex.isEmpty()); in TEST()
41 simplex.rollback(snapshot2); in TEST()
42 ASSERT_TRUE(simplex.isEmpty()); in TEST()
44 simplex.rollback(snapshot); in TEST()
45 ASSERT_FALSE(simplex.isEmpty()); in TEST()
51 Simplex simplex(1); in TEST() local
52 simplex.addInequality({1, -1}); // x >= 1. in TEST()
53 ASSERT_FALSE(simplex.isEmpty()); in TEST()
54 simplex.addEquality({1, 0}); // x == 0. in TEST()
55 EXPECT_TRUE(simplex.isEmpty()); in TEST()
58 void expectInequalityMakesSetEmpty(Simplex &simplex, ArrayRef<int64_t> coeffs, in expectInequalityMakesSetEmpty() argument
60 ASSERT_FALSE(simplex.isEmpty()); in expectInequalityMakesSetEmpty()
61 unsigned snapshot = simplex.getSnapshot(); in expectInequalityMakesSetEmpty()
62 simplex.addInequality(coeffs); in expectInequalityMakesSetEmpty()
63 EXPECT_EQ(simplex.isEmpty(), expect); in expectInequalityMakesSetEmpty()
64 simplex.rollback(snapshot); in expectInequalityMakesSetEmpty()
68 Simplex simplex(3); in TEST() local
79 unsigned snapshot = simplex.getSnapshot(); in TEST()
81 expectInequalityMakesSetEmpty(simplex, checkCoeffs[0], false); in TEST()
82 expectInequalityMakesSetEmpty(simplex, checkCoeffs[1], false); in TEST()
85 simplex.addInequality(coeffs[(run + i) % 4]); in TEST()
87 expectInequalityMakesSetEmpty(simplex, checkCoeffs[0], true); in TEST()
88 expectInequalityMakesSetEmpty(simplex, checkCoeffs[1], true); in TEST()
90 simplex.rollback(snapshot); in TEST()
91 EXPECT_EQ(simplex.getNumConstraints(), 0u); in TEST()
93 expectInequalityMakesSetEmpty(simplex, checkCoeffs[0], false); in TEST()
94 expectInequalityMakesSetEmpty(simplex, checkCoeffs[1], false); in TEST()
101 Simplex simplex(nDim); in simplexFromConstraints() local
103 simplex.addInequality(ineq); in simplexFromConstraints()
105 simplex.addEquality(eq); in simplexFromConstraints()
106 return simplex; in simplexFromConstraints()
237 Simplex simplex(0); in TEST() local
238 simplex.addInequality({0}); // 0 >= 0. in TEST()
240 simplex.detectRedundant(); in TEST()
241 ASSERT_FALSE(simplex.isEmpty()); in TEST()
242 EXPECT_TRUE(simplex.isMarkedRedundant(0)); in TEST()
246 Simplex simplex(0); in TEST() local
247 simplex.addEquality({0}); // 0 == 0. in TEST()
248 simplex.detectRedundant(); in TEST()
249 ASSERT_FALSE(simplex.isEmpty()); in TEST()
250 EXPECT_TRUE(simplex.isMarkedRedundant(0)); in TEST()
254 Simplex simplex(1); in TEST() local
255 simplex.addEquality({1, 0}); // x == 0. in TEST()
257 simplex.detectRedundant(); in TEST()
258 ASSERT_FALSE(simplex.isEmpty()); in TEST()
259 EXPECT_FALSE(simplex.isMarkedRedundant(0)); in TEST()
263 Simplex simplex(1); in TEST() local
264 simplex.addEquality({0, 0}); // 0x == 0. in TEST()
265 simplex.detectRedundant(); in TEST()
266 ASSERT_FALSE(simplex.isEmpty()); in TEST()
267 EXPECT_TRUE(simplex.isMarkedRedundant(0)); in TEST()
271 Simplex simplex(1); in TEST() local
272 simplex.addEquality({-1, 0}); // -x == 0. in TEST()
273 simplex.detectRedundant(); in TEST()
274 ASSERT_FALSE(simplex.isEmpty()); in TEST()
275 EXPECT_FALSE(simplex.isMarkedRedundant(0)); in TEST()
279 Simplex simplex(1); in TEST() local
280 simplex.addInequality({1, 0}); // x >= 0. in TEST()
281 simplex.detectRedundant(); in TEST()
282 ASSERT_FALSE(simplex.isEmpty()); in TEST()
283 EXPECT_FALSE(simplex.isMarkedRedundant(0)); in TEST()
287 Simplex simplex(1); in TEST() local
288 simplex.addInequality({0, 0}); // 0x >= 0. in TEST()
289 simplex.detectRedundant(); in TEST()
290 ASSERT_FALSE(simplex.isEmpty()); in TEST()
291 EXPECT_TRUE(simplex.isMarkedRedundant(0)); in TEST()
295 Simplex simplex(1); in TEST() local
296 simplex.addInequality({-1, 0}); // x <= 0. in TEST()
297 simplex.detectRedundant(); in TEST()
298 ASSERT_FALSE(simplex.isEmpty()); in TEST()
299 EXPECT_FALSE(simplex.isMarkedRedundant(0)); in TEST()
305 Simplex simplex(3); in TEST() local
307 simplex.addEquality({-1, 0, 1, 0}); // u = w. in TEST()
308 simplex.addInequality({-1, 16, 0, 15}); // 15 - (u - 16v) >= 0. in TEST()
309 simplex.addInequality({1, -16, 0, 0}); // (u - 16v) >= 0. in TEST()
311 simplex.detectRedundant(); in TEST()
312 ASSERT_FALSE(simplex.isEmpty()); in TEST()
314 for (unsigned i = 0; i < simplex.getNumConstraints(); ++i) in TEST()
315 EXPECT_FALSE(simplex.isMarkedRedundant(i)) << "i = " << i << "\n"; in TEST()
319 Simplex simplex(3); in TEST() local
322 simplex.addInequality({0, -1, 0, 1}); // [0]: y <= 1. in TEST()
323 simplex.addInequality({-1, 0, 8, 7}); // [1]: 8z >= x - 7. in TEST()
324 simplex.addInequality({1, 0, -8, 0}); // [2]: 8z <= x. in TEST()
325 simplex.addInequality({0, 1, 0, 0}); // [3]: y >= 0. in TEST()
326 simplex.addInequality({-1, 0, 8, 7}); // [4]: 8z >= 7 - x. in TEST()
327 simplex.addInequality({1, 0, -8, 0}); // [5]: 8z <= x. in TEST()
328 simplex.addInequality({0, 1, 0, 0}); // [6]: y >= 0. in TEST()
329 simplex.addInequality({0, -1, 0, 1}); // [7]: y <= 1. in TEST()
331 simplex.detectRedundant(); in TEST()
332 ASSERT_FALSE(simplex.isEmpty()); in TEST()
334 EXPECT_EQ(simplex.isMarkedRedundant(0), true); in TEST()
335 EXPECT_EQ(simplex.isMarkedRedundant(1), true); in TEST()
336 EXPECT_EQ(simplex.isMarkedRedundant(2), true); in TEST()
337 EXPECT_EQ(simplex.isMarkedRedundant(3), true); in TEST()
338 EXPECT_EQ(simplex.isMarkedRedundant(4), false); in TEST()
339 EXPECT_EQ(simplex.isMarkedRedundant(5), false); in TEST()
340 EXPECT_EQ(simplex.isMarkedRedundant(6), false); in TEST()
341 EXPECT_EQ(simplex.isMarkedRedundant(7), false); in TEST()
345 Simplex simplex(3); in TEST() local
346 simplex.addInequality({0, -1, 0, 1}); // [0]: y <= 1. in TEST()
347 simplex.addInequality({1, 0, 0, -1}); // [1]: x >= 1. in TEST()
348 simplex.addInequality({-1, 0, 0, 2}); // [2]: x <= 2. in TEST()
349 simplex.addInequality({-1, 0, 2, 7}); // [3]: 2z >= x - 7. in TEST()
350 simplex.addInequality({1, 0, -2, 0}); // [4]: 2z <= x. in TEST()
351 simplex.addInequality({0, 1, 0, 0}); // [5]: y >= 0. in TEST()
352 simplex.addInequality({0, 1, -2, 1}); // [6]: y >= 2z - 1. in TEST()
353 simplex.addInequality({-1, 1, 0, 1}); // [7]: y >= x - 1. in TEST()
355 simplex.detectRedundant(); in TEST()
356 ASSERT_FALSE(simplex.isEmpty()); in TEST()
363 EXPECT_FALSE(simplex.isMarkedRedundant(0)); in TEST()
364 EXPECT_FALSE(simplex.isMarkedRedundant(1)); in TEST()
365 EXPECT_TRUE(simplex.isMarkedRedundant(2)); in TEST()
366 EXPECT_FALSE(simplex.isMarkedRedundant(3)); in TEST()
367 EXPECT_FALSE(simplex.isMarkedRedundant(4)); in TEST()
368 EXPECT_TRUE(simplex.isMarkedRedundant(5)); in TEST()
369 EXPECT_TRUE(simplex.isMarkedRedundant(6)); in TEST()
370 EXPECT_FALSE(simplex.isMarkedRedundant(7)); in TEST()
374 Simplex simplex(3); // Variables are x, y, N. in TEST() local
375 simplex.addInequality({1, 0, 0, 0}); // [0]: x >= 0. in TEST()
376 simplex.addInequality({-32, 0, 1, -1}); // [1]: 32x <= N - 1. in TEST()
377 simplex.addInequality({0, 1, 0, 0}); // [2]: y >= 0. in TEST()
378 simplex.addInequality({-32, 1, 0, 0}); // [3]: y >= 32x. in TEST()
379 simplex.addInequality({32, -1, 0, 31}); // [4]: y <= 32x + 31. in TEST()
380 simplex.addInequality({0, -1, 1, -1}); // [5]: y <= N - 1. in TEST()
383 simplex.detectRedundant(); in TEST()
384 EXPECT_FALSE(simplex.isMarkedRedundant(0)); in TEST()
385 EXPECT_TRUE(simplex.isMarkedRedundant(1)); in TEST()
386 EXPECT_TRUE(simplex.isMarkedRedundant(2)); in TEST()
387 EXPECT_FALSE(simplex.isMarkedRedundant(3)); in TEST()
388 EXPECT_FALSE(simplex.isMarkedRedundant(4)); in TEST()
389 EXPECT_FALSE(simplex.isMarkedRedundant(5)); in TEST()
393 Simplex simplex(2); in TEST() local
394 simplex.addInequality({-1, 0, -1}); // x <= -1. in TEST()
395 unsigned snapshot = simplex.getSnapshot(); in TEST()
397 simplex.addInequality({-1, 0, -2}); // x <= -2. in TEST()
398 simplex.addInequality({-3, 0, -6}); in TEST()
405 simplex.detectRedundant(); in TEST()
409 simplex.rollback(snapshot); in TEST()
411 simplex.computeOptimum(Simplex::Direction::Up, {1, 0, 0}); in TEST()
416 Simplex simplex(1); in TEST() local
417 simplex.addInequality({1, -1}); // x >= 1. in TEST()
418 simplex.addInequality({1, 0}); // x >= 0. in TEST()
419 simplex.detectRedundant(); in TEST()
420 ASSERT_FALSE(simplex.isEmpty()); in TEST()
421 EXPECT_FALSE(simplex.isMarkedRedundant(0)); in TEST()
422 EXPECT_TRUE(simplex.isMarkedRedundant(1)); in TEST()
426 Simplex simplex(1); in TEST() local
428 unsigned snapshot1 = simplex.getSnapshot(); in TEST()
429 simplex.appendVariable(); in TEST()
430 simplex.appendVariable(0); in TEST()
431 EXPECT_EQ(simplex.getNumVariables(), 2u); in TEST()
434 simplex.addInequality({0, 1, -yMin}); // y >= 2. in TEST()
435 simplex.addInequality({0, -1, yMax}); // y <= 5. in TEST()
437 unsigned snapshot2 = simplex.getSnapshot(); in TEST()
438 simplex.appendVariable(2); in TEST()
439 EXPECT_EQ(simplex.getNumVariables(), 4u); in TEST()
440 simplex.rollback(snapshot2); in TEST()
442 EXPECT_EQ(simplex.getNumVariables(), 2u); in TEST()
443 EXPECT_EQ(simplex.getNumConstraints(), 2u); in TEST()
445 simplex.computeIntegerBounds({0, 1, 0}), in TEST()
448 simplex.rollback(snapshot1); in TEST()
449 EXPECT_EQ(simplex.getNumVariables(), 1u); in TEST()
450 EXPECT_EQ(simplex.getNumConstraints(), 0u); in TEST()
454 Simplex simplex(2); in TEST() local
455 simplex.addInequality({0, -1, 2}); // y <= 2. in TEST()
456 simplex.addInequality({1, 0, 0}); // x >= 0. in TEST()
457 simplex.addEquality({-1, 1, 0}); // y = x. in TEST()
459 EXPECT_TRUE(simplex.isRedundantInequality({-1, 0, 2})); // x <= 2. in TEST()
460 EXPECT_TRUE(simplex.isRedundantInequality({0, 1, 0})); // y >= 0. in TEST()
462 EXPECT_FALSE(simplex.isRedundantInequality({-1, 0, -1})); // x <= -1. in TEST()
463 EXPECT_FALSE(simplex.isRedundantInequality({0, 1, -2})); // y >= 2. in TEST()
464 EXPECT_FALSE(simplex.isRedundantInequality({0, 1, -1})); // y >= 1. in TEST()
468 Simplex simplex(2); in TEST() local
469 simplex.addInequality({0, -1, 2}); // y <= 2. in TEST()
470 simplex.addInequality({1, 0, 0}); // x >= 0. in TEST()
471 simplex.addEquality({-1, 1, 0}); // y = x. in TEST()
473 EXPECT_TRUE(simplex.findIneqType({-1, 0, 2}) == in TEST()
475 EXPECT_TRUE(simplex.findIneqType({0, 1, 0}) == in TEST()
478 EXPECT_TRUE(simplex.findIneqType({0, 1, -1}) == in TEST()
480 EXPECT_TRUE(simplex.findIneqType({-1, 0, 1}) == in TEST()
482 EXPECT_TRUE(simplex.findIneqType({0, 1, -2}) == in TEST()
485 EXPECT_TRUE(simplex.findIneqType({-1, 0, -1}) == in TEST()
490 Simplex simplex(2); in TEST() local
491 simplex.addInequality({0, -1, 2}); // y <= 2. in TEST()
492 simplex.addInequality({1, 0, 0}); // x >= 0. in TEST()
493 simplex.addEquality({-1, 1, 0}); // y = x. in TEST()
495 EXPECT_TRUE(simplex.isRedundantEquality({-1, 1, 0})); // y = x. in TEST()
496 EXPECT_TRUE(simplex.isRedundantEquality({1, -1, 0})); // x = y. in TEST()
498 EXPECT_FALSE(simplex.isRedundantEquality({0, 1, -1})); // y = 1. in TEST()
500 simplex.addEquality({0, -1, 2}); // y = 2. in TEST()
502 EXPECT_TRUE(simplex.isRedundantEquality({-1, 0, 2})); // x = 2. in TEST()
543 Simplex simplex(/*nVar=*/1); in TEST() local
544 simplex.addDivisionVariable({1, 0}, 2); in TEST()
545 simplex.addInequality({1, 0, -3}); // x >= 3. in TEST()
546 simplex.addInequality({-1, 0, 9}); // x <= 9. in TEST()
547 Optional<SmallVector<int64_t, 8>> sample = simplex.findIntegerSample(); in TEST()
553 LexSimplex simplex(/*nVar=*/1); in TEST() local
554 simplex.addInequality({2, -1}); // x >= 1/2. in TEST()
557 EXPECT_TRUE(simplex.isRedundantInequality({3, -2})); in TEST()
558 EXPECT_FALSE(simplex.isSeparateInequality({3, -2})); in TEST()
561 EXPECT_FALSE(simplex.isRedundantInequality({-3, 2})); in TEST()
562 EXPECT_TRUE(simplex.isSeparateInequality({-3, 2})); in TEST()
565 EXPECT_FALSE(simplex.isRedundantInequality({-1, 1})); in TEST()
566 EXPECT_FALSE(simplex.isSeparateInequality({-1, 1})); in TEST()