Skip to main content

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
0 answers
40 views

Complexity of cardinality constrained maximum weight independent set problem

Given a graph with a set of nodes and edges, the goal of the maximum independent set problem is to find the maximum number of vertices where no two vertices are adjacent. This is well-known NP-hard ...
Mostafa's user avatar
  • 2,104
1 vote
1 answer
50 views

Can sparse set cover problem be solved or approximated more efficiently comparing to its non-sparse counter part?

I am an electrical engineer who is currently working with some bench table placement problem, and suddenly my problem look pretty much like the set cover problem here. After that, some of my colleague ...
Tuong Nguyen Minh's user avatar
1 vote
1 answer
57 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
594 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
  • 543
2 votes
0 answers
43 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
134 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
  • 629
1 vote
0 answers
319 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
73 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,104
3 votes
1 answer
340 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
320 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
150 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
450 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
94 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
105 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
102 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
527 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,143