added 8 characters in body
Source Link
Wolfgang Bangerth
  • 49.5k
  • 49
  • 103

Why not multiply the data (i.e., the matrix $A$ and vector $b$ in the constraint $Ax \ge b$ and the vector $c$ in the objective function $c^Tx$) by the greatest common denominator of all entries? If you do so, you end up with a problem that has only integer constraints. Of course, you could do that for each individual constraint separately if you want to use smaller multipliers.

If all you want to do is estimate the bit size you need, then the bits you need to represent a fraction $\alpha/\beta$ in a matrix or vector entry is simply $bits(\alpha/\beta)=bits(\alpha)+bits(\beta^*)$ where $\beta^*\ge \beta$ is the largestsmallest common multiplier, and this yields the same complexity bound for the linear program if you adjust the bit count for rational numbers. Of course, this yields the very same bound as you get if you just scale the entire problem by the largest common denominator $\beta^*$.

Why not multiply the data (i.e., the matrix $A$ and vector $b$ in the constraint $Ax \ge b$ and the vector $c$ in the objective function $c^Tx$) by the greatest common denominator of all entries? If you do so, you end up with a problem that has only integer constraints. Of course, you could do that for each individual constraint separately if you want to use smaller multipliers.

If all you want to do is estimate the bit size you need, then the bits you need to represent a fraction $\alpha/\beta$ in a matrix or vector entry is simply $bits(\alpha/\beta)=bits(\alpha)+bits(\beta^*)$ where $\beta^*\ge \beta$ is the largest multiplier, and this yields the same complexity bound for the linear program if you adjust the bit count for rational numbers. Of course, this yields the very same bound as you get if you just scale the entire problem by the largest common denominator $\beta^*$.

Why not multiply the data (i.e., the matrix $A$ and vector $b$ in the constraint $Ax \ge b$ and the vector $c$ in the objective function $c^Tx$) by the greatest common denominator of all entries? If you do so, you end up with a problem that has only integer constraints. Of course, you could do that for each individual constraint separately if you want to use smaller multipliers.

If all you want to do is estimate the bit size you need, then the bits you need to represent a fraction $\alpha/\beta$ in a matrix or vector entry is simply $bits(\alpha/\beta)=bits(\alpha)+bits(\beta^*)$ where $\beta^*\ge \beta$ is the smallest common multiplier, and this yields the same complexity bound for the linear program if you adjust the bit count for rational numbers. Of course, this yields the very same bound as you get if you just scale the entire problem by the largest common denominator $\beta^*$.

Source Link
Wolfgang Bangerth
  • 49.5k
  • 49
  • 103

Why not multiply the data (i.e., the matrix $A$ and vector $b$ in the constraint $Ax \ge b$ and the vector $c$ in the objective function $c^Tx$) by the greatest common denominator of all entries? If you do so, you end up with a problem that has only integer constraints. Of course, you could do that for each individual constraint separately if you want to use smaller multipliers.

If all you want to do is estimate the bit size you need, then the bits you need to represent a fraction $\alpha/\beta$ in a matrix or vector entry is simply $bits(\alpha/\beta)=bits(\alpha)+bits(\beta^*)$ where $\beta^*\ge \beta$ is the largest multiplier, and this yields the same complexity bound for the linear program if you adjust the bit count for rational numbers. Of course, this yields the very same bound as you get if you just scale the entire problem by the largest common denominator $\beta^*$.