12
$\begingroup$

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

https://cloud.google.com/blog/products/data-analytics/distributed-optimization-with-cloud-dataflow

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?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ 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". $\endgroup$
    – JakobS
    Commented Sep 13, 2019 at 10:28

3 Answers 3

Reset to default
10
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ 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" $\endgroup$
    – JakobS
    Commented Sep 13, 2019 at 10:24
6
$\begingroup$

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.

To answer your questions:

  • GD in general is probably not a good idea for (MI)LP, but it might be interesting for very special problems.
  • Again, this depends on the problem - but I'd lean towards agreeing.
Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ I would also describe the simplex method as a way of modifying gradient descent to deal with constraints. $\endgroup$
    – Misha Lavrov
    Commented Sep 13, 2019 at 14:51
3
$\begingroup$

In general, no, as Gradient Descent (G)D is designed primarily for unconstrained continuous problems. However, you might get somewhere if you formulate your problem such that the constraints and integrality conditions are penalized in the objective and apply GD on that.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.