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.

Filter by
Sorted by
Tagged with
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 ...
Elam Harnish's user avatar
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 ...
OR Junior's user avatar
  • 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 ...
Daniele Cuomo's user avatar
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 ...
mars's user avatar
  • 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..!
user3237357's user avatar
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 ...
Mostafa's user avatar
  • 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 ...
czaduu's user avatar
  • 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 \...
dgamboz's user avatar
  • 135
2 votes
1 answer
161 views

A more efficient way of solving an peculiar optimization problem

Given the table ...
dgamboz's user avatar
  • 135
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\...
Divyam Aggarwal's user avatar
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 ...
Divyam Aggarwal's user avatar
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&...
foliveira2's user avatar
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 ...
German Velasquez Diaz's user avatar
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 ...
LarrySnyder610's user avatar
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 ...
Thomas Kalinowski's user avatar
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} \] ...
Djames's user avatar
  • 1,133