0
$\begingroup$

I would like to scale my linear/integer program and also mixed-integer program using the equilibrium scaling method. I have worked on two research papers and one research book. However, they did the same thing in different ways (in a somewhat conflicting manner) so I would like to learn what is the correct way to scale linear/integer program or/and mixed-integer program.

My observations so far: The book creates a row and column scaling factors first. To find the row scaling factor, at first it find biggest elements in all rows and then it becomes divisor in a following manner: [ 1/max(first row); 1/max (second row); 1/max(third row). To find column scaling factor it does the same thing for the columns. Finally, it multiplies matrix A first with row scaling factor and then column scaling factors and creates scaled A. It multiplies b with row scaling factor and creates scaled b. It multiplies c with column scaling factor and creates scaled c. I think the following example from the book explains everything. enter image description here

Therefore, there is one 3x1 column scaling factor matrix and one 4x1 column scaling factor matrix for a 3x4 A matrix.

On the other hand, both of the articles mention R and C diagonal matrices that are used in the scaling LP/IPs. The first article also differentiates MIP scaling from IP/LP scaling. It says "Note that for a for MIP, integer columns are not scaled..." Does it mean numbers that are integers do not enter scaling or does it mean columns that represent integers in MIP do not enter scaling? A full description from the first article could be seen below. enter image description here

The paragraphs continue with the statement that: "...ST first scales rows by dividing each row by the absolute value of the nearest power of two of its largest element and then scales columns in the same fashion."

The second article is a very old one. Actually, it is one of the oldest papers about the Scaling of linear programs. In a similar manner, it mentions R and C diagonal scaling factors. You can see the way it describes;

enter image description here

To sum up, I have been working on scaling applications in C++, so far I have applied the Equilibrium scaling method in a way it is described in the book. However, the articles confused me with diagonal matrices, the reason is how R and C are created is not explained properly in both of those articles. My question is if these diagonal matrices play role in the scaling, How can I create these diagonal R and C matrices from the A matrix given to me. Let's assume our A matrix is the one given above in the picture.

If they do not play role in equilibrium scaling, can I just assume the way the book uses is the correct and proper way to conduct equilibrium scaling?

All three sources in MLA format could be seen below.

The Book: Ploskas, Nikolaos, and Nikolaos Samaas. Linear Programming Using MATLAB®. Vol. 127. Switzerland: Springer, 2017.

First Article: Berthold, Timo, and Gregor Hendel. "Learning to scale mixed-integer programs." Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 5. 2021.

Second Article: Tomlin, John A. "On scaling linear programming problems." Computational practice in mathematical programming. Springer, Berlin, Heidelberg, 1975. 146-166.

EDIT: If you are saying they are the same thing, I would be more than welcome if you can prove your point.

enter image description here enter image description here

Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
5
$\begingroup$

Regarding integer columns, it means the columns that correspond to integer variables. The $j\in \mathcal{I}$ notation makes that explicit. The idea is that scaling continuous variables preserves problem structure in the sense that you can solve the problem in the scaled space and then postsolve to unscale back to the original space. For integer variables, such scaling does not generally preserve integrality.

Improve this answer
$\endgroup$
7
  • $\begingroup$ What about R and C diagonal matrices, do they required or can I just use the method described in the book? $\endgroup$
    – asdf
    Apr 11, 2022 at 7:04
  • $\begingroup$ Multiplication by the diagonal matrices is equivalent to the method in the book. $\endgroup$
    – RobPratt
    Apr 11, 2022 at 13:08
  • $\begingroup$ Can you explain why they are equivalent to the method in the book, then I can approve your answer $\endgroup$
    – asdf
    Apr 21, 2022 at 13:40
  • 2
    $\begingroup$ It follows directly from the definition of multiplication by a diagonal matrix. I recommend explicitly writing out $R$ and $C$ and the corresponding matrix inequalities for your small example to see what's going on. $\endgroup$
    – RobPratt
    Apr 22, 2022 at 14:22
  • $\begingroup$ Hello @RobPratt But for instance, r in the first picture is not a diagonal matrix, it is 3x1 matrix, how does it make the same thing with a diagonal matrix? Could you please explain a bit more? I have written them on paper to see them more clearly. I have also added all pictures and how they are creating a new A matrix. I could not see how they are related to a diagonal matrix. $\endgroup$
    – asdf
    Apr 22, 2022 at 14:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.