What is the complexity of intlinprog

I have used intlinprog in my algorithm and interested in finding the complexity of developed algorithm. what is the complexity of intlinprog and which method is used by intlinprog for solving mixed integer linear programming problem.

[Prerna]

What is the complexity of solving integer linear programming problem using intlinprog in terms of number of constaints and number of variables and complexity of solving mixed integer linear programming problem using intlinprog in terms of number of constaints and number of variables

[Steven Lord]

How are you hoping to use this information? Suppose you were told (making up something completely arbitrarily) that it was O(n^pi). What effect would that have on what you're trying to do?

What exactly do you consider to be one operation? If I evaluate y = a*x+b, is that one operation or two?

Do you consider memory access in your analysis of the program?

See the last couple paragraphs of this document.

Answer 1

[John D'Errico]

This is a question with seemingly no answer as posed. Why not? Because intlinprog will use many different methods, depending on the problem. So knowing what method is used is impossible, and then even a guess at the complexity is also impossible.

For example, if your problem is purely a linear programming problem, then there are TWO different methods that can be employed, at the user's direction, thus a dual or a primal simplex method.

But you can also call intlinprog in a way that would just solve a linear system of equations. That would involve nothing more than an LU factorization.

On the integer side of things, there would appear to be 11 possible heuristics possible for finding a feasible solution.

In terms of the main algorithms employed for the main MILP code, you might want to read the doc pages under

"Mixed-Integer Linear Programming (MILP) Algorithms"

to get some information about the algorithms emplyed. Those pages go into a fair amount of depth on the algorithms employed, far more than we can write here. Again though, it depends on the specific problem, and the options chosen by the user.

Complexity questions are asked here over and over again. Complexity is something that gets pushed hard in schools, where we are convinced that every algorithm has some intrinsic complexity. The problem is, that fails completely when you get into the real computing world, where you will find algorithms that are an amalgam of many different sub-algorithms. (As is the case with INTLINPROG.) It fails even when faced with the idea that many computations MAY be automatically farmed out to multiple cores on modern computers, but the choice of when to do so is left up to other codes, like the BLAS, or by your CPU itself. (Are there other operations running on your CPU in the background? There always are on any modern computer. And that will influence what happens.) At best, you can see how that code performs on different size problems of the class you want to solve. Even then, you will find many strange things happen, due to interactions between the various levels of cache on your computer, between the cores on your CPU, the speed of your RAM, your disk drive, etc. I can give an example where even for something as a matrix multiply, the question of complexity is not as easy to answer as you would think.