Hi all,I am trying to select bonds from a given pool under multiple criteria/constraints such as maximum individual obligor concentration limit, maximum Weighted average rating, maximum country concentration limit etc. The objective is to maximise the sum of par/book value/market value of the selected bonds. the size of pool ranges from 200 to 300 namesCan anyone suggest any non-heuristic optimization methodology used to solve this kind of problem? Any literature references will also be most welcome.Thanks

Unless I am issing something, sounds like classic linear programming,see also the Simplex method.regards,

Hi Alan,The problem as i received it is of the form Subject towhere e_i is the exposure of ith bond,WARF_i is the weighted average rating factor for the i'th bond,WARF{max} is the WARF limit for the poolCONC{max} is the maximum concentration allowedx_i is a zero-one variable indicating inclusion or exclusion of the ith bondi can be from 1 to 200-300I lineraized both constraints by multiplying both sides with the sigma terms in denominators and collecting all x_i's on one side, then tried solving using implicit enumeration in VBA. It works but takes very long (e.g with i = 1 to 180, and only the WARF constraint, it takes 2 hours)I was thinking that maybe i am doing something wrong here. There might be some better way of formulation to handle the Weighted average/concentration constraints or there might be a faster algorithmIf you know any better way, please let me know.Thanks

Hi Chiranjiv,Whare is the idea behind what you are trying to do here? I may be able to help. Tell me what are you trying to do?

I see -- it's linear programming with integer constraints.This is called integer programming, which I have never tried.Googling turned up an algorithm called 'branch and bound', whichmight help you.

Actually, come to think of it, This is a typical problem that is used in Index replication as well, when a portfolio manager is trying to replicate the benchmark.I have seen some models that can handle this pretty well within VBA. What i think you are doing here is nothing wrong. I think your run time should improve, if you use some other optimization toolDid you try formulating this problem in SAS.Should be matter of few minutes for SAS

Alan- Yes, this is a special class of integer programming (In integer programming, the variables can take any integer values but here they can only be 0-1). The branch and bound algorithm is a well-known algorithm for solving integer programming problems. It involves solving the problem as an LP without the integrality constraint and then searching for integer solutions. The algorithm I implemented(implicit enumeration) is a specialized form of the branch-and-bound which does away with the overhead of solving the LP's capitalizing on the binary nature of the variables. I tried the general branch-and-bound as it is implemeneted in Excel Solver, I found that the there are no feasible results or the results are not optimal, depending on the starting values of x_i's!! Thanks for taking the trouble to look it up....Devilish-You are right about using a better tool..Well, that is an constraint on me ! The resulting program has to be shared with users with no access to SAS so I am stuck with VBA! The context of the problem is pretty familiar:Selection of assets from a given pool for securitization under some market/rating agencies specified guidelines.I am just trying to speed up the manual process!As you can easily notice the problem has a search space of 2^n possible compbinations (where n is the number of bonds) without the use of any optimization algorithm. Additionally, the Weighted Average/Concentration constraints are AGGREGATE constraints i.e. they can't be evaluated for feasibility unless all the x_i's are specified, whereas branch and bound type methods work one x_i at a time making the search inefficient esp. with VBA. If anyone has any experience of using a better methodology for such problems please let me know......I am sure some analytics shops have tackled the issue..Thanks Alan, devilish for your comments

any ideas? anyone?