Cover Inequalities

**fool** · #1 (**permalink**) 07-07-2009

Xét 0-1 knapsack set $K=\left\{ x\in\left\{ 0,1\right\} ^{N}:\sum_{j\in N}a_{j}x_{j}\leq b\right\}$ với các hệ số không âm. $a_{j}\geq0$ với $j\in N$ và $b\geq0.$

Đn: Tập $C\subseteq N$ là 1 cover nếu

$\lambda=\sum_{j\in C}a_{j}-b>0$

Ngoài ra, Cover C là minimal nếu $a_{j}\geq\lambda$ với mọi $j\in C$ .

Định lý (OK): Gs $C\subseteq N$ là 1 cover. Cover inequality

$\begin{equation} \sum_{j\in C}x_{j}\leq|C|-1 \end{equation}$

là valid cho K. Ngoài ra, nếu C là minimal, thì bdt này xác định một facet của $conv(K_{C})$ với $K_{C}=K\cap\{x<img src=$ _{j}=0,j\in N\backslash C\}">

------------------------------------
Xét mixed 0-1 knapsack set

$S=\left\{ (x,s)\in\{0,1\}^{N}\times\mathbb{R}_{+}:\sum_{j\in N}a_{j}x_{j}\leq b+s\right\}$

với các hệ số không âm. $a_{j}\geq0$ và $b\geq0.$

Định lý : Gs $C\subseteq N$ là 1 cover. Bdt

$<br /> \sum_{j\in C}\text{min}(a_{j},\lambda)x_{j}\leq\sum_{j\in C}min(a_{j},\lambda)-\lambda+s<br />$

là valid cho S. Ngoài ra, bdt này xác định 1 facet cho $conv(S_{C})$ với $S_{C}=S\cap\{x<img src=$ _{j}=0,j\in N\backslash C\}">.

Bác nào có thể giải thích giúp cái đối với mixed knapsack set S thì s ở vế phải có ý nghĩa gì hay ứng với cái gì trong thực tế (mô hình 1 bài toán nào đó). Khi s=0 thì nó là knapsack thông thường và tôi đã OK. Và cái bdt bên dưới này dịch ra tiếng Việt (hiểu 1 cách dân dã) thì nó nói lên cái gì. Cái cover inequality bên trên thì tôi đã Ok. Cái bên dưới này tôi cũng đã xoay sở chứng minh được nhưng chưa hiểu về thực tế nó mô tả cái gì, phải Việt hóa được nó thì mới có thể hiểu lâu được.

Mấy cái này tôi đọc trong 2 bài báo:

a. Cutting planes in integer and mixed integer programming
b. Valid Inequalities for Mixed Integer Linear Programs

bác nào cần thì ghi lên forum.

**fool** · #2 (**permalink**) 07-07-2009

Xét flow set tại một nút: $X=\left\{ (x,y)\in\left\{ 0,1\right\} ^{N}\times\mathbb{R}_{+}^{N}:\sum_{j\in N}y_{j}\leq b,y_{j}\leq a_{j}x_{j},j\in N\right\}$ và $C \subseteq N$ là flow cover,

yj: luồng qua cung thứ j.
aj: luồng tối đa qua cung thứ j.
xj: 0 - nếu không có luồng qua cung thứ j - 1 nếu có luồng qua cung thứ j.
Cần chuyển không quá b đơn vị qua nút này theo các cung.

Dựa vào bdt bên trên hoặc cm trực tiếp, thu được bdt sau:

Đly: giả sử $C\subseteq N$ là flow cover với $\text{max}_{j\in C}a_{j}>\lambda$ .Bdt $\begin{equation}\sum_{j\in C}\left[y_{j}+(a_{j}-\lambda)^{+}(1-x_{j})\right]{\displaystyle \leq}b\end{equation}$ là 1 facet defining inequality cho conv(X).

Cái này tôi translate ra tiếng Việt nghĩa là nếu chưa bão hòa thì ta có thể gửi $(a_j - \lambda)^{+}$ đơn vị luồng trên mỗi cung chưa được sử dụng (các cung mà có y_j bằng 0 hay x_j = 0 tương ứng). Còn phần sau thì chưa (có thể đọc mục 9.2.3 - IP của Wosley về các pp cm).

Chắc biên dịch như thế là chính xác, nhưng nó còn có 1 version khác mạnh hơn nữa mà tôi mới đọc và chưa chứng minh và tất nhiên là chưa chuyển thành ý nghĩa cụ thể được (page 191. mục 9.4.1 . proposition 9.6 - Integer Programming, của Wosley).

**fool** · #3 (**permalink**) 07-10-2009

Bây giờ xét tiếp cái flow set này, cái flow set bên trên mới chỉ có vào chứ không có ra, cái này thì có cả 2 (nội dung chi tiết xem cuốn IP của Wosley)

$X=\left\{ (x,y)\in R_{+}^{n}\times B^{n}:\sum_{j\in N_{1}}x_{j}\leq b+\sum_{j\in N_{2}}x_{j},x_{j}\leq a_{j}y_{j}\text{for }j\in N_{1}\cup N_{2}\right\} .$

Và cái này có thể được xem là feasible region của bt fixed charge flow network.

Đn : Tập $C=C_{1}\cup C_{2}$ with $C_{1}\subseteq N_{1},C_{2}\subseteq N_{2}$ là một generalised cover cho X nếu $\sum_{j\in C_{1}}a_{j}-\sum_{j\in C_{2}}a_{j}=b+\lambda$ với $\lambda>0$ . $\lambda$ được gọi là (cover-) excess. NGhĩa là tập cạnh C1, C2 cho phép luồng qua nó thỏa mãn dấu =.

Đly : Flow cover inequality $<br /> \sum_{j\in C_{1}}x_{j}+\sum_{j\in C_{1}}(a_{j}-\lambda)^{+}(1-y_{j})\leq b+\sum_{j\in C_{2}}a_{j}+\lambda\sum_{j\in L_{2}}y_{j}+\sum_{j\in N_{2}\backslash(C_{2}\cup L_{2})}x_{j}$ là đúng cho X với $L_{2}\subseteq N_{2}\backslash C_{2}$ .

BDT này có thể cm tương tự như bên trên nhưng ko phải là facet (nghĩa là ko phải là bdt cần thiết để mô tả conv(X)). Với vài dk thì nó sẽ trở thành facet (xem sách IP).

Và tôi dịch là : nếu chưa bão hòa thì sẽ có cách tăng luồng vào và cách điều thiết lập luồng ra dựa vào bdt trên (gán giá trị luồng bao nhiêu cho từng cạnh để thỏa mãn đk luồng).

Các bdt này được dùng để cut đi các nghiệm fractional của bài toán relax đối với biến y.