2
$\begingroup$

With the advent of "big data" applications, different algorithms have to be used to efficiently solve optimization problems, even in the convex case (e.g. the recent success of stochastic gradient descent).

Now I was wondering what happens in cases where you have hard MILP instances with millions ($10^6$-$10^9$) of variables and a similar number of integer constraints (say $10^5$-$10^8$). Also assume that these problems have to be solved really quickly, in a few seconds or less, but a very good approximative answer suffices. In such cases, a standard branch-and-bound algorithm is bound to fail (setting a time limit on standard MILP solvers will usually produce a bad solution or no solution at all).

Are there any resources for dealing with such kind of problems (in the MILP context)? I am looking both for textbooks or for journal articles which describe methods to tackle such problems and especially cases where the large scale of the problem actually increases the power of these methods.

Examples of articles I am looking for, are the following ones by Robin Vujanic:

Vujanic, Robin, et al. "Large scale mixed-integer optimization: A solution method with supply chain applications." Control and Automation (MED), 2014 22nd Mediterranean Conference of. IEEE, 2014.

Vujanic, Robin, et al. "Vanishing duality gap in large scale mixed-integer optimization: a solution method with power system applications." submitted to Journal of Mathematical Programming (2014).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.