"""Checks and a report for Part 9: the fewest commands, exactly, as an integer program. Run from this folder: python test_branch_cut.py The HiGHS checks and the big-room report need highspy (pip install highspy); without it they are skipped, and say so. The big-room report takes a while: each 40x40 room gets 15 minutes. """ import itertools import random import time import branch_cut import route_lp import shortest_route_exact import simplex from shortest_route_fast import lower_bound, parse from shortest_route_fast import solution as fast from test_cleaning_robot import random_room, simulate try: import highspy # noqa: F401 HAVE_HIGHS = True except ImportError: HAVE_HIGHS = False # Rooms whose linear program (Part 8) is below the shortest route: here branch and bound has work # to do. Found by trying 3,000 rooms of 5x5 to 8x8 from random_room(random.Random(90), ...) with # 8 to 20 fields, solving the LP and the integer program with HiGHS; these are the smallest of the # 27 with a gap, without repeats. test_gap_rooms checks that each still has one. GAP_ROOMS = [ ['########', '######.#', '######.#', '####...#', '####*..#', '####..##', '########'], ['######', '######', '#.####', '#....#', '##.#.#', '##..*#', '######'], ['######', '####.#', '#.#..#', '#...*#', '#.#..#', '######'], ['#####', '#.###', '#.#.#', '#...#', '#.#.#', '#..*#', '#####'], ['#######', '#.....#', '#*#.###', '#.....#', '#######'], ['#######', '#..#..#', '#.#..*#', '#.....#', '#######'], ['######', '#.#..#', '#..#.#', '#*...#', '#..#.#', '######'], ['#####', '#.*.#', '#.#.#', '#...#', '#...#', '#.#.#', '#####'], ['########', '#####..#', '###...##', '##..#..#', '##..*.##', '########'], ['#####', '###*#', '#...#', '#.#.#', '#...#', '##.##', '#...#', '#####'], ['########', '#.#....#', '#...##.#', '#.#..*.#', '########'], ] def test_gomory(rng, count=200): """Gomory's cuts never cut off a whole-number point, and always cut off the fractional corner they came from. Small programs in two variables, every whole-number point listed.""" made = 0 for _ in range(count): c = [rng.randint(-5, 5) for _ in range(2)] rows = [({0: rng.randint(-3, 4), 1: rng.randint(-3, 4)}, simplex.LE, rng.randint(0, 12)) for _ in range(3)] rows += [({j: 1}, simplex.LE, 6) for j in range(2)] points = [p for p in itertools.product(range(7), repeat=2) if all(sum(a * p[j] for j, a in co.items()) <= b for co, _, b in rows)] for _ in range(4): r = simplex.solve(c, rows) if r.status != 'optimal': break cuts = simplex.gomory_cuts(r) if not cuts: break for co, _, b in cuts: assert all(sum(a * p[j] for j, a in co.items()) >= b for p in points) assert sum(a * r.x[j] for j, a in co.items()) < b made += len(cuts) rows += cuts print(f'Gomory cuts ............. ok ({made} cuts on {count} random programs: none cut off a whole-number ' f'point, every one cut off its fractional corner)') def test_small_rooms(rng, count=60): """Branch and bound against Part 3's exact search, and its route against the simulator.""" for _ in range(count): room = random_room(rng, rng.randint(3, 6), rng.randint(3, 6), rng.choice([0, 0.2, 0.35])) route, _ = branch_cut.solve(room) assert simulate(room, route) == parse(room)[1] assert len(route) == len(shortest_route_exact.solution(room)) print(f'small rooms ............. ok ({count} rooms: branch and bound finds Part 3\'s exact answer, ' f'and its route cleans every field)') def test_gap_rooms(): """Where the LP is below the best route, the tree has work to do. With and without one round of Gomory's cuts at the root.""" rows = [] for room in GAP_ROOMS: best = len(shortest_route_exact.solution(room)) lp = route_lp.lp_bound(room) assert lp.value < best, 'no gap any more' out = [len(route_lp.Model(room).fields), lp.value, best, len(fast(room))] for rounds in (0, 1): t = time.perf_counter() route, stats = branch_cut.solve(room, gomory_rounds=rounds) assert simulate(room, route) == parse(room)[1] and len(route) == best out += [stats['nodes'], stats['root'], time.perf_counter() - t] rows.append(out) print(f'gap rooms ............... ok ({len(rows)} rooms: every one solved exactly, with and without Gomory)') print(' fields LP best fast | nodes root time | with one Gomory round: nodes root time') for n, lp, best, f, n0, r0, t0, n1, r1, t1 in rows: print(f' {n:>6} {str(lp):>3} {best:>4} {f:>4} | {n0:>5} {str(r0):>4} {t0:>4.1f}s | ' f'{n1:>28} {str(r1):>4} {t1:>4.1f}s') print(f' total nodes: {sum(r[4] for r in rows)} without, {sum(r[7] for r in rows)} with; ' f'time {sum(r[6] for r in rows):.0f}s against {sum(r[9] for r in rows):.0f}s') def test_highs(rng, count=40): """HiGHS against branch and bound (small rooms) and against the gap rooms.""" import route_ip for room in [random_room(rng, rng.randint(3, 6), rng.randint(3, 6), rng.choice([0, 0.2, 0.35])) for _ in range(count)] + GAP_ROOMS: r = route_ip.solve(room, time_limit=60) assert r['optimal'] and simulate(room, r['route']) == parse(room)[1] assert len(r['route']) == len(shortest_route_exact.solution(room)) print(f'HiGHS ................... ok ({count} random rooms and the {len(GAP_ROOMS)} gap rooms: proven ' f'best, the same length as Part 3\'s exact answer, and its route cleans every field)') def report_rooms(rng, groups=((12, 0.15, 10), (12, 0.3, 10), (20, 0.15, 6), (20, 0.3, 6), (40, 0.15, 1), (40, 0.3, 1)), time_limit=900): import route_ip print('\nRandom furnished rooms (HiGHS, 15 minutes a room at most):') print(' size furniture rooms fields fast Part 3 LP bound best found proven fast is best ' 'fast over best time') for size, p, count in groups: rows = [] for _ in range(count): room = random_room(rng, size, size, p) r = route_ip.solve(room, time_limit=time_limit) assert simulate(room, r['route']) == parse(room)[1] rows.append((len(parse(room)[1]), len(fast(room)), lower_bound(room), r['lp'], len(r['route']), r['bound'], r['optimal'], r['seconds'])) mean = lambda i: sum(r[i] for r in rows) / count print(f' {size}x{size} {100 * p:>6.0f}% {count:>6} {mean(0):>6.0f} {mean(1):>4.0f} {mean(2):>6.0f} ' f'{mean(3):>8.1f} {mean(4):>10.1f} {sum(r[6] for r in rows):>3}/{count} ' f'{sum(r[1] == r[4] for r in rows):>6}/{count} {mean(1) - mean(4):>14.1f} {mean(7):>5.0f}s') for r in rows: if not r[6]: print(f' not proven: best {r[4]}, no route shorter than {r[5]} ({100 * (r[4] - r[5]) / r[4]:.1f}% gap)') def report_formulations(rng, count=4): """What each part of the model is worth, on the same rooms in the same run: the flow rules' linear program alone against Part 8's; and HiGHS's time with and without the fast route.""" import route_ip print('\nWhat the parts of the model are worth (20x20, 30% furniture):') print(" fields flow rules alone with Part 8's rules best | seconds: no start fast route as start") for _ in range(count): room = random_room(rng, 20, 20, 0.3) weak = route_ip.solve(room, cuts=False, relax=True)['relaxation'] strong = route_ip.solve(room, relax=True)['relaxation'] cold = route_ip.solve(room, start=False, time_limit=900) warm = route_ip.solve(room, time_limit=900) assert len(cold['route']) == len(warm['route']) or not (cold['optimal'] and warm['optimal']) print(f' {len(parse(room)[1]):>6} {weak:>16.1f} {strong:>19.1f} {len(warm["route"]):>4} | ' f'{cold["seconds"]:>16.1f} {warm["seconds"]:>19.1f}') def report_showcase(): """The rooms of Part 8's table, now solved.""" import route_ip rng = random.Random(8) print('\nPart 8\'s rooms (random.Random(8)), solved:') print(' room fields fast Part 3 LP bound best proven time') for size, p in ((12, 0.2), (20, 0.3), (40, 0.3)): room = random_room(rng, size, size, p) r = route_ip.solve(room, time_limit=900) print(f' {size}x{size}, {100 * p:.0f}% {len(parse(room)[1]):>6} {len(fast(room)):>4} {lower_bound(room):>6} ' f'{r["lp"]:>8.2f} {len(r["route"]):>4} {"yes" if r["optimal"] else "no, >= " + str(r["bound"]):>6} ' f'{r["seconds"]:>5.0f}s') def main(): rng = random.Random(9) test_gomory(rng) test_small_rooms(rng) test_gap_rooms() if HAVE_HIGHS: test_highs(rng) report_showcase() report_formulations(rng) report_rooms(rng) else: print('\nThe HiGHS checks and the big-room report need highspy; skipped.') if __name__ == '__main__': main()