3
$\begingroup$

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?

Improve this question
$\endgroup$
5
  • $\begingroup$ How high do $i$ and $j$ go? This is critical to a scaling solution. $\endgroup$
    – Reinderien
    Jul 26 at 0:22
  • $\begingroup$ In this particular case i = 10^7 and j = 10^3, but I am interested in understanding for other ranges as well. $\endgroup$
    – gomory-chvatal
    Jul 26 at 13:33
  • $\begingroup$ I assume you mean $i \le 10^7$ and $j \le 10^3$ $\endgroup$
    – Reinderien
    Jul 26 at 14:07
  • $\begingroup$ An LP problem with ~10 billion variables is enormous. Is this really what you're doing? $\endgroup$
    – Reinderien
    Jul 26 at 14:10
  • $\begingroup$ 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. $\endgroup$
    – gomory-chvatal
    Jul 26 at 16:47

2 Answers 2

Reset to default
1
$\begingroup$

In my opinion, these two formulations are exactly the same. However, coefficience scalling would lead the float number coefficience in the first constraints, and then that would not be the benefit for your solver to solve the problem. The reason is numerical issue can be lead other issues for simplex method such as: select entering/leaving variables, that might make cyclic or degenerate issues happened.

So, in my past experience, I would try to deal with integral coefficience in the MIP model to reduce the burden for the solver.

Improve this answer
$\endgroup$
-2
$\begingroup$

Scaling will directly impact the Objective function of an optimization problem. say we have

Max obj1 = c1x1 + c2x2

Now if your c1 = [0-10] & c2 = [200-1000], x2 variable will dictate much of the objective function. But, you are talking about Constraints. For Constraints, aren't we just check if this constraint is satisfied or not (in such case, scaling seems not a matter). May I missing something?

Improve this answer
$\endgroup$
1
  • $\begingroup$ From a purely mathematical standpoint the coefficient ranges on constraints don't matter, however, when implemented in practice using floating point numbers it does CPLEX docs and gurobi docs. Knowing this I can scale coefficients to be within recommended ranges, but I am concerned that my approach for scaling is just masking the problem. $\endgroup$
    – gomory-chvatal
    Aug 2 at 13:04

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.