Which optimization algorithm should I use for maximizing profit with time limitations?

I would like to find an appropriate algorithm to solve this problem:

Suppose we have N projects and we know how much money we will earn by each project and how much time it is required for each project to be done(estimated time for each project). We have certain amount of available time to do all projects. We want to select projects so that our profit is maximized and overall estimated time does not exceed available time. Can you please advise which optimization algorithm should I u开发者_C百科se? Are there any already made things that I could use in C#, .NET technology or Java technology?

---

This sounds like straightforward Knapsack problem:

Given a set of items, each with a weight and a value, determine the count of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.

In your case, the weight is the time required for the projects, and the limit is the time limit.

Normally, if you are doing this for the real world, then a brute-force would suffice for the small cases, and greedy approximation with some randomization should be good enough for the large cases if you don't really care for the accurate maximal. However, I doubt if anyone would use such a strict model for the real world.

In the case of theoretical interest, knapsack problem is NP-hard, and an active field of algorithm.

---

What you're looking for is called the Knapsack problem.

in your case the "weight" limit is the time limit, and the value is the value.

---

Simplified, this looks like a weighted http://en.wikipedia.org/wiki/Knapsack_problem. Your time would be the size of the project and your weight would be your costs

---

Coming at this problem from an Operations Research perspective you are looking at some for of mixed-integer program (MIP). The knapsack problem approach might be sufficient but without getting more specifics on the problem I can't suggest a more detailed formulation.

Once you've decided on your formulation there are a couple of c# solutions available to solve the MIP. Microsoft has a Microsoft Solver Foundation that you can look into that is capable of solving simple MIPs and that has a nice C# API

IBM recently purchased the OPL optimization package (considered industry leading) that you can use to develop your MIP formulation. Once you have the formulation OPL offers .NET APIs that you can call to run your models.

Having gone the OPL route myself I would avoid using the OPL .NET APIs if possible because they are very cumbersome. If your problem is simple you may want to look into solver foundation because it offers a modern and clean API as compared to the OPL