Can we use them to solve nonlinear programming problem (OPTIMIZATION)
The big-M method is not an algorithm but a formulation trick to model discrete decisions in the context of a mixed integer program (MIP). As such, it is impossible to say how fast it is relative to an actual algorithm such as the simplex algorithm. However, MIP formulations with big-M's usually do not solve quickly and problems that are purely linear (no integer variables) will solve quickly.
As a side note, whenever you make a big-M formulation for a problem, M should be large enough, but no larger than that, as very big M's lead to very loose linear programming relaxations.
Hi, I agree with Joachim. In addition these methods are specific to linear problem and cannot be applied to nonlinear programming problems. For these last ones you can use SQP methods.
Dear friends
Thanks for answering my problem. I agree ur answers. I believe that you will reply for my problem in future.
Dear Joachim Arts,
you were misled by the question: the big-M method here refers to a variant for the startup of the simplex method for LPs.
Two-pase approach: solve first the auxiliary problem in the first phase, then - if its objective reached zero - continuing in the second phase with a feasible point for the original problem.
Big-M-method: add the auxiliary variables and solve the problem using as an objective the original one plus M times the sum of the auxiliary variables.
If M was chose big enough (but of course not too big for numerical stability) the method ends with infeasibility (auxiliary variables not all zero) or an optimal point of the original problem -- if M was big enough.
Viewing this as a parametric LP with parameter M in the objective the method could be contiued increasing M if the local stablility interval has an upper bound.
I agree with Joachim. BigM is a technique. Two phase method gives crisp solutions.
Hi Punita,
I have to correct you: there are two different uses for the notion BigM, please read
https://en.wikipedia.org/wiki/Big_M_method
Dear Ralf sir
Thanks to solve my problem. U point out all parts of my problem. I am very happy to read my problem . I was waiting ur answer. I believe that you will solve my problem in near future.
With regards to u
Theoretically, there is a (maybe huge) value of M, s.t. the big-M-method will end up with the optimal solution - but that value is problem dependent and a really big M might lead to numerical problems on a computer. This is an important drawback of the big-M-method. The method could be combined with one-parametric optimization wrt. increasing values of M, but I am not aware of existing implementations.
The number of Simplex steps necessary for both methods strongly depends on the geometry of the actual feasible domain, so there will not be a general rule which one (with reasonable values of M) would be faster.
The dual Simplex is faster in a number of cases than the two-phase primal Simplex. And the Barrier method is faster than both for a number of cases. That's why e.g. CPLEX when applied to MIPs starts the three methods in parallel on modern multi-core CPUs and stops the calculations as soon as one of the methods gave a result. With this approach there is no necessity to know which one will be fastest for the problem at hand.
Though Joachim Arts is right that there is a Big-M formulation in MIPs to express e.g. alternative inequalities, his is not the one mentioned in the question.
In the contex of linear programming this means the combination
original objective + M*artificial objective
While in the two-phase start in phase 1 is used solely the artificial objective to fid a feasible basic solution or to prove infeasibility, and only afterwards the original objective is used to find an optimum or to detect unboundedness, both tasks are combined into one step - provided the factor M is chosen big enough.
One-Parametric linear optimization could be applied if M is not big enough to reach the goal.
If M is chosen too big it endangers numerical stability of the simplex method.
- Badges
- Science topic
- Similar topics
- Names