Which algorithm to use for solving an LP with a very large number of variables?

I'm a newbie at modelling and optimization of LPs. My research problem concerns assigning tasks/jobs to virtual machines in a data centre depending on the least energy cost incurred. As you can imagine this is a very large problem.

My primary question is: Which algorithm (interior point, genetic algorithm....etc) would be efficient in solving very large LPs?

I was initially using CPLEX as a solver and quickly realised that it was inefficient on very large data. So now I'm planning to solve the LP using C++. Is this wise? Are there any problems that I might encounter if using C++ to solve the LP?

• You should really provide more details. How many variables? How many constraints? How much precision do you need? Any special structure in the nonzero matrix? Jan 31, 2014 at 3:25

CPLEX is commercial grade and solves very large LPs and IPs. If CPLEX didn't pan out for you, then switching to a different solver may not be the answer. Here's one SO Question on good solvers.

Instead, here are three suggestions for you, rather than going for the solver speed or the specific algorithm.

Focus on your formulation. How many constraints and variables do you have? Are you modeling each of task/jobs to be assigned and each one of the virtual machines?

In other words, do have binary variables of the type X_ij where i is the set of jobs and j is the set of virtual machines? If you make the IP very large, then every solver out there will choke.

Formulation related suggestions

1. Groups: Try to make groups of jobs/tasks, and create groups of virtual machines. Even if it is just to get an initial feasible solution, make groups of 100 or even 1000 and that will significantly reduce your problem size. Now, the solver should be able to solve your problem.

2. Hierarchical problems: This is similar to grouping. Instead of one LP, you solve multiple ones. Make a hierarchy of machines and big groups of jobs. Once you have a solution for this higher level LP, you can then solve sub-problems at higher levels of granularity. This is a very typical approach when "good" solutions are acceptable. It would be a mistake to go for the absolute lowest electricity costs.

3. Problem Relaxations: Look into simplifying or decomposing your problem. Compare your formulation to textbook formulations of "assignment problems." It is quite possible that in your formulation, there is a nice underlying structure, but a few dense constraints are giving the solver trouble. If you can identify these constraints, you can "relax" those, and maybe even throw it into the objective function with a multiplier. One option is to consider Lagrangian relaxations for 'troublesome constraints.'

Try some of these and see if you can make progress.

The big solvers like CPLEX / GUROBI are usually quite good, especially concerning linear programs and not integer linear programs, however they have natural difficulties beyond a certain problem size.

Tackling the problem with c++ alone will probably not help, since I doubt that it is to easy to beat CPLEX implementations. CLPEX itself provides a c++ api, but it wont help you much on the inbound LP solver, it is rather for the "integer" part (though it can help a lot there if you problem is integer by custom heuristics/cutting-planes)

If your (integer) linear problem's size, informally amount of columns / rows, makes up for most of the difficulty, you can try column-generation or cutting plane algorithms, however they are not trivial to implement. I am not sure whether the current versions of GUROBI/ CPLEX support these algorithms, but another solver called SCIP (as well by its c++ api) provides opportunities to do so.

• Does CPLEX actually have a C++ API, as opposed to its C API being usable in C++? I can't find that in the documentation. Dec 19, 2016 at 23:28

A brief word on solvers

Don't roll your own code to start out. People have been working on this problem for decades, and have developed high-quality solvers. Of these, CPLEX and Gurobi are the state-of-the-art. If you decide you must roll your own code (perhaps you need certain features existing solvers don't provide, or you really want to write a solver yourself), consider contributing to a community project like the COIN-OR solvers. For people who can't use CPLEX or Gurobi (say, due to cost, or licensing restrictions), the COIN-OR solvers are a good no-cost alternative, and they're always looking for solver improvements. Much of the advice below is geared towards CPLEX and Gurobi, although a lot of it applies to the COIN-OR solvers as well, with the caveats that the COIN-OR solvers tend to be slower, have worse heuristics, and have fewer features.

Methods you could use to speed up the solution of a large-scale LP

Assuming you have a large LP with no integer variables the main strategies typically employed are:

• interior point methods
• delayed column generation (e.g., Dantzig-Wolfe decomposition)
• delayed row generation (e.g., Benders' decomposition, generalized Benders' decomposition)
• Lagrangian relaxation (as mentioned by RamNarasimhan)
• exploit parallelism

I originally put this section last, but it's probably best to put it first. If you haven't explored different methods for modeling your problem, you should, and you should follow RamNarasimhan's advice on grouping and hierarchical formulations. These methods are good exercises anyway, because they will help you understand tradeoffs you're making between mathematical modeling and time-to-solution.

Once you settle on a level of modeling detail, it's still worth structuring a large-scale formulation to take advantage of the other methods. Interior point methods are suited to large-scale, sparse problems. If your problem is large-scale and dense, it is less helpful, and your problem may still be intractable. Similarly, delayed column generation works best if you have sets of mostly uncoupled variables, coupled by a small number of constraints. Lagrangian relaxation works best if you can identify a small number of difficult constraints.

Interior point methods

CPLEX and Gurobi both have heuristics that select either an interior-point method or a simplex method based on the data supplied to its solvers. These libraries can also switch between the two via "cross-over" steps. Without any information on how large your problem is (number of variables, number of constraints) or any information on exploitable problem structure, I can only assume that CPLEX and Gurobi would use interior point methods automatically.

Delayed column/row generation

Delayed column generation and delayed row generation are both methods that are not generally implemented in CPLEX or Gurobi automatically because they require manual intervention to decompose your problem into a master problem and smaller subproblems. There are examples of how to implement them in CPLEX (and probably Gurobi) available online. The one exception I can think of is cutting plane generation for mixed-integer linear programs; in that case, CPLEX and Gurobi will both generate Gomory cuts, lift-and-project cuts, and so on, using heuristics (and if you know something about the structure of your problem, user intervention).

Lagrangian relaxation

As noted by RamNarasimhan, Lagrangian relaxation works by dualizing a subset of constraints known to be difficult to solve, so it comes up more in the context of mixed-integer and nonlinear programming than it does in linear programming. It has been used effectively to solve large-scale linear programs also.

Parallelism

If you have access to machines with many cores, or a number of machines with fast interconnects, you might be able to parallelize your problem, if it is large enough. CPLEX and Gurobi both have facilities for exploiting parallelism, although I don't know in detail what algorithms it uses. The impression I get is that there is a lot of room for improvement in parallelizing optimization algorithms, so I would suggest exhausting all other avenues before looking to speed up the solution of your problem via parallelism.