Different optimization solutions with weighted objective functions

Hi everybody,

I want so solve an optimization problem regarding integers in a matrix. I am using the problem-based approach with intlinprog.

The objective function is e.g.

f_1 = -sum(col(x(:,:,1))); % Maximize the 1s
f_2 = -sum(col(x(:,:,3))); % Maximize the 3s

w_1 = 1;
w_2 = 1;

w = 1;

fun = w*(w_1*f_1 + w_2*f_2);
prob.Objective = fun;

In this case the two parts of the objective function (f_1 and f_2) are weighted equally. But the optimized solution depends on the overall weighting factor w.

For example

for w=1 :

number 1s = 1

number 3s = 6

for w = 10:

number 1s = 3

number 3s = 4

for w = 50/ w = 100

number 1s = 1

number 3s = 6

for w = 150

number 1s = 3

number 3s = 4

So the total number of 1s and 3s is always the same, but the allocation of the numbers is different depending on w.

I thought that the number are always be the same because of the same weight w_1 and w_2. Why is the solution of the optimization dependent on the w? And why am I not getting the optimal solution, I think in thsi case that there are three 1s and four 3s when I am weighting the two objective functions the same?

I know it is not a complete example, I would like to understand in theory why the results can be different when the objective function is weighted.

Answer 1

[Bruno Luong]

They are all optimal solution since the number of 1 + number of 3 are 7 in 4 cases.

Your objective function (divided by w) are the same, there is no preference bwteen 4 solutions.

When your change the total weight the algorithm (cut and bounds) behave differently, it follow different trajectory (it is an iterative method) and ends uop at different solution. There is nothing to be puzzeled about it.

[b999]

So is it theoretically random at which w in this case the 1s or 3s get more or less?

[Bruno Luong]

It's deterministic since the intlinprog algorithm is deterministic (but complex). There is nothing random about it, just difficult to predict the outcome.

[b999]

Okay, thank you!

[Matt J]

It's deterministic since the intlinprog algorithm is deterministic

Although, you may find that the same code gives you different solutions on different CPUs.