The linear multiple choice knapsack problem with equity constraints
by George Kozanidis, Emanuel Melachrinoudis, Marius M. Solomon
International Journal of Operational Research (IJOR), Vol. 1, No. 1/2, 2005

Abstract: In this paper, we introduce an important variation of a well known problem, the linear multiple choice knapsack problem with equity constraints, which finds application in the allocation of funds to highway improvements. The multiple choice constraints are used to model the interactions that arise among different improvements. The equity constraints are introduced to ensure a balance on the budget amounts allocated to different sets of improvements. We present the mathematical formulation and show that this problem structure has several fundamental properties. These are used to develop an optimal two phase greedy algorithm for its solution. We report computational results which indicate that the algorithm is more efficient than a commercial linear programming package and the outperformance increases with problem size.

Online publication date: Wed, 20-Jul-2005

The full text of this article is only available to individual subscribers or to users at subscribing institutions.

 
Existing subscribers:
Go to Inderscience Online Journals to access the Full Text of this article.

Pay per view:
If you are not a subscriber and you just want to read the full contents of this article, buy online access here.

Complimentary Subscribers, Editors or Members of the Editorial Board of the International Journal of Operational Research (IJOR):
Login with your Inderscience username and password:

    Username:        Password:         

Forgotten your password?


Want to subscribe?
A subscription gives you complete access to all articles in the current issue, as well as to all articles in the previous three years (where applicable). See our Orders page to subscribe.

If you still need assistance, please email subs@inderscience.com