Set covering algorithms using cutting planes, heuristics, and subgradient optimization: A computational study

By E. Balas, Andrew C. Ho. 1980

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Learning Combinatorial Optimization Algorithms over Graphs (2017, methodology): “We guarantee that each node in U has at least 2 edges, and each node in C has at least one edge, a standard measure for SCP instances [5].”
The volume algorithm: producing primal solutions with a subgradient method (2000, methodology): “The subgradient algorithm has been used to obtain dual solutions and lower bounds in [17,4,9,10] and others.”
Exact Combinatorial Optimization with Graph Convolutional Neural Networks (2019, methodology): “b.com/ds4dm/learn2branch. 5.1 Setup Benchmarks We evaluate our approach on three NP-hard problem benchmarks. Our ﬁrst benchmark is comprised of set covering instances generated following Balas and Ho [7], with 1,000 columns. We train and test on instances with 500 rows, and we evaluate on instances ”
Flexibility, efficiency, and accountability: adapting reserve selection algorithms to more complex conservation problems (2000, background): “This is a well known 0/1 linear programming problem: the set covering problem (Padberg 1979, Balas 1980, Balas and Ho 1980, Underhill 1994, Ando et al. 1998) and can be written as: Minimise % n j=1 xj (I) Subject to % n j=1 aijxj]1, i=1, 2, . . . , m (II) xj {0, 1} j=1, 2, . . . , n (III) where n…”