1 /* Copyright (c) 2019-2022. The SimGrid Team. All rights reserved. */
3 /* This program is free software; you can redistribute it and/or modify it
4 * under the terms of the license (GNU LGPL) which comes with this package. */
6 #include "src/include/catch.hpp"
7 #include "src/kernel/lmm/bmf.hpp"
8 #include "src/surf/surf_interface.hpp"
11 namespace lmm = simgrid::kernel::lmm;
13 TEST_CASE("kernel::bmf Basic tests", "[kernel-bmf-basic]")
15 lmm::BmfSystem Sys(false);
16 xbt_log_control_set("ker_bmf.thres:debug");
18 SECTION("Single flow")
21 * A single variable using a single resource
24 * o System: a1 * p1 * \rho1 < C
25 * o consumption_weight: a1=1
26 * o sharing_penalty: p1=1
32 lmm::Constraint* sys_cnst = Sys.constraint_new(nullptr, 3);
33 lmm::Variable* rho_1 = Sys.variable_new(nullptr, 1);
35 Sys.expand(sys_cnst, rho_1, 1);
38 REQUIRE(double_equals(rho_1->get_value(), 3, sg_maxmin_precision));
44 * Two flows sharing a single resource
47 * o System: a1 * p1 * \rho1 + a2 * p2 * \rho2 < C
48 * o consumption_weight: a1=1 ; a2=10
49 * o sharing_penalty: p1=1 ; p2=1
56 lmm::Constraint* sys_cnst = Sys.constraint_new(nullptr, 3);
57 lmm::Variable* rho_1 = Sys.variable_new(nullptr, 1);
58 lmm::Variable* rho_2 = Sys.variable_new(nullptr, 1);
60 Sys.expand(sys_cnst, rho_1, 1);
61 Sys.expand(sys_cnst, rho_2, 10);
64 REQUIRE(double_equals(rho_1->get_value(), 3.0 / 2.0, sg_maxmin_precision));
65 REQUIRE(double_equals(rho_2->get_value(), (3.0 / 2.0) / 10.0, sg_maxmin_precision));
68 SECTION("Variable penalty/priority")
71 * A variable with twice the penalty gets half of the share
74 * o System: a1 * p1 * \rho1 + a2 * p2 * \rho2 < C
75 * o consumption_weight: a1=1 ; a2=1
76 * o sharing_penalty: p1=1 ; p2=2
79 * o rho1 = 2* rho2 (because rho2 has twice the penalty)
80 * o rho1 + rho2 = C (because all weights are 1)
83 lmm::Constraint* sys_cnst = Sys.constraint_new(nullptr, 3);
84 lmm::Variable* rho_1 = Sys.variable_new(nullptr, 1);
85 lmm::Variable* rho_2 = Sys.variable_new(nullptr, 2);
87 Sys.expand(sys_cnst, rho_1, 1);
88 Sys.expand(sys_cnst, rho_2, 1);
91 REQUIRE(double_equals(rho_1->get_value(), 2, sg_maxmin_precision));
92 REQUIRE(double_equals(rho_2->get_value(), 1, sg_maxmin_precision));
95 SECTION("Disable variable doesn't count")
98 * Two flows sharing a single resource, but only disabled
101 * o System: a1 * p1 * \rho1 + a2 * p2 * \rho2 < C
102 * o consumption_weight: a1=1 ; a2=10
103 * o sharing_penalty: p1=1 ; p2=0
109 lmm::Constraint* sys_cnst = Sys.constraint_new(nullptr, 3);
110 lmm::Variable* rho_1 = Sys.variable_new(nullptr, 1);
111 lmm::Variable* rho_2 = Sys.variable_new(nullptr, 0);
113 Sys.expand(sys_cnst, rho_1, 1);
114 Sys.expand(sys_cnst, rho_2, 10);
117 REQUIRE(double_equals(rho_1->get_value(), 3.0, sg_maxmin_precision));
118 REQUIRE(double_equals(rho_2->get_value(), 0.0, sg_maxmin_precision));
121 SECTION("No consumption variable")
124 * An empty variable, no consumption, just assure it receives something
126 * o System: a1 * p1 * \rho1 < C
127 * o consumption_weight: a1=0
128 * o sharing_penalty: p1=1
134 lmm::Constraint* sys_cnst = Sys.constraint_new(nullptr, 3);
135 lmm::Variable* rho_1 = Sys.variable_new(nullptr, 1);
136 lmm::Variable* rho_2 = Sys.variable_new(nullptr, 0);
138 Sys.expand(sys_cnst, rho_1, 1);
139 Sys.expand(sys_cnst, rho_2, 10);
142 REQUIRE(double_positive(rho_1->get_value(), sg_maxmin_precision));
145 SECTION("Bounded variable")
148 * Assures a player receives the min(bound, share) if it's bounded
150 * o System: a1 * p1 * \rho1 + a2 * p2 * \rho2 < C
151 * o bounds: b1=0.1, b2=-1
152 * o consumption_weight: a1=1, a2=1
153 * o sharing_penalty: p1=1, p2=1
160 lmm::Constraint* sys_cnst = Sys.constraint_new(nullptr, 1);
161 lmm::Variable* rho_1 = Sys.variable_new(nullptr, 1, .1);
162 lmm::Variable* rho_2 = Sys.variable_new(nullptr, 1);
164 Sys.expand(sys_cnst, rho_1, 2);
165 Sys.expand(sys_cnst, rho_2, 1);
167 REQUIRE(double_equals(rho_1->get_value(), .1, sg_maxmin_precision));
168 REQUIRE(double_equals(rho_2->get_value(), .8, sg_maxmin_precision));
174 * Two flows using a fatpipe resource
177 * o System: a1 * p1 * \rho1 < C and a2 * p2 * \rho2 < C
178 * o consumption_weight: a1=1 ; a2=1
179 * o sharing_penalty: p1=1 ; p2=1
186 lmm::Constraint* sys_cnst = Sys.constraint_new(nullptr, 3);
187 sys_cnst->set_sharing_policy(lmm::Constraint::SharingPolicy::FATPIPE, {});
188 lmm::Variable* rho_1 = Sys.variable_new(nullptr, 1);
189 lmm::Variable* rho_2 = Sys.variable_new(nullptr, 1);
191 Sys.expand(sys_cnst, rho_1, 1);
192 Sys.expand(sys_cnst, rho_2, 1);
195 REQUIRE(double_equals(rho_1->get_value(), 3.0, sg_maxmin_precision));
196 REQUIRE(double_equals(rho_2->get_value(), 3.0, sg_maxmin_precision));
199 SECTION("(un)Bounded variable")
202 * Assures a player receives the share if bound is greater than share
204 * o System: a1 * p1 * \rho1 + a2 * p2 * \rho2 < C
205 * o bounds: b1=1, b2=-1
206 * o consumption_weight: a1=1, a2=1
207 * o sharing_penalty: p1=1, p2=1
214 lmm::Constraint* sys_cnst = Sys.constraint_new(nullptr, 1);
215 lmm::Variable* rho_1 = Sys.variable_new(nullptr, 1, 1);
216 lmm::Variable* rho_2 = Sys.variable_new(nullptr, 1);
218 Sys.expand(sys_cnst, rho_1, 1);
219 Sys.expand(sys_cnst, rho_2, 1);
221 REQUIRE(double_equals(rho_1->get_value(), .5, sg_maxmin_precision));
222 REQUIRE(double_equals(rho_2->get_value(), .5, sg_maxmin_precision));
225 SECTION("Dynamic bounds")
228 * Resource bound is modified by user callback and shares are adapted accordingly
230 * o System: a1 * p1 * \rho1 + a2 * p2 * \rho2 < C
231 * o consumption_weight: a1=1, a2=1
232 * o sharing_penalty: p1=1, p2=1
235 * o rho1 = .5 and .25
239 lmm::Constraint* sys_cnst = Sys.constraint_new(nullptr, 1);
240 sys_cnst->set_sharing_policy(lmm::Constraint::SharingPolicy::NONLINEAR,
241 [](double bound, int n) { return bound / n; });
242 // alone, full capacity
243 lmm::Variable* rho_1 = Sys.variable_new(nullptr, 1);
244 Sys.expand(sys_cnst, rho_1, 1);
246 REQUIRE(double_equals(rho_1->get_value(), 1, sg_maxmin_precision));
248 // add another variable, half initial capacity
249 lmm::Variable* rho_2 = Sys.variable_new(nullptr, 1);
250 Sys.expand(sys_cnst, rho_2, 1);
253 REQUIRE(double_equals(rho_1->get_value(), .25, sg_maxmin_precision));
254 REQUIRE(double_equals(rho_2->get_value(), .25, sg_maxmin_precision));
257 Sys.variable_free_all();
260 TEST_CASE("kernel::bmf Advanced tests", "[kernel-bmf-advanced]")
262 lmm::BmfSystem Sys(false);
263 xbt_log_control_set("ker_bmf.thres:debug");
265 SECTION("2 flows, 2 resources")
268 * Two flows sharing 2 resources with opposite requirements
271 * o System: a1 * p1 * \rho1 + a2 * p2 * \rho2 < C1
272 * o System: a1 * p1 * \rho1 + a2 * p2 * \rho2 < C2
274 * o consumption_weight: a11=1, a12=10, a21=10, a22=1
275 * o sharing_penalty: p1=1, p2=1
278 * o rho1 = rho2 = C/11
281 * [1 10] * [rho1 rho2] = [1]
285 lmm::Constraint* sys_cnst = Sys.constraint_new(nullptr, 1);
286 lmm::Constraint* sys_cnst2 = Sys.constraint_new(nullptr, 1);
287 lmm::Variable* rho_1 = Sys.variable_new(nullptr, 1, -1, 2);
288 lmm::Variable* rho_2 = Sys.variable_new(nullptr, 1, -1, 2);
290 Sys.expand(sys_cnst, rho_1, 1);
291 Sys.expand(sys_cnst2, rho_1, 10);
292 Sys.expand(sys_cnst, rho_2, 10);
293 Sys.expand(sys_cnst2, rho_2, 1);
296 REQUIRE(double_equals(rho_1->get_value(), 1.0 / 11.0, sg_maxmin_precision));
297 REQUIRE(double_equals(rho_2->get_value(), 1.0 / 11.0, sg_maxmin_precision));
300 SECTION("BMF paper example")
303 * 3 flows sharing 3 resources
306 * [1 1 1/2] * [rho1 rho2 rho3] = [1]
310 * Expectations (several possible BMF allocations, our algorithm return this)
311 * o rho1 = rho2 = rho3 = 2/5
314 lmm::Constraint* sys_cnst = Sys.constraint_new(nullptr, 1);
315 lmm::Constraint* sys_cnst2 = Sys.constraint_new(nullptr, 1);
316 lmm::Constraint* sys_cnst3 = Sys.constraint_new(nullptr, 1);
317 lmm::Variable* rho_1 = Sys.variable_new(nullptr, 1, -1, 3);
318 lmm::Variable* rho_2 = Sys.variable_new(nullptr, 1, -1, 3);
319 lmm::Variable* rho_3 = Sys.variable_new(nullptr, 1, -1, 3);
321 Sys.expand(sys_cnst3, rho_1, 1.0); // put this expand first to force a singular A' matrix
322 Sys.expand(sys_cnst, rho_1, 1.0);
323 Sys.expand(sys_cnst2, rho_1, 1.0);
324 Sys.expand(sys_cnst, rho_2, 1.0);
325 Sys.expand(sys_cnst2, rho_2, 1.0 / 2.0);
326 Sys.expand(sys_cnst3, rho_2, 3.0 / 4.0);
327 Sys.expand(sys_cnst, rho_3, 1.0 / 2.0);
328 Sys.expand(sys_cnst2, rho_3, 1.0);
329 Sys.expand(sys_cnst3, rho_3, 3.0 / 4.0);
332 REQUIRE(double_equals(rho_1->get_value(), 1.0 / 3.0, sg_maxmin_precision));
333 REQUIRE(double_equals(rho_2->get_value(), 4.0 / 9.0, sg_maxmin_precision));
334 REQUIRE(double_equals(rho_3->get_value(), 4.0 / 9.0, sg_maxmin_precision));
337 SECTION("IO - example")
340 * Two flows sharing 1 disk
341 * read, write and readwrite constraint
344 * o System: a1 * p1 * \rho1 + a2 * p2 * \rho2 < C1
345 * o System: a1 * p1 * \rho1 + a2 * p2 * \rho2 < C2
346 * o System: a1 * p1 * \rho1 + a2 * p2 * \rho2 < C3
348 * o consumption_weight: a1=1, a2=1
349 * o sharing_penalty: p1=1, p2=1
352 * o rho1 = rho2 = C/2
355 * [1 10] * [rho1 rho2] = [1]
359 lmm::Constraint* sys_cnst = Sys.constraint_new(nullptr, 1e6);
360 lmm::Constraint* sys_cnst2 = Sys.constraint_new(nullptr, 1e6);
361 lmm::Constraint* sys_cnst3 = Sys.constraint_new(nullptr, 1e6);
362 lmm::Variable* rho_1 = Sys.variable_new(nullptr, 1, -1, 3);
363 lmm::Variable* rho_2 = Sys.variable_new(nullptr, 1, -1, 3);
365 /* A' and C' matrices are dependent on the order of initialization
366 * this order is needed to identify a bug in the solver */
367 Sys.expand(sys_cnst2, rho_2, 1);
368 Sys.expand(sys_cnst, rho_1, 1);
369 Sys.expand(sys_cnst3, rho_1, 1);
370 Sys.expand(sys_cnst3, rho_2, 1);
373 REQUIRE(double_equals(rho_1->get_value(), 1e6 / 2.0, sg_maxmin_precision));
374 REQUIRE(double_equals(rho_2->get_value(), 1e6 / 2.0, sg_maxmin_precision));
377 SECTION("Proportional fairness")
380 * 3 flows sharing 2 resources with crosstraffic
382 * Regular max-min would give B/2 for every flow.
383 * BMF is equivalent to proportional fairness in this case, and give a quite
388 lmm::Constraint* sys_cnst = Sys.constraint_new(nullptr, 1);
389 lmm::Constraint* sys_cnst2 = Sys.constraint_new(nullptr, 1);
390 lmm::Variable* rho_1 = Sys.variable_new(nullptr, 1, -1, 2);
391 lmm::Variable* rho_2 = Sys.variable_new(nullptr, 1, -1, 2);
392 lmm::Variable* rho_3 = Sys.variable_new(nullptr, 1, -1, 2);
394 double epsilon = 0.05;
395 Sys.expand(sys_cnst, rho_1, 1.0);
396 Sys.expand(sys_cnst2, rho_1, epsilon);
397 Sys.expand(sys_cnst, rho_2, 1.0);
398 Sys.expand(sys_cnst2, rho_2, epsilon);
399 Sys.expand(sys_cnst2, rho_3, 1.0);
400 Sys.expand(sys_cnst, rho_3, epsilon);
403 REQUIRE(double_equals(rho_1->get_value(), 1.0 / (2.0 + 2 * epsilon), sg_maxmin_precision));
404 REQUIRE(double_equals(rho_2->get_value(), 1.0 / (2.0 + 2 * epsilon), sg_maxmin_precision));
405 REQUIRE(double_equals(rho_3->get_value(), 1.0 / (1.0 + epsilon), sg_maxmin_precision));
408 Sys.variable_free_all();
411 TEST_CASE("kernel::bmf Subflows", "[kernel-bmf-subflow]")
413 lmm::BmfSystem Sys(false);
414 xbt_log_control_set("ker_bmf.thres:debug");
416 SECTION("2 subflows and 1 resource")
419 * 2 identical flows composed of 2 subflows
421 * They must receive the same share and use same amount of resources
424 * o System: a1 * p1 * \rho1 + a2 * p2 * \rho2 < C
425 * o consumption_weight: a11=5, a12=7, a2=7, a2=5
426 * o sharing_penalty: p1=1, p2=1
429 * o rho1 = rho2 = (C/2)/12
432 * [12 12] * [rho1 rho2] = [1]
436 lmm::Constraint* sys_cnst = Sys.constraint_new(nullptr, 5);
437 lmm::Variable* rho_1 = Sys.variable_new(nullptr, 1);
438 lmm::Variable* rho_2 = Sys.variable_new(nullptr, 1);
440 Sys.expand_add(sys_cnst, rho_1, 5);
441 Sys.expand_add(sys_cnst, rho_1, 7);
442 Sys.expand_add(sys_cnst, rho_2, 7);
443 Sys.expand_add(sys_cnst, rho_2, 5);
446 REQUIRE(double_equals(rho_1->get_value(), 5.0 / 24.0, sg_maxmin_precision));
447 REQUIRE(double_equals(rho_2->get_value(), 5.0 / 24.0, sg_maxmin_precision));
450 SECTION("1 subflows, 1 flow and 1 resource")
453 * 2 flows, 1 resource
454 * 1 flow composed of 2 subflows
456 * Same share/rho, but subflow uses 50% more resources since it has a second connection/subflow
459 * o System: a1 * p1 * \rho1 + a2 * p2 * \rho2 < C
460 * o consumption_weight: a11=10, a12=5 a2=10
461 * o sharing_penalty: p1=1, p2=1
468 * [15 10] * [rho1 rho2] = [1]
472 lmm::Constraint* sys_cnst = Sys.constraint_new(nullptr, 5);
473 lmm::Variable* rho_1 = Sys.variable_new(nullptr, 1);
474 lmm::Variable* rho_2 = Sys.variable_new(nullptr, 1);
476 Sys.expand_add(sys_cnst, rho_1, 10);
477 Sys.expand_add(sys_cnst, rho_1, 5);
478 Sys.expand(sys_cnst, rho_2, 10);
481 REQUIRE(double_equals(rho_1->get_value(), (5.0 / 25.0), sg_maxmin_precision));
482 REQUIRE(double_equals(rho_2->get_value(), (5.0 / 25.0), sg_maxmin_precision));
483 REQUIRE(double_equals(15 * rho_1->get_value(), 10 * rho_2->get_value() * 3 / 2, sg_maxmin_precision));
486 SECTION("1 subflows using 2 resources: different max for each resource")
489 * Test condition that we may have different max for different resources
492 * o System: a1 * p1 * \rho1 + a2 * p2 * \rho2 < C
493 * o consumption_weight: a11=1, a12=1, a2=1
494 * o consumption_weight: a21=1/2, a12=1/2 a2=3/2
495 * o sharing_penalty: p1=1, p2=1
502 * [2 1 ] * [rho1 rho2] = [1]
506 lmm::Constraint* sys_cnst = Sys.constraint_new(nullptr, 1);
507 lmm::Constraint* sys_cnst2 = Sys.constraint_new(nullptr, 1);
508 lmm::Variable* rho_1 = Sys.variable_new(nullptr, 1, -1, 2);
509 lmm::Variable* rho_2 = Sys.variable_new(nullptr, 1, -1, 2);
511 Sys.expand_add(sys_cnst, rho_1, 1.0);
512 Sys.expand_add(sys_cnst, rho_1, 1.0);
513 Sys.expand(sys_cnst, rho_2, 1);
514 Sys.expand_add(sys_cnst2, rho_1, 1.0 / 2.0);
515 Sys.expand_add(sys_cnst2, rho_1, 1.0 / 2.0);
516 Sys.expand(sys_cnst2, rho_2, 3.0 / 2.0);
519 REQUIRE(double_equals(rho_1->get_value(), (1.0 / 3.0), sg_maxmin_precision));
520 REQUIRE(double_equals(rho_2->get_value(), (1.0 / 3.0), sg_maxmin_precision));
523 Sys.variable_free_all();
526 TEST_CASE("kernel::bmf Loop", "[kernel-bmf-loop]")
528 lmm::BmfSystem Sys(false);
529 xbt_log_control_set("ker_bmf.thres:debug");
531 SECTION("Initial allocation loops")
534 * Complex matrix whose initial allocation loops and is unable
535 * to stabilize after 10 iterations.
537 * The algorithm needs to restart from another point
540 std::vector<double> C = {1.0, 1.0, 1.0, 1.0, 1.0};
541 std::vector<std::vector<double>> A = {
542 {0.0918589, 0.980201, 0.553352, 0.0471331, 0.397493, 0.0494386, 0.158874, 0.737557, 0.822504, 0.364411},
543 {0.852866, 0.383171, 0.924183, 0.318345, 0.937625, 0.980201, 0.0471331, 0.0494386, 0.737557, 0.364411},
544 {0.12043, 0.985661, 0.153195, 0.852866, 0.247113, 0.318345, 0.0918589, 0.0471331, 0.158874, 0.364411},
545 {0.387291, 0.159939, 0.641492, 0.985661, 0.0540999, 0.383171, 0.318345, 0.980201, 0.0494386, 0.364411},
546 {0.722983, 0.924512, 0.474874, 0.819576, 0.572598, 0.0540999, 0.247113, 0.937625, 0.397493, 0.364411}};
548 std::vector<lmm::Constraint*> sys_cnst;
550 sys_cnst.push_back(Sys.constraint_new(nullptr, c));
552 std::vector<lmm::Variable*> vars;
553 for (size_t i = 0; i < A[0].size(); i++) {
554 vars.push_back(Sys.variable_new(nullptr, 1, -1, A.size()));
556 for (size_t j = 0; j < A.size(); j++) {
557 for (size_t i = 0; i < A[j].size(); i++) {
558 Sys.expand_add(sys_cnst[j], vars[i], A[j][i]);
563 for (auto* rho : vars) {
564 REQUIRE(double_positive(rho->get_value(), sg_maxmin_precision));
568 Sys.variable_free_all();
571 TEST_CASE("kernel::bmf Stress-tests", "[.kernel-bmf-stress]")
573 lmm::BmfSystem Sys(false);
575 SECTION("Random consumptions - independent flows")
579 auto data = GENERATE_COPY(chunk(C * N, take(100000, random(0., 1.0))));
580 std::vector<lmm::Constraint*> sys_cnst;
581 for (int i = 0; i < C; i++) {
582 sys_cnst.push_back(Sys.constraint_new(nullptr, 1));
584 for (int j = 0; j < N; j++) {
585 for (int i = 0; i < C; i++) {
586 lmm::Variable* rho = Sys.variable_new(nullptr, 1);
587 Sys.expand_add(sys_cnst[i], rho, data[i * j + j]);
593 SECTION("Random consumptions - flows sharing resources")
597 auto data = GENERATE_COPY(chunk(C * N, take(100000, random(0., 1.0))));
599 std::vector<lmm::Constraint*> sys_cnst;
600 for (int i = 0; i < C; i++) {
601 sys_cnst.push_back(Sys.constraint_new(nullptr, 1));
603 for (int j = 0; j < N; j++) {
604 lmm::Variable* rho = Sys.variable_new(nullptr, 1, -1, C);
605 for (int i = 0; i < C; i++) {
606 Sys.expand_add(sys_cnst[i], rho, data[i * j + j]);
613 SECTION("Random integer consumptions - flows sharing resources")
617 auto data = GENERATE_COPY(chunk(C * N, take(100000, random(1, 10))));
619 std::vector<lmm::Constraint*> sys_cnst;
620 for (int i = 0; i < C; i++) {
621 sys_cnst.push_back(Sys.constraint_new(nullptr, 10));
623 for (int j = 0; j < N; j++) {
624 lmm::Variable* rho = Sys.variable_new(nullptr, 1, -1, C);
625 for (int i = 0; i < C; i++) {
626 Sys.expand_add(sys_cnst[i], rho, data[i * j + j]);
632 SECTION("Random consumptions - high number of constraints")
636 auto data = GENERATE_COPY(chunk(C * N, take(100000, random(0., 1.0))));
638 std::vector<lmm::Constraint*> sys_cnst;
639 for (int i = 0; i < C; i++) {
640 sys_cnst.push_back(Sys.constraint_new(nullptr, 1));
642 for (int j = 0; j < N; j++) {
643 lmm::Variable* rho = Sys.variable_new(nullptr, 1, -1, C);
644 for (int i = 0; i < C; i++) {
645 Sys.expand_add(sys_cnst[i], rho, data[i * j + j]);
651 SECTION("Random integer consumptions - high number of constraints")
655 auto data = GENERATE_COPY(chunk(C * N, take(100000, random(1, 10))));
657 std::vector<lmm::Constraint*> sys_cnst;
658 for (int i = 0; i < C; i++) {
659 sys_cnst.push_back(Sys.constraint_new(nullptr, 10));
661 for (int j = 0; j < N; j++) {
662 lmm::Variable* rho = Sys.variable_new(nullptr, 1, -1, C);
663 for (int i = 0; i < C; i++) {
664 Sys.expand_add(sys_cnst[i], rho, data[i * j + j]);
670 Sys.variable_free_all();
673 TEST_CASE("kernel::AllocationGenerator Basic tests", "[kernel-bmf-allocation-gen]")
675 SECTION("Full combinations")
677 Eigen::MatrixXd A(3, 3);
678 A << 1, .5, 1, 1, 1, .5, 1, .75, .75;
679 lmm::AllocationGenerator gen(std::move(A));
681 std::vector<int> alloc;
682 while (gen.next(alloc))
684 REQUIRE(i == 3 * 3 * 3);
687 SECTION("Few options per player")
689 Eigen::MatrixXd A(3, 3);
690 A << 1, 0, 0, 0, 1, 0, 0, 1, 1;
691 lmm::AllocationGenerator gen(std::move(A));
693 std::vector<int> alloc;
694 while (gen.next(alloc))
696 REQUIRE(i == 1 * 2 * 1);