# Is using gradient descent for MIP a good idea?

I'm researching ways of solving constrained optimization problems on a cloud platform. I stumbled across this:

Where they claim that gradient descent (and potentially even Tensorflow) can be used to solve MIP.

Is that a good idea?

My understanding is that even though MIP is NP-Hard, it has enough structure that you are better off using Branch-and-X and other linear specific solvers than search methods or heuristic methods. Is this correct?

• I would argue that in some particular cases (very few discrete variables/ very limited discrete search space) you can enumerate all possible discrete combinations and then compute the remaining non-fixed continuous variables (potentially with additional parallelizing of this step). Note that this approach will reach its limits in terms of applicability very fast with a growing number of discrete variables/decisions. The authors them-self write "the size may quickly grow beyond what is feasible, even with the scalability offered by Dataflow". Sep 13 '19 at 10:28

I think that this article is not about using gradient descent to solve MIP problems. It seems to me that they are explicitly enumerating all possible value combinations for the discrete decisions and then apply gradient descent to all of the continuous subproblems where the discrete decisions are fixed the candidate values.

• They even state in the article that "The exhaustive search over the discrete solution grid we discussed in this example has its limits: the size may quickly grow beyond what is feasible, even with the scalability offered by Dataflow" Sep 13 '19 at 10:24

If you're solving a very odd and trivial LP without any constraints, then gradient descent would be directly applicable (N.B. but still useless, because such a problem would be unbounded). As soon as constraints enter the picture, you have to extend gradient descent to "respect" these constraints. There are various ways of doing this, but these extensions are no longer called "Gradient Descent". For example, you can express the constraints as penalties (Lagrange multipliers) or project the point back into the feasible set. Both approaches would only be able to solve LPs, not (M)ILPs however.