rk900/cs170-project

CS 170 Final Project Fall 2019

cs170-project's Issues

Output file seems to have incorrect path

Steps to reproduce

• Run input_generator.py on final_inputs/inputs/200.in
• GUROBI should output a valid path (check output logs and graph)
• Output file (outputs/200/200_November24_1059.out) path does not end at 0

Potential causes

• DFS traversal may be off

For some graphs, creates 2 SCCs

2_subconnected_components.in
(also called 02:38PM on November 22, 2019r4bhoxsg.in)

Creates 2 SCCs because in lazy constraints we're ignoring SCCs with Soda (source) in it.

It creates 1 additional SCC w/o Soda because the LP ignores the SCC with Soda in it, leading the LP to believe only 1 SCC exists.

Invalid walk for 71_100/200

Gradescope says

This is not a valid walk for the given graph.
The total cost of your solution is infinite.

We need to investigate why our solution is an invalid walk for both of their inputs. Probably requires visualizing the solution via networkx

Unoptimal bounds/outputs while running lp/timeouts

Maybe these need to be manually solved or we need some constraints. These take 2+ hrs and don't come close to optimal on latte

Most of the time the solution doesn't improve after 500 seconds at most and just stalls the machine. These might need to be manually inspected to see if we need to resolve our solutions to find a better bounds.

error bound 0.001
233_200-log.out 432706.51546116854 526139.5640199999 0.21592706654590726
350_200-log.out 1766.4777097738645 2123.8360333333335 0.2022999336941626
82_200-log.out 529.0 1310.0 1.4763705103969755
97_100-log.out 107.33333333333333 115.00000000000001 0.0714285714285716
327_200-log.out 35.68 41.73666666666667 0.16974962630792242
335_200-log.out 4.639164086542013 4.875509999999999 0.050945797356815745
245_200-log.out 4950.865051946212 5639.064386666667 0.13900587624579272
23_200-log.out 41.666666666666664 52.0 0.24800000000000008
357_200-log.out 5087479317.826382 5120285764.864468 0.006448467893153509
258_200-log.out 463.85781221310896 545.22538 0.17541489147003636
271_200-log.out 44548.48855181879 50634.48901666667 0.1366151953229265
97_200-log.out 125.0 231.66666666666666 0.8533333333333333
296_200-log.out 5496056788.789431 5903553872.552453 0.07414353588816872
324_200-log.out 756.6666666666666 814.3333333333333 0.07621145374449334
238_200-log.out 2708.939652086525 3024.6117333333336 0.11652975768716982
309_200-log.out 6594895120.091211 8112056613.854636 0.23005089029261797
82_100-log.out 870.0 1272.6666666666667 0.4628352490421457
214_200-log.out 579.6666666666666 589.0 0.01610120759056936
239_200-log.out 102.0 102.33333333333333 0.003267973856209104
19 items with error greater than 0.001