The cardinality constrained multiple knapsack problem

Download

index.pdf

Date

2008

Author

Aslan, Murat

Metadata

Show full item record

Item Usage Stats

172
views

57
downloads

The classical multiple knapsack problem selects a set of items and assigns each to one of the knapsacks so as to maximize the total profit. The knapsacks have limited capacities. The cardinality constrained multiple knapsack problem assumes limits on the number of items that are to be put in each knapsack, as well. Despite many efforts on the classical multiple knapsack problem, the research on the cardinality constrained multiple knapsack problem is scarce. In this study we consider the cardinality constrained multiple knapsack problem. We propose heuristic and optimization procedures that rely on the optimal solutions of the linear programming relaxation problem. Our computational results on the large-sized problem instances have shown the satisfactory performances of our algorithms.

Subject Keywords

Industrial engineering.

URI

http://etd.lib.metu.edu.tr/upload/12610131/index.pdf
https://hdl.handle.net/11511/18079

Collections

Graduate School of Natural and Applied Sciences, Thesis

Suggestions

OpenMETU
Core

The general lot sizing and scheduling problem with sequence dependent changeovers Koçlar, Ayşe; Süral, Haldun; Department of Industrial Engineering (2005) In this study, we consider the General Lot Sizing and Scheduling Problem in single level capacitated environments with sequence dependent item changeovers. Process industries may be regarded as suitable application areas of the problem. The focus on capacity utilization and intensively time consuming changeovers necessitate the integration of lot sizing and sequencing decisions in the production plan. We present a mathematical model which captures the essence of cases in the most generic and realistic setti...
The biobjective traveling salesman problem with profit Şimşek, Ömür; Karasakal, Esra; Department of Industrial Engineering (2007) The traveling salesman problem (TSP) is defined as: given a finite number of cities along with the cost of travel between each pair of them, find the cheapest way of visiting all the cities only once and returning to your starting city. Some variants of TSP are proposed to visit cities depending on the profit gained when the visit occurs. In literature, these kind of problems are named TSP with profit. In TSP with profit, there are two conflicting objectives, one to collect profit and the other to decrease ...
The inventory routing problem with deterministic order-up-to level inventory policies Pınar, Özlem; Süral, Haldun; Department of Industrial Engineering (2005) This study is concerned with the inventory routing problem with deterministic, dynamic demand and order-up-to level inventory policy. The problem mainly arises in the supply chain management context. It incorporates simultaneous decision making on inventory management and vehicle routing with the purpose of gaining advantage from coordinated decisions. An integrated mathematical model that represents the features of the problem is presented. Due to the magnitude of the model, lagrangean relaxation solution ...
A probabilistic approach to multi criteria sorting problem Buğdacı, Aslı Gül; Köksalan, Murat; Department of Industrial Engineering (2009) We aim to classify alternatives evaluated in multiple criteria among preference ordered classes assuming an underlying additive utility function. We develop a probabilistic classification method by calculating the probability of an alternative being in each class. We assign alternatives to classes based on threshold probabilities. We require the decision maker to place an alternative to a class when no alternatives satisfy the required thresholds. We find new probabilities for unassigned alternatives in the...
The budget constrained discrete time/cost trade-off problem in project networks Değirmenci, Güvenç; Azizoğlu, Meral; Department of Industrial Engineering (2008) The time/cost trade-off models in project management aim to compress the project completion time by accelerating the activity durations at an expense of additional resources. The budget problem in discrete time/cost trade-off scheduling selects the time/cost mode -among the discrete set of specified modes- for each activity so as to minimize the project completion time without exceeding the available budget. There may be alternative modes that solve the budget problem optimally, however each solution may ha...

Citation Formats

M. Aslan, “The cardinality constrained multiple knapsack problem,” M.S. - Master of Science, Middle East Technical University, 2008.