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
3
votes
0answers
58 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 ...
2
votes
0answers
39 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 ...
3
votes
1answer
251 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 ...
5
votes
2answers
160 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 \...
2
votes
1answer
146 views
2
votes
1answer
61 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:
$min \left(\sum_{j=1}^{P} ...
3
votes
0answers
109 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 ...
3
votes
1answer
75 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&...
9
votes
0answers
75 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 ...
22
votes
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 ...
8
votes
0answers
82 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 ...
19
votes
3answers
251 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}
\]
...
