Optimization problems (general) // nchoosek optimization
显示 更早的评论
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
采纳的回答
Walter Roberson
2019-3-26
编辑：Walter Roberson
2019-3-26
0 个投票
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 个评论
Christian Schumacher
2019-3-26
Christian Schumacher
2019-3-30
Walter Roberson
2019-3-30
Add several rows to the A matrix, and corresponding values in the b vector.
For each category, create a row vector in which each name is set to -1 (negative!!) if the name belongs to the category, and 0 otherwise. So this might look like
-1 -1 -1 0 0 0 0 0 0 0 0 0 0
0 0 0 -1 -1 -1 -1 -1 0 0 0 0 0
0 0 0 0 0 0 0 0 -1 -1 -1 -1 -1
to indicate that the first 3 names are the first category, the 5 after that are the second category, the 5 after that are the third category.
Set the corresponding b entries all to -1
Recall here that the A b matrices are used for linear inequalities, A*x <= b . So where x is 0 for not selected and 1 for selected, the -1's only in one category end up counting the negative of the number of selected items in that category. And with the b entry being -1 that says that the negative of of the number of selected items must be <= -1 . Which, of course, is the same as saying that the count of the selected items must be >= 1 .
Do not use positive 1's here, only use -1's for this purpose. If you use +1's then, Yes, the counts would end up being directly the number of names in that category, but it would still be a <= operation. If you had count <= 1 then that would be satisfied by a count of 0, so you cannot use +1's to make constraints about the minimum number in each category. Now, if you also happened to have maximum numbers, so that you do not end up with (say) 1 in first, 1 in second, 1 in third, 1 in fourth, 15 in fifth, then you would use +1's to control those. +1's to control maximum counts, -1's to control minimum counts.
Christian Schumacher
2019-3-31
Walter Roberson
2019-3-31
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.
更多回答（0 个）
类别
在 帮助中心 和 File Exchange 中查找有关 Get Started with Optimization Toolbox 的更多信息
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!
Translated by 
