Steiner tree packing instances may be trivial for heuristic solvers

[RoutingEnthusiast]

Unless I am mistaken the Steiner tree instances are easily solved by simple ripup and reroute approaches (non-optimally of course). The first variant I tried could generate valid solutions for all instances without any tuning, according to the provided checker. Looking at a few instances it seems that there is too much space or too few terminals.

A solution file for instance stp_s100_l4_t6_h2_rs37235 is s100_l4_t6_h2_rs37235.bst.sol.txt. It has length 2023. Note that this is on a 100x100x4 grid so it is almost empty.

Should you be able to provide denser and more difficult instances I would be very happy, especially if they were closer to modern VLSI-routing instances.

[mlschicker]

Hi @RoutingEnthusiast ,

Thank you for opening an issue.

The difficulty in the problems also lies in proving that your solution is optimal.
Do you have a way of proving optimality?
As for finding a feasible solution, I will take a look at the logs of our runs to get an idea of how the incumbent evolves.

In the misc directory, there is a script to generate new instances.

Can you provide a source for modern VLSI-routing instances that are denser?

Moreover, I would be interested to see how good your solutions are compared to the ones we provided.
Feel free to make a submission!

Best, Max

[RoutingEnthusiast]

Thanks for your answer!

The difficulty in the problems also lies in proving that your solution is optimal.
Do you have a way of proving optimality?

No, but deciding whether a valid Steiner tree packing exists is such a hard problem that I was surprised how easy it is for the instances in this benchmark. I'd recommend adding instances where finding any solution is difficult. And sorry but I cannot provide instances.

Moreover, I would be interested to see how good your solutions are compared to the ones we provided.
Feel free to make a submission!

The code I wrote was intended for evaluating your Steiner tree packing instances and it was written in a couple hours. Hence, there is no point in formally submitting the solutions.

Regarding solution quality: My solutions are never better than those provided in the solutions folder. However, they often beat the ones stored in sol.txt in the instances (by the way: these files are easy to miss). Statistics for each instance: rnr_solutions_comparison.txt. Solution files for each instance: rnr_solutions.tar.gz.

[mlschicker]

Hi @RoutingEnthusiast ,

thank you for your response and the data!

I agree that it is easy to find feasible solutions for our instances with the method you described.
(especially when the instances are as sparse as you noted)
We will look into generating instances where this is harder to do.

The solution quality looks good for your approach!
Can you give me an estimate on the runtime of your algorithm?

I will run a few tests on the instances, e.g., how long it takes MIP solvers to find feasible solutions and how good the solution quality is.
I will keep you updated in this thread.

Best, Max

[RoutingEnthusiast]

We will look into generating instances where this is harder to do.

Thanks, that sounds promising!

I did not measure time in the original run but the following comparison contains runtimes (single-threaded): rnr_solutions_500_permutations_comparison.txt
solutions: rnr_solutions_500_permutations.tar.gz. In this run I tried 500 different net orderings.

The previous one had only 50 so its results are a bit worse but such a run would be approximately 10 times faster than the times reported above. Note that a few solutions from this run are slightly better than the ones from the run with 500 orderings because the program changed a bit to improve runtime.

I will run a few tests on the instances, e.g., how long it takes MIP solvers to find feasible solutions and how good the solution quality is.

I tried running with just one ordering and disabling some non-essential code that improves solution quality. With that the slowest instance too 25ms and finding a valid solution for all instances took half a second.

edit: had more fun with these instances than I had expected so I computed some improved solutions: compare.txt rnr_solutions_best.tar.gz

[mlschicker]

Hi @RoutingEnthusiast ,

thank you for providing your solutions.
It would be nice, if you could upload them in a submission.
Then I can add the solutions with the correct reference in the solution directory.

I tried running the smaller instances with Gurobi. (see gurobi_stp.csv)
For many of the bigger instances, a feasible solution could not be found within 10 minutes.
The model gets very large for bigger instances. (see model metrics)

To generate the new, harder instances, we will use a specialized heuristic for verification.
Would you be able to provide your code or explain your approach in more detail?

Best, Max

[gnannicini]

@RoutingEnthusiast FYI, the rip-up approach that you suggest is exactly what we used to guarantee that the instances are feasible: if you look at the instance generation script, it computes a single steiner tree at a time, blocks out the corresponding arcs, then tries to pack additional steiner trees. So it is no surprise you can find a solution in that manner. Sometimes there could be a discrepancy between the given seed solution and what you find because the steiner trees that we compute in instance generation are not guaranteed to be optimal (we use Cplex with a relatively short time limit).

Generating instances that are guaranteed to be feasible, but at the same time it is difficult to find a feasible solution, seems like a difficult problem. I'm working on a new instance generation script that might go somewhat in that direciton, but I cannot guarantee that it will be difficult to find primal solutions given that we require the instances to be feasible.

[RoutingEnthusiast]

Thanks to both of you!

It would be nice, if you could upload them in a submission. Would you be able to provide your code or explain your approach in more detail?

Sorry, but no for now (what I did was nothing interesting and your submission process is quite restrictive). But I can explain the algorithm a bit more: It picks a random ordering and tries to complete the nets one by one. If other nets block the current nets use ripup and reroute (with some added costs for ripping out nets and in contested regions to avoid trying the same stuff again and again). Whenever a net is fully routed call Dreyfus Wagner on every net that was routed so far, optimizing it without causing conflicts to other nets (the conflict avoidance during ripup can add avoidable detours). After all nets are routed the solution is post-processed again: Pick maybe 3-5 nets and rip them out. Try connecting them again for every possible order. If this fails we keep the old solution but if quality does not degrade keep the new solution. Repeat that until a full round has failed to find any improvement. This whole process is repeated for different net orderings. It's simple, not suitable for practical purposes, and nothing new but this approach leads to OK solutions on these instances.

I also generated some lower bounds but that is easy to get wrong. I think there may also be a problem with your optimal solutions or with the checking tool. Here are the slightly updated best solutions I found: compare.txt solutons.tar.gz. Note the instance where a solution that is better than the provided optimal solution was found. It's valid according to the provided checker. You can do with the solutions whatever you like, e.g. throwing them away or providing them as reference solutions without attribution.

Generating instances that are guaranteed to be feasible, but at the same time it is difficult to find a feasible solution, seems like a difficult problem. I'm working on a new instance generation script that might go somewhat in that direciton, but I cannot guarantee that it will be difficult to find primal solutions given that we require the instances to be feasible.

Maybe, but you could try maintaining a feasible solution, adding only stuff (nets, terminals, blockages) such that the solution remains feasible or revising the maintained solution as needed, you might be able to generate harder instances. This way I could easily generate instances that my simple solver could not solve (it was very easy when allowing terminals in middle and a little harder when only allowing it at the boundary). I've attached three examples with boundary terminals on the lowest layer only harder_instances.tar.gz. I'm not claiming that these are great instances or that they are super difficult to solve.

A completely different strategy might be to generate Steiner tree packing instances from openly available design data, e.g. form the OpenROAD flow scripts example designs, but they might require additional restrictions and I'm not sure how interesting such instances would be.

And maybe it's not a big problem that it's very easy to find feasible solutions. I was just a little surprised and disappointed about it, as I was looking for much harder Steiner tree packing instances to try some completely different ideas.

[mlschicker]

Hi @RoutingEnthusiast ,

thank you for the more detailed explanation of your algorithm!
And thank you for providing your solutions!

I have checked the log-file for the instance stp_s030_l3_t5_h1_rs24098.
And indeed, Gurobi does not claim optimality - there must have been a mistake when parsing the logs.
I will check the rest of the provided solutions.
Thank you for this insight!

I will try running the instances you sent.

Instances, where it is hard to find a feasible solution, are very interesting.
We will keep working on this and keep this issue updated!

Best, Max