MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Dear all,

its quite clearly stated that independence of decision variables are necessary for solving optimization problems using the simplex method.

Is this a requirement for all linear optimization techniques? And if so, what methods could be used to bypass this requirement. I have been able to solve such problems using exhaustive search and by heuristic techniques, but I would be grateful if someone could point me towards some good papers regarding optimization with interdependencies between decision variables.

Thanks in advance.


share|cite|improve this question
Stated where, exactly? – Will Jagy May 26 '11 at 19:54
Where is that stated? I don't know what you mean by "independence of decision variables". The simplex method can be used to solve linear programming problems with inequality and/or equality constraints on the decision variables. If, say, $x_1 + x_2 = 1$ is one of the constraints, do you consider $x_1$ and $x_2$ to be "independent"? – Robert Israel May 26 '11 at 19:58
To be specific, there is a simple (well, simple enough) technique for including "equality constraints" in a linear programming problem, one says that a certain linear combination of variables is greater than or equal to the desired constant, then in another line say the linear combination is less than or equal to the line. Indeed, one book I have treats the case of all equality constraints as the standard problem, then points out that an inequality can be included by adding a new slack variable, which is given no influence on the objective function. – Will Jagy May 26 '11 at 20:11

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.