In addition to what's already been said, I suggest that you look at some of the work done by Ismael de Farias on solving optimization problems without introducing auxiliary binary variables (which typically happens when big-M constraints are used). The main idea is to omit the big-M constraints and enforce them during branching (specialized cutting planes can and should be used as well). Computational experience shows significant improvements for certain problem classes.

There's a nice paper on using Benders decomposition for this, which I suspect reduces to essentially the same solution Tallys mentioned. You end up adding Benders cuts during the branching process. The citation is:

Codato, G. & Fischetti, M. Combinatorial Benders' Cuts for Mixed-Integer Linear Programming Operations Research, 2006, 54, 756-766.

Hi Mathieu,

The standard approach is reformulate your problem in disjunctive form, and then take the convex hull of the disjunction. You can Google for "convex hull reformulation". You get a better relaxation, but at the cost of usually introducing extra variables and constraints in your model.

I'm trying to think of the best references to give you. There are some nice examples in John Hooker's book "Logic-Based Methods for Optimization." You can also take a look at the papers of my advisor, Ignacio Grossmann, especially those with Nicolas Sawaya, which talk about Generalized Disjunctive Programming.

Hopefully this will get you pointed in the right direction.

Schmidt (above) described it very well. Big M method is not used in practice that much. I also suggest you take a look at Michael Ferris's works. He uses complementarity constraints instead of the big M method to model a cable in a mechanical system. And almost all of the major mathematical programming languages support that already.