Stalence
commented
1 year ago Hey,
Sorry for the late reply! Yes, you could just combine a bunch of different constraints. I don't have a proof for you but a simple approach would be to take whatever constraints you have in mind and just take a union bound over them. In other words, you will have a probability of failure for each constraint independently, and then you could bound the probability of any of them failing using the union bound.
Since I'm not sure whether by "more constraints" you literally mean combining multiple constraints or whether you mean other types of constraints than the ones presented in the paper, I will also try to reply to the latter. Generally, there are constraints that are harder to deal with. You mentioned MST. Encoding the spanning tree constraint for a set is actually one of the harder constraints to encode into a loss function. Based on what I've tried so far, I would say that routing problems tend to be more challenging to express in our probabilistic penalty setting compared to problems that have to do with cliques, covers, satisfiability, etc. For example for MST, you either have to move to variables on the edges of the graph and work from there or perhaps try to work with some rank constraints on the laplacian of the subgraph induced by the solution set S. Both of those can be tricky but maybe you can make them work. I have only done some preliminary attempts but the results weren't great. Maybe you can make them work though :)
Hi,
This paper was super interesting to read. I am working on a similar graph CO problem where my objective is to “activate” as many nodes as possible in the graph to maximize as many paths as possible under some resource constraints (leaving out more details for brevity). My broader problem is situated in Systems Research, I.e. I am building a scheduling algorithm that approximates the LP to a reasonable degree.
Pardon my naïveté but my question is whether it is possible to make the loss function more rich. For instance, consider the traveling salesman problem. We know that twice MST is a 2-approximation to TSP. Similarly, there are other algorithms such as Christofides that guarantee a 1.5 approximation. I was wondering can we impose more constraints in the learning of the distribution with this existing literature knowledge? A potential benefit is if there is a way to incorporate these heuristics with guarantees then resulting learned agent will perform at least as good as the known approximations.