21

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. Only when no more routes can be generated by heuristics, the exact pricing algorithm is run. When heuristic pricing is used in this way, the overall method is ...


18

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 items, $i$, where $a_{ij}=1$ and it does not cover any other items. Increasing $x_j$ to $1+\varepsilon$, for some $\varepsilon>0$, will increase the cost, and ...


9

When pricing $x_j$, there are two possibilities: $x_j$ is not in the restricted master problem / $x_j$ has not been added before. In this case, $x_j=0$ in the current solution. The constraint $x_j \le 1$ is not active, such that the associated multiplier is equal to 0. It is thus not a problem that the constraint was not added to the restricted master ...


8

The general rule is to use dynamic programming (Labeling Algorithm) to solve the VRP pricing problem. It has some advantage over solving the mathematical model. DP can yield many columns in each iteration versus the one column that yielded by solving the model. As @Kevin Dalmeijer mentioned you need to be able to solve the pricing problem exactly even if you ...


6

There are two possible situations. 1) You still want to solve your VRP exactly or obtain a valid lower bound. Then heuristic pricing is used only to speed up column generation (and it is always used nowadays). At the end, you always need to solve the pricing problem (or at least its relaxation) exactly. A standard approach for heuristic pricing is some ...


6

Contrary to the other answers, I claim that you don't need to solve the pricing problem exactly, not even as a last resort after trying heuristics. If you do solve it exactly, then you found the optimal solution (say $z^*_\text{LP}$) to the relaxed reduced master problem at the node. But this is not needed: you want to use $z^*_\text{LP}$ as a lower bound ...


5

Let us get some additional insights by assuming $d_{ij} \in \{0,1\}$ and interpreting the data as a directed graph. For now we assume the number of $i$'s and $j$'s is the same, but I don't think it will be difficult to generalize that assumption. We say there is an arc from $i$ to $j$ iff $d_{ij} \neq 0$. Now for each vertex $j$ where $s_j \neq 0$, we have ...


5

The problem is NP-hard because it can be used to solve the subset-sum problem: Subset-sum: given a set of numbers $a_k\forall k\in K$ and a special number $b$ is there a subset of numbers $K' \subset K$ such that $\sum_ {k\in K'} a_k =b$ Reduction: let $j \in \{1,2\}$, and $s_1=b$ $d_{k,j} = a_k \forall k,j$ and $s_2=\sum_i a_i - b$ I don't know of any ...


4

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 neighbors. Let binary decision variable $x_i$ indicate whether $i \in D$. The problem is to minimize $\sum_{i \in S} w_i x_i$ subject to $$x_i + \sum_{j \in N_i} ...


4

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 targets for your products and $d_{ij}$ is the "demand" or probability to sell product $j$. \begin{align} \min&\quad\sum_i x_i \\ \text{s.t.}&\...


3

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 bound constraints will be satisfied. Therefore, you only need to track the dual variables $\pi$ of those 'hard' constraints which are $$\sum\limits_{j=1}^na_{ij}...


3

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 portion of the primal objective. You can rewrite the primal objective as \begin{gather*} \sum_{j=1}^{P}c_{j}x_{j}+P_{Dhd}\left[\sum_{i=1}^{F}\sum_{j=1}^{P}a_{ij}...


2

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 formulation OP presented, Church & ReVelle (1974)1 proposed a second formulation for the problem in their breakthrough paper, that is as follows: \begin{alignat}4 ...


2

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 when $|S|$ is large. Agarwal et al. (1989) have used column generation to solve small instances of the VRP optimally. Heuristic rules for producing a promising ...


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