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:
- change your formulation
- 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
Change your formulation
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).
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.
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.