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:

1. 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.
2. 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.
3. 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

Answer 1

[Walter Roberson]

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.

[Christian Schumacher]

Thank you for your detailed answer!

[Christian Schumacher]

Dear Walter,

thank you again for the answer! I was able to implement a lot of my problems and solving them in very little time. I went with the intlinprog - method.

Now I have annother problem, and was wondering if you would have an advise for me! I I am now trying to implement categories for the names: every name is assigned to one or two of five categories. The solution with 8 names has to yield at least one player from every category. Is it possible to implement the constraint to my first problem?

I would really appriciate your help!

[Walter Roberson]

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]

Dear Walter,

Thank you again for your detailed answer! I was able to implement it, I have an optimizier now which picks at least one out of each category. My matrix A is looking ike this right now (as you suggested.

0	-1	-1	-1	0	0	0	0	0	-1
0	-1	-1	0	-1	0	0	0	0	-1
-1	0	0	0	-1	-1	-1	0	0	0
0	0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	-1	-1	0

and my b:

-1
-1
-1
-1
-1

what I was wondering now - how can I add this to the constraint from before? I need this constraint to meet the following the constraint, that the sum off the values from row 3, stay under 50.000.

My A-Matrix before looked like this:

3000	5500	3000	3000	7100	3500	3000	3100	3300	11200

and my b was just b = 50.000

I tried to mix up the matrices like this:

0	-5500	-3000	-3000	0	0	0	0	0	-11200
0	-5500	-3000	0	-7100	0	0	0	0	-11200
-3000	0	0	0	-7100	-3500	-3000	0	0	0
0	0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	-3100	-3300	0

and my b matrix like this:

-50000
-50000
-50000
-50000
-50000

but for this input no optimal solution can be found.

The code for this part is still really small and looks like below. The weird thing is, that I am getting no error - I just get no optimal solution. Do you have any suggestion, how to merge the both constraints?!

I am really thankful for your help!

Aeq = ones(1,length(f));
beq = 8;
lb = zeros(1,length(f));
ub = ones(1,length(f));
x = intlinprog(f,intcon,A,b,Aeq,beq,lb,ub);

[Walter Roberson]

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.