linear-programming

How to use interior point method to get an extreme point with optimal objective value in large scale linear programming?

I need to solve a linear programming with few constraints but many variables:

LP with many columns

A is mxn. m is about 15, but n is more than 1 million. I used Matlab linprog with different algorithm(dual-simplex, interior-point, interior-point-legacy).Below are the time they spent.

  1. Dual-simplex method takes almost a day.

  2. Interior-point method takes more than a day.

  3. Interior-point-legacy only takes within 5 miniutes.

As I know, interior point method is faster than simplex method in large scale linear programming. But the results 1 and 2 above are unexpected.

Discuss only dual-simplex method (1) and interior-point-legacy method (3). They get different answers. (1) gets an answer which has only 12 nonzero terms while (3) gets an answer with all terms nonzero. Two answers have the same objective value.

The answer of (1) is what I want (Only a few nonzero terms), but (1) is time-comsuming. The answer of (3) is an interior point, so all terms are nonzero. But almost 99% of the terms are very small (smaller than 0.001). That is not what I want. But (3) is fast.

What I want is to let the answer of (3) goes to the extreme point. (Let the number of nonzero terms is at most the number of constraints.) I use some key words like 'large scale', 'interior point method', 'linear programming' to search on the Internet, but I have not found what I want yet. Is there any direction or suggestion?

Sorry, one thing I forgot to mention. My coefficients in A and b are all positive. And the coefficients in c are all "-1".

Solution

  • In your case, the Sifting method is probably best suited:

    Sifting iteratively solves subproblems containing only some of the variables and checks for optimality of the remaining ones. This can work because as you already suggested most of the variables in a basic solution would be zero.

    Most commercial solvers like CPLEX, or Gurobi would use this method automatically for your problem.