Optimization problems (general) // nchoosek optimization
4 views (last 30 days)
Show older comments
Christian Schumacher
on 26 Mar 2019
Commented: Walter Roberson
on 31 Mar 2019
Hello,
I am new too optimization in Matlab and new to optimization (had only the basics at university), so I am not looking for an exact code-solution (I think the project will be way to difficult to solve in just a few steps). What I am looking for, is advice which optimization methods in general and what specific
My problem is as follows:
- I have a table or cell given with follwing entries in every row: "Name_1", "Number_1"(an integer between 0-70), "Number_2"(another integer between 3000-12000). For every problem I want to solve, I have 40-80 rows per problem.
- My Problem is as follows: I need exactly 8 Names from the "Name_1"-column. The sum from the second column is the one, I want to have maximized. The only constraint I am having: The sum of the third column (the integer between 3000-12000) must be below or equal to 50000. In practise, there won't be an optimal solution, which has a sum-value under 48000.
- The perfect solution would also return the less optimal solution. So my perfect output would be a cell containing 100-200 entries. Every entry contains 8 names. The first one is the optimal, the second one is a little bit less optimal....
I already tried to solve this with nchoosek and some sorting methods, but with 80 choose 8 (28 billion) this isn't a practical solution. -> I figured out that I have to use an optimization method. Does anyone have a suggestion which matlab functions could be useful? or in general which optimization method could be useful?
I am looking forward to your answers.
Kind regards,
Christian
0 Comments
Accepted Answer
Walter Roberson
on 26 Mar 2019
Edited: Walter Roberson
on 26 Mar 2019
If you have a newer release, you can use problem-based optimization similar to https://www.mathworks.com/help/optim/examples/office-assignments-by-binary-integer-programming.html
With older releases, you would use https://www.mathworks.com/help/optim/ug/intlinprog.html
Your f would be the negative of your second column, arranged as a vector.
Your intcon would be 1:number_of_rows
Your A would have one row that is the values from your third column, arranged as a row. The corresponding b entry is 50000.
Your Aeq would be one row that is ones(1, number_of_rows), with corresponding beq entry of 8 (so exactly 8 variables are to be turned on.)
Your lb would be zeros(1,number_of_rows). Your ub would be ones(1,number_of_rows).
You would be using one binary variable for each row of your original data, with the value 0 being for not selected and the value 1 being for selected. The Aeq beq combination ensures that exactly 8 are selected. The A b combination ensures that the sum of the third column of the selected elements is <= 50000
The above would (try to) get you the optimal solution. For the less optimal solutions, use an options structure as well, and use OutputFcn with 'savemilpsolutions'. This will create xIntSol in your workspace where each column is a feasible solution. You could then do an appropriate matrix multiplication by your f matrix in order to calculate the value associated with that solution; sort in ascending order to get less and less good values. Remember these values will be the negative of what you are looking for: you find maxima by minimizing the negative of the system.
5 Comments
Walter Roberson
on 31 Mar 2019
Just use
[3000 5500 3000 3000 7100 .... etc
0 -1 -1 -1 0 .... etc
0 -1 -1 0 0 ... etc
]
b = [5500; -1; -1; -1; -1; -1];
Is it correct that you have overlapping categories? The second name is a member of both the first and second category?
Your 4th line of the -1 + 0 matrix shows all 0s; you should not end up with a row of all 0's for this kind of constraint.
More Answers (0)
See Also
Categories
Find more on Get Started with Optimization Toolbox in Help Center and File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!