Vietscholar forum - Xem bài viết đơn

**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.