Linearization does not give the expected result

MIDCP
1

I have x_j=\sum_{i=1}^Na_{i,j}f_{i,j}

The constraint is: x_j\ge ty_j

Here, a_{i,j}\in\{0,1\} is a binary variable and 0\le f_{i,j}\le 1 is a continuous variable.

In order to linearize the multiplication of a binary variable and continuous variable, I use the following linearization technique.

Let z_{i,j}=a_{i,j}f_{i,j}. From the Big-M linearization technique I have the following linear constraints
i. z_{i,j}\le a_{i,j}
ii. z_{i,j}\ge 0
iii. z_{i,j}\le f_{i,j}
iv. z_{i,j}\ge f_{i,j}-(1-a_{i,j})

since we have f_{i,j}^{lb} (lower bound of f_{i,j})=0 and f_{i,j}^{ub} (upper bound of f_{i,j})=3.

I can solve this in CVX. But, I do not the results I expect.

For some a_{i,j}=1, I have f_{i,j}=0. Why?

But, if a_{i,j}=1, I must have f_{i,j}>0.

What is the mistake here?

2

The constraints you have shown look like a correct implementation of the Big M method to handle the product of the binary and continuous variable.

But why should

if a_{i,j}=1, I must have f_{i,j}>0

be true?

You haven’t told us the entirety of your optimization problem, so I don’t know whether the situation you question should or should happen. But if it should not happen, that would have to due to some other portion of your optimization problem which you haven’t shown.

3

Here is the program I have:

Here a_{i,j} is an assignment indicator. every user has some demand. If user j is assigned to resource i, it gets some part of resource i. Its like if a person is assigned a room, he must get some resources in that room. Each room has some given amount of resources. One person can go to a maximum of 3 rooms to satisfy its demand. The total amount of resources collected by the people assigned to any room must not exceed the number of resources available in that room.

4

Can you now answer my question?

But why should

if a_{i,j}=1, I must have f_{i,j}>0

be true?

Can you show a complete (minimally-sized) reproducible problem, with CVX and solver output and all CVX variable values after completion, and tell us what is happening which should not be, and why the reported optimal solution is not optimal?

5

Here a_{i,j} is an assignment indicator. every user has some demand. If user j is assigned to resource i, it gets some part of resource i. Its like if a person is assigned a room, he must get some resources in that room. Each room has some given amount of resources. One person can go to a maximum of 3 rooms to satisfy its demand. The total amount of resources collected by the people assigned to any room must not exceed the number of resources available in that room.

6

You haven’t shown us the input data Y and R. Which part of your model formulation prevents a_{ij} = 1, f_{ij} = 0? Apparently, with the input data you are using, nothing is preventing that.

7

Here are the data

Y=[111459218 69402381 41554195 64915981 96088520 100738827 80956547 92148898 108575710 42139509 61849981 41458371 53281759 94837132 94962859];

R=1000.*[180000 180000 90000 144000 0 72000 81000 121500 180000 0 0 64800 0 0 0; 180000 180000 90000 144000 0 72000 81000 121500 180000 0 0 64800 0 0 0; 0 135000 180000 180000 64800 180000 180000 0 180000 135000 135000 180000 54000 54000 0; 0 135000 180000 180000 64800 180000 180000 0 180000 135000 135000 180000 54000 54000 0; 0 0 180000 121500 180000 180000 180000 0 135000 135000 0 180000 0 135000 0; 0 0 180000 121500 180000 180000 180000 0 135000 135000 0 180000 0 135000 0; 0 97200 81000 72000 0 97200 81000 180000 180000 144000 180000 81000 162000 0 0; 0 97200 81000 72000 0 97200 81000 180000 180000 144000 180000 81000 162000 0 0; 0 0 180000 81000 72000 180000 180000 162000 172800 180000 180000 180000 180000 180000 0; 0 0 180000 81000 72000 180000 180000 162000 172800 180000 180000 180000 180000 180000 0; 0 0 121500 0 135000 162000 144000 0 0 172800 135000 162000 97200 180000 180000; 0 0 121500 0 135000 162000 144000 0 0 172800 135000 162000 97200 180000 180000 ];

I get, a_(4,4)=1, but f_{4,4}=0

8

Then, how can I prevent this?

9

Y and R have horrible scaling. Entries are very big. That can possibly cause problems with integrality tolerance in the solver. Try to improve the scaling, and you can also decrease the integrality tolerance of the solver using cvx_solver_settings http://cvxr.com/cvx/doc/solver.html#advanced-solver-settings

1 Like
10

Thanks, I will try them.

11

Fundamentally though, there is nothing preventing the situation you don’t like from happening. Your scaling is terrible, but Idon’t think that’s the problem.

The optimal objective value is 1.87098, but the optimal solution is not unique. Playing around with the scaling or optimality tolerance could happen, BY LUCK, to cause a different optimal solution to be found, and that solution may or may not be more to your liking. Also, using a different solver could result in a different optimal solution to be found.

It sounds like you have a deficient model for your purpose, rather than being a matter of CVX implementation.

1 Like