Chemical equation balancing: An integer programming approach | Hacker News Reader

Chemical equation balancing: An integer programming approach

sciencedirect.com

82 pointstheideasmith29 comments

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.

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...

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

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

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.

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.

>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.

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.

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.

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."

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

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.

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

Ugh, this makes me so angry and resentful ...

School's first objective is to make you obey.

Looks isomorphic to what you can do with matrices (including some heuristics to what rows to go for first). Of course, that doesn't make it better.

by placing backdoors in his technique.

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.

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

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

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.

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

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

Ehh...

1 - Yes

2 - Good luck with that

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

Is chemical equation balancing NP-complete? hehe

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. "

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.

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

Not yet.

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.

Reply on news.ycombinator.com