# Questions tagged [set-covering]

For questions related to the set covering problem. Having a set of elements, S, and a collection of sets whose union equals S, the set covering problem tries to identify the smallest sub-collection of sets whose union equals S.

18 questions
Filter by
Sorted by
Tagged with
1 vote
40 views

### Complexity of cardinality constrained maximum weight independent set problem

Given a graph with a set of nodes and edges, the goal of the maximum independent set problem is to find the maximum number of vertices where no two vertices are adjacent. This is well-known NP-hard ...
• 2,104
1 vote
50 views

### Can sparse set cover problem be solved or approximated more efficiently comparing to its non-sparse counter part?

I am an electrical engineer who is currently working with some bench table placement problem, and suddenly my problem look pretty much like the set cover problem here. After that, some of my colleague ...
1 vote
57 views

### Set covering SOTA methods and benchmarks

I want to compare different methods for Set Covering problem. So I have 2 questions: what are the best methods for solving this problem (precise and not precise methods) what are the most common ...
594 views

### Packing a number of unequal circles in a rectangle

Given the dimension of a rectangle and the radii of n unequal circles, how can I decide if these circles can fit in the rectangle? I don't know if there is a formula to compute such a thing! The ...
• 543
43 views

### Shortest (undirected) path constrained to a sub-set of nodes

I expect this to be an NP-complete problem, as it may reduce to the Hamiltonian Path problem. Anyway, I was wondering whether there exists some study and (aproximated) solutions for this particular ...
1 vote
134 views

### Set Partitioning Formulation of PDPTW

I am studying a paper on a Pickup Dropoff Problem with Time Window (https://pubsonline.informs.org/doi/abs/10.1287/trsc.1090.0272 ). The three index formulation is straightforward. The formulation is ...
• 629
1 vote
319 views

### Set Covering and Column Generation

I need some set covering and column generation examples in OR-Tools python. If anyone can provide or direct me to some resources that would be great..!
• 137
73 views

### Is this a common generalization of the independent set problem?

Suppose a minimum weighted independent set in a conflict graph with $n$ vertices. The basic version is where each vertex $i$ is associated with a weight $c_i$. i.e., there is a vector $C$ for the ...
• 2,104
340 views

### social network analysis - relations between people with weights

I asked this question on datascience.stackexchange but they directed me here. I have a social network represented as a set of people $S$ and individual weights for each of person (weight is the cost ...
• 39
320 views

### Polynomial algorithm for a special ILP problem

Given the following problem: \begin{align} & z=\min \sum_{ij} x_{ij}\\ \text{s.t.} & \quad \sum_i d_{ij} x_{ij} \ge s_j, \quad \forall j \tag1 \\ & \quad \sum_j x_{ij} \le 1, \quad \...
• 135
161 views

### A more efficient way of solving an peculiar optimization problem

Given the table ...
• 135
150 views

### On dual-formulation of a given primal for a set-covering problem

I need to solve an LP-relaxation of an airline crew pairing optimization problem (CPOP). The problem formulation is a modified SCP and is as follows: Primal of the CPOP: \begin{align}\min&\quad\...
450 views

### On solving the Restricted Master Problem in Column Generation technique

I am working on developing a column generation (CG) based optimization framework for a large-scale airline crew pairing problem (a set-covering problem). First, I generate an initial feasible solution ...
94 views

### How to linearize a weighted maximum coverage problem?

Is it possible that the binary variables below be modeled as continuous variables? \begin{alignat}2\max&\quad\sum _{{e\in E}}w(e_{j})\cdot y_{j}\\\text{s.t.}&\quad\sum {x_{i}}\leq k,\quad&...
• 101
105 views

I am solving a scheduling problem-to find shifts and task schedules- using column generation. In essence, it is a set covering problem with additional constraints. The problem seems to be that the ...
2k views

### Solving pricing problem heuristically in column generation algorithm for VRP

In the set covering/column generation approach for the VRP (Balinski and Quandt (1964), or e.g. this tutorial), the basic idea is: Generate some routes. Solve the set covering problem using those ...
• 13.1k
102 views

### Examples for a kind of "set family hitting" problem

Given a ground set, say $[n]=\{1,2,\dots,n\}$, and a collection of subset families $\mathcal F_i\subseteq 2^{[n]}$, $i=1,2,\dots,m$, I want to select $m$ sets $B_i\in\mathcal F_i$ such that the ...
527 views

### Variable bounds in column generation

Consider the set covering problem \begin{align} \min&\ \sum_{j=1}^nc_jx_j\\ s.t.:&\ \sum_{j=1}^na_{ij}x_j\geq 1,\quad \forall i=1,\dots,m\\ &\ 0\leq x_j \leq 1 \end{align} ...
• 1,143