Jump to content

Help with combinatorial optimization

Recommended Posts

Hi all,

I need a little help regarding simple optimization:

There are a given number of pairs of positive numbers for e.g. [latex](a_1, b_1), (a_2, b_2)... (a_N, b_N)[/latex]. The objective is to choose a subset [latex]S[/latex] of some pairs:


[latex]\max \sum_{i \in S} a_i[/latex]


s.t [latex]\sum_{i \in S} b_i\le B[/latex]

In other words, this problem can be thought as follows: You have some bank balance [latex]B[/latex] and there are number of different products in the market of price lets say [latex]b_i[/latex] that give some utility [latex]a_i[/latex]. Objective is to maximize utility (choose some number of products) subject to bank balance. What are such kind of problems called? Also, you can also assume that whenever [latex]b_1>b_2[/latex], then [latex]a_1>a_2[/latex] that is whenever something is expensive, it also gives better utility. I am not sure if this could be important.


Also if possible, can someone suggest how could this be solved (a fast method rather than exhaustive search)? (Taking the maximum [latex]a_i[/latex]'s until the budget is satisfied is not optimal in general for e.g. large number of small cheap products can give better overall utility than fewer high utility expensive products).



Edited by moterpoker
Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
  • Create New...

Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.