Given an algorithm for the Knapsack problem, can you also solve the min set covering problem?

Min set covering problem:
min \sum_j c_j y_j such that
\sum_j s_j y_j >= b
y_j \in {0,1}

Knapsack problem: max \sum_j c_j y_j such that
\sum_j s_j y_j <= b
y_j \in {0,1}


Answer (As per Sune's recommendation below):
1. Substitute every y_j by 1-z_j in the set covering problem. min \sum_j c_j (1-z_j) such that
\sum_j s_j (1-z_j) >= b
z_j \in {0,1}

rewriting and rearranging these constraints yields:
max \sum_j c_j z_j - sum_j c_j such that
\sum_j s_j z_j <= \sum_j s_j - b
z_j \in {0,1}

This problem is indeed the desired knapsack problem. the "- sum_j c_j" term in the objective is a constant and can therefore be ignored. After solving this knapsack problem, one can obtain a feasible solution to the set cover problem by setting y_j=1-z_j.
Interpretation: Let c_j be the value or cost of an item j, and s_j its weight. The knapsack problem tries to select the most expensive items while keeping their total weight equal or below \sum_j s_j - b. As a result, the remaining items will be as cheap as possible while having a total weight larger or equal to \sum_j s_j-(\sum_j s_j - b)=b.

asked 11 Mar '15, 17:29

Joris%20Kinable's gravatar image

Joris Kinable
accept rate: 16%

edited 11 Mar '15, 20:40

You have a binary set covering problem with only one cover constraint?

(11 Mar '15, 19:23) Paul Rubin ♦♦

@Joris Your definition of Set Cover is nonstandard. Here is the standard one.

(11 Mar '15, 23:12) Austin Buchanan

@Austin: you are right. I'm not sure ow to name a problem having such a "cover" constraint. Yet I encounter these fairly frequently. Are you aware of a different name?

(13 Mar '15, 15:04) Joris Kinable

Try to just substitute \(y_i=1-z_i\) in the original problem and remember that \(\max f(x)=-\min-f(x)\)


answered 11 Mar '15, 18:36

Sune's gravatar image

accept rate: 20%

Thanks, that indeed is correct. I've updated my question with the answer.

(11 Mar '15, 20:42) Joris Kinable
Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported



Asked: 11 Mar '15, 17:29

Seen: 1,152 times

Last updated: 13 Mar '15, 15:04

OR-Exchange! Your site for questions, answers, and announcements about operations research.