# Coefficient Scaling for MIP

I have a coefficient matrix for an MIP with a less than ideal range of magnitudes. For example, consider this constraint:

$$\sum_{ij} {\rm cost}_{ij} \cdot x_{ij} \leq \rm Budget$$ $$x_{ij} \in \{0, 1\} \; \forall i,j$$ where the cost of a specific $$i$$, $$j$$ pair may be $$10^{-2}$$ and the RHS might be $$10^{10}$$

I remember either hearing or reading that masking this scaling through another variable(s) doesn't actually help. Is that correct? For example:

$$10^{-3} \cdot \sum_{i} x_{ij} = {\rm scaledcount}_{j} \; \forall j$$ $$\sum_{j} {\rm cost}_{j} \cdot {\rm scaledcount}_{j} \leq {\rm Budget}^*$$ $$x_{ij} \in \{0, 1\} \; \forall i,j$$ $${\rm count}_{j} \in \mathbb{R} \; \forall j$$

where Budget can now be scaled back by $$10^{-3}$$.

Is the assumption that this approach doesn't strengthen the model scaling correct?

• How high do $i$ and $j$ go? This is critical to a scaling solution. Jul 26 at 0:22
• In this particular case i = 10^7 and j = 10^3, but I am interested in understanding for other ranges as well. Jul 26 at 13:33
• I assume you mean $i \le 10^7$ and $j \le 10^3$ Jul 26 at 14:07
• An LP problem with ~10 billion variables is enormous. Is this really what you're doing? Jul 26 at 14:10
• This is just an example to demonstrate the question. Does adding a linear variable that is equal to a scaled summation of a subset of integer/binary variables help with coefficient scaling as commonly implemented by a solver. Jul 26 at 16:47