# 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.

12 questions
Filter by
Sorted by
Tagged with
44 views

### Optimal Seat Allocation Problem

I have to do an operations research assignment based on optimal seat allocation. The problem goes something like this. There are 5 rooms in an office each with a separate seating capacity. We now have ...
34 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 ...
248 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 ...
153 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 \...
145 views

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

Given the table ...
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: min \left(\sum_{j=1}^{P} ... 0answers 94 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 ... 1answer 74 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&... 0answers 73 views ### Adjusting duals heuristically 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 ... 5answers 1k 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 ... 0answers 81 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 ...
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} ...