Solve chemical formula (number of molecules in reaction)

Question

In order to balance atom count in chemical equation:

 a O2 + b C12H24O11 → c CO2 + d H2O

I make linear equation:

O: 2*a + 11*b = 2*c + d
C: 12*b = c
H: 24*b = 2*d

and I must find smallest positive non-zero integer that satisfy that question.

In GNU Octave I bit this problem with human interaction:

[2,11,-2,-1; 0,12,-1,0; 0,24,0,-2; 0,1,0,0]\[0;0;0;1]
ans =
12.5000
 1.0000
12.0000
12.0000

[2,11,-2,-1; 0,12,-1,0; 0,24,0,-2; 0,1,0,0]\[0;0;0;2]
ans =
25
 2
24
24

by searching across b coefficient until find first integer solution.

Is there any math package that find solution automatically?

Answer 1

Generally, the algorithm that would be used would be solving a system of equations of the form you show in your question, and then multiplying by the smallest integer that yields integral coefficients for each species. This algorithm would not be carried out via mixed-integer programming, since mixed-integer programming would use inefficient algorithms to solve this sort of problem.

Answer 2

As far as I know, the only additional pieces you need are functions to convert to a rational approximation and find the least common multiple. Octave (and Matlab) have rat and lcm:

x1 = A\[0;0;0;1];
[n,d] = rat(x1);
x = x1*lcm(d(1),lcm(d(2),lcm(d(3),d(4))))

Matlab's lcm at least can't handle sets, so you'll need to customize this to other dimensions.

It's possible that error will be introduced in solving some systems – especially for larger ones. In which case the rational approximation will return a wacky value. You can set a tolerance as a second argument to rat. Another way around this is to solve the system symbolically and use numden:

x1 = sym(A)\sym([0;0;0;1]);
[n,d] = numden(x1);
d = double(d);
...

I should also mention that it's not necessary to create an augmented A matrix by adding a fourth row when using either of these methods.