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.
16
questions
1
vote
1
answer
53
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 ...
- 53
3
votes
1
answer
526
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 ...
- 489
2
votes
0
answers
42
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 ...
- 561
1
vote
0
answers
115
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 ...
- 619
1
vote
0
answers
293
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
70
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,086
3
votes
1
answer
329
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
304
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
161
views
2
votes
1
answer
138
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
362
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
92
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
93
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 ...
26
votes
5
answers
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
8
votes
0
answers
101
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 ...
20
votes
3
answers
433
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,133