Właściwości rozwiązań problemu plecakowego z ograniczoną podzielnością elementów

• Autorzy: Pieńkosz K.

Warianty tytułu

EN

Properties of the knapsack problem with restricted item fragmentation

• Konferencja: XV Krajowa Konferencja Automatyzacji Procesów Dyskretnych, Zakopane, 20-23 września 2006r.
• Języki publikacji: PL

Abstrakty

PL

W pracy jest rozpatrywany wariant problemu plecakowego, w którym dopuszcza się podział elementów podczas pakowania przy zastrzeżeniu, że waga umieszczanych w plecaku fragmentów nie może być mniejsza niż zadany parametr [beta]. Analizowane są właściwości rozwiązań optymalnych takiego problemu. Sformułowano warunki opłacalności pakowania poszczególnych elementów, co w wielu przypadkach umożliwia znaczącą redukcję wymiaru rozpatrywanego zadania.

EN

In the paper the semi-continuous variant of the knapsack problem is considered in which items may be fragmented into smaller pieces while putting them into the knapsack. Fragmentation is however subjected to the restriction that the weight of each piece cannot be smaller than the given parameter [beta]. In the paper the properties of the semi-continuous knapsack problem are investigated. It is shown how the optimal values of some variables may be fixed in advance and thus the size of the problem may be reduced.

Słowa kluczowe

PL

problem plecakowy; pakowanie; SCKP

EN

knapsack problem

• Wydawca: Wydawnictwo Politechniki Śląskiej
• Czasopismo: Zeszyty Naukowe. Automatyka / Politechnika Śląska
• Rocznik: 2006
• Tom: z. 144
• Strony: 189--195
• Opis fizyczny: Bibliogr. 5 poz.

Twórcy

autor

Pieńkosz K.

• Instytut Automatyki i Informatyki Stosowanej, Politechniki Warszawskiej, ul. Nowowiejska 15/19, 00-665 Warszawa, tel. [phone],

Bibliografia

• 1. de Farias LR Jr.: Semi-continous cuts for mixed-integer programming, Lecture Notes in Computer Science, vol. 3064, Springer Verlag, 2004, p. 163-177
• 2. Kellerer H., Pferschy U., Pisinger D.: Knapsack Problems, Springer Verlag, 2004.
• 3. Martello S., Toth P.: Knapsack problems: algorithms and computer implementations. Wiley, New York 1990.
• 4. Martello S., Pisinger D., Toth P: New trends in exact algorithms for 0-1 knapsack problem, European Journal of Operational Research, vol. 123, 2000, p. 325-332.
• 5. Pieńkosz K.: On solving the semi-contiuous knapsack problem, Proceedings of the 11th IEEE International Conference on Methods and Models in Automation and Robotics, 2005, p. 851-855.