We present an algorithm for finding near-optimal solutions to robust combinatorial optimization problems with knapsack constraints under interdiction uncertainty. We incorporate a heuristic for generating feasible solutions in a standard row generation approach. Experimental results are presented for set covering, simple plant location, and min-knapsack problems under a discrete-budgeted interdiction uncertainty set introduced in this work.
Citation
Escuela de Computación, Facultad de Ciencias, Universidad Central de Venezuela