Chemical equation balancing: An integer programming approach

http://www.sciencedirect.com/science/article/pii/S0895717706000367

by theideasmith • 10 years ago

82 29 10 years ago

Amusingly, I discovered a method very similar to this in college. My method was simpler - stick a 1 in front of one chemical, then you get an n x n linear system of equations for the remaining compounds. Solve it, then figure out what to multiply by to get an int solution. I suspect that my version isn't stable, which I gather is the problem these guys are solving.

I was forbidden from using this method on the final, since it isn't the ad-hoc method that was taught.

eru2• 10 years ago

How are you supposed to solve it, and how would they know?

wrong_variable• 10 years ago

by placing backdoors in his technique.

yummyfajitas2• 10 years ago

Roughly speaking, this method: http://www.wikihow.com/Balance-Chemical-Equations

Showing work is required, and if work contains a matrix then they'd just mark it as zero.

nsajko2• 10 years ago

Did you ask if it would be alright to use your unusual method and only then had this method disallowed, or did somebody forbid you from using it after eg. seeing you use it for homework?

I wonder if they did it purely to reduce the workload of the TAs which will be grading the finals, or did somebody think it would be wrong to have an unorthodox path to the result.

irixusr2• 10 years ago

I was a TA and grading "independent" solutions is a pain.

But that's their job. And it's the university's to hire enough TAs to do a good, through, job

insaneirish• 10 years ago

This reminds of my first chemistry class in high school. Everything in the beginning seemed so trivial that I tended to not pay attention at all. I had my own methods for various things (including stoichiometry like you).

Then the first test came. I seemingly had no problem with it. A few days later, the tests were returned. Everyone got theirs back except for me. I was summoned to the front of the room and the teacher asked me to explain how I did things. We went over the first problem, she understood my explanation. The second, same thing. I was continuing my explanations and she cut me off--"Forget it; I trust you." She flipped the paper over and wrote 100 on it and gave it to me.

Boy did that make me never want to do any work in that class again. Apparently I and the eventual valedictorian of our class were real pains in the asses to her. We were "punished" by being given a box of magazines (Scientific American, etc.) and told to sit in the back of the room and not talk.

I apologize, Ms. M., for being nuissance, but I think this was a fair treatment rather than being scolded for having my own ways of doing things.

kwhitefoot• 10 years ago

Anecdotal evidence suggests to me that this is actually all too common. When I describe my primary and secondary schools (1970-1974, Park Senior High, etc., Swindon) where challenging teachers with difficult questions and alternative methods simply prompted the teachers to either gently shoot down your naive idea or return the challenge with something a bit more difficult I am often told "That's how it worked at your school, the rest of us didn't have it so good."

jamessb• 10 years ago

A while ago I saw a paper in the SIAM Review - just one and a half pages of maths, followed by

"Remark 2. The theorem proved here gives a completely new general method. It generalizes all known results for balancing chemical equations cited chronologically in references [1]–[125]." http://www.siam.org/journals/problems/downloadfiles/71-025s....

Reference 125 is to this paper.

_delirium• 10 years ago

It's interesting that despite being long open, both the problem and the solution are stated using only elementary linear algebra.

GFK_of_xmaspast2• 10 years ago

In fairness, this paper is looking for integer solutions instead of SiRev's real ones.

octonion2• 10 years ago

This appears to be essentially equivalent to solving a linear system using the Moore-Penrose pseudoinverse. https://en.m.wikipedia.org/wiki/Moore%E2%80%93Penrose_pseudo...

markc2• 10 years ago

My high-school chemistry teacher had a tradition of announcing "Automatic A" challenges at the start of the term. One challenge was balancing a large chemical equation. I recall it required solving something like 6 equations with 6 unknowns. I solved it with multiple attempts and many pages of algebra, and crucial hints at sticking points from my dad who had a Masters in Chemistry. Easy A.

Another term, an A was promised for anyone turning in a "print out" of the numbers from 1 to 1 million. Dad, coming to the rescue again, got me access to a Microfilm printer at his work, and taught me just enough FORTRAN to generate the list. (Yeah, short program, all about the formatting.) Another easy A. The teacher's expression was priceless.

kaik2• 10 years ago

Did you enjoy working on those things?

The way you write it it seems like you think that it was stupid for a professor to give you an A for such easy things. However I bet you learned a lot.

markc2• 10 years ago

seems like you think that it was stupid

Because I mentioned the expression on his face? I didn't intend to convey that I was laughing at him for that - only that he was (understandably) surprised, and I enjoyed that.

I don't think it was stupid. The chemical equation balancing was highly relevant, and I did learn a lot from that. In some sense it was like "testing out" of the class - by mastering a homework challenge that was much harder than any of the class material.

The "million" challenge was interesting as well, and I did learn from it, but not about Chemistry. I knew I had the A less than halfway into the term, so I stopped doing chem homework. That was not optimal if the goal was to teach me Chemistry. In that sense, the first challenge was probably better.

vondur• 10 years ago

I'd always assumed that stoichiometry problems could be solved with linear algebra, but was too lazy to investigate. Usually the problems assigned were easy enough that you didn't have to work too hard to figure them out.

amelius• 10 years ago

Does this mean that, conversely, we can solve integer programming problems by doing chemical experiments?

marcosdumay• 10 years ago

Ehh...

1 - Yes

2 - Good luck with that

3 - Take a look on DNA computing (wikipedia et all)

kaik2• 10 years ago

Is chemical equation balancing NP-complete? hehe

GFK_of_xmaspast2• 10 years ago

Did you perhaps miss the third sentence of the abstract: "This special algorithm is polynomial time O(n3), unlike the ILP approach, and uses the widely available conventional floating-point arithmetic, obviating the need for both rational arithmetic and multiple modulus residue arithmetic. "

theideasmith2• 10 years ago

My face lit up when I found this paper after beginning balancing chemical equations in my 10th grade chemistry class this morning - so I thought I share it with HN.

elcritch• 10 years ago

That's awesome. Bonus points, did you implement it on a TI?

theideasmith2• 10 years ago

Not yet.

openasocket• 10 years ago

I might be missing something big, but isn't chemical equation balancing just a system of linear Diophantine equations[1]? If it is, you should be able to solve it in O(n^3) time by converting to Smith normal form[2]. Unlike Hermite form, which the paper mentions, you don't need rational arithmetic or floating points.

[1]https://en.wikipedia.org/wiki/Diophantine_equation#System_of... [2]https://en.wikipedia.org/wiki/Smith_normal_form

sgeisenh• 10 years ago

Yeah, I remember using gaussian elimination to solve them in high school chemistry. My teacher taught us some guess and check method when it was clearly just a system of linear equations. He gave us a "challenge" problem with more variables than normal; much to his chagrin, I popped it into my TI-89 and had a solution within a few minutes.

octonion2• 10 years ago

Not quite, because for equation balancing non-negative integers are required.

Chemical equation balancing: An integer programming approach

Related Stories