Skip to main content

# Tag Info

## Hot answers tagged set-covering

22 votes
Accepted

### Solving pricing problem heuristically in column generation algorithm for VRP

Generating routes heuristically, or heuristic pricing, is very common in the vehicle routing literature. Even when the pricing problem can be solved exactly, heuristic pricing is often tried first. ...
• 6,252
18 votes
Accepted

### Variable bounds in column generation

Assuming that the $a_{ij}$'s are either zero or one, and the $c_j$'s are positive, you do not need the upper bound on the variables. To see this, if $x_j=1$ for some $j$, then column $j$ covers all ...
• 6,657
12 votes

• 2,411
6 votes
Accepted

### Packing a number of unequal circles in a rectangle

You can determine whether such a packing is possible by solving a nonconvex quadratically constrained feasibility problem where the decision variables are the coordinates of the circle centers. See ...
• 33.2k
5 votes

### social network analysis - relations between people with weights

This is the minimum weight dominating set problem. You can solve it via integer linear programming as follows. For node $i \in S$, let $w_i$ be the weight and let $N_i \subseteq S$ be the set of ...
• 33.2k
4 votes

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

For a given set of dimensions, a sparse model is likely to be faster to solve than a dense one simply because fewer nonzero coefficients mean less arithmetic per iteration of whatever algorithm you ...
• 39.9k
4 votes
Accepted

### A more efficient way of solving an peculiar optimization problem

This problem is actually not an assignment problem but a set covering problem. Let's say that choosing customer $i$ is represented by $x_i=1$ when chosen, $0$ otherwise. Let's say $t_j$ are the sales ...
• 2,411
3 votes

### Variable bounds in column generation

Another understanding can be the following. Denote $X = \{ x \in \Bbb R^n \mid 0 \leq x_j \leq 1, \forall j = 1,\dots, n\}$. When solving the pricing problem successfully to optimal, all variable ...
• 512
3 votes
Accepted

### On dual-formulation of a given primal for a set-covering problem

It does not look correct, and in particular the dual of an LP is an LP, so it makes no sense to have a binary variable in the dual. I suspect what led you astray was a misunderstanding of the penalty ...
• 39.9k
2 votes

### How to correctly interpret the $\ln(n)$ approximation ratio of the set cover problem under its integer formulation context?

$n$ is the number of elements. Elements are what needs to be covered; therefore, the constraints.
• 2,643
2 votes

### Set covering SOTA methods and benchmarks

The instances from the literature are available here: http://people.brunel.ac.uk/~mastjjb/jeb/orlib/scpinfo.html Note that the set covering problem is a quite fundamental problem that can appear in ...
• 2,643
2 votes

### How to linearize a weighted maximum coverage problem?

I think there is no continuous form of the maximal covering location problem (MCLP) with a guarantee of providing the same optimal solution as the integer program. However, in addition to the ...
• 2,104
2 votes

### Solving pricing problem heuristically in column generation algorithm for VRP

I found a survey paper1 that talks about the heuristics for the VRP. In page 289 it is mentioned that: This formulation was first proposed by Balinski and Quandt (1964), but becomes impractical ...
• 8,677

Only top scored, non community-wiki answers of a minimum length are eligible