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.
13
questions
1
vote
0
answers
75
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 ...
- 499
1
vote
0
answers
189
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
2
votes
0
answers
54
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,054
3
votes
1
answer
275
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
5
votes
2
answers
228
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
2
votes
1
answer
153
views
2
votes
1
answer
114
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\...
- 668
3
votes
0
answers
206
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 ...
- 668
2
votes
1
answer
87
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
9
votes
0
answers
87
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 ...
24
votes
5
answers
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 ...
- 12.7k
8
votes
0
answers
87
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
3
answers
333
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,011