We propose a dynamic version of the classical node packing problem, also called the stable set or independent set problem. The problem is defined by a node set, a node weight vector, and an edge probability vector. For every pair of nodes, an edge is present or not according to an independent Bernoulli random variable defined by the corresponding entry in the probability vector. At each step, the decision maker selects an available node that maximizes the expected weight of the final packing, and then observes edges adjacent to this node. We formulate the problem as a Markov decision process and show that it is NP-Hard even on star graphs. Next, we introduce relaxations of the problem’s achievable probabilities polytope, analogous to the linear and bilinear edge-based formulations in the deterministic case; we show that these relaxations can be weak, motivating a polyhedral study. We derive classes of valid inequalities arising from cliques, paths, and cycles. For cliques, we completely characterize the polytope and show that it is a submodular polyhedron. For both paths and cycles, we give an implicit representation of the polytope via a cut-generating linear program of polynomial size based on a compact dynamic programming formulation. Our computational results show that our inequalities can greatly reduce the upper bound and improve the linear relaxation’s gap, particularly when the instance’s expected density is high.
Citation
H. Milton Stewart School of Industrial and Systems Engineering. November, 2020.