Name
Abstract | ||
|---|---|---|
We study the structure of dual optimization problems associated with linear constraints, bounds on the variables, and separable cost. We show how the separability of the dual cost function is related to the sparsity structure of the linear equations. As a result, techniques for ordering sparse matrices based on nested dissection or graph partitioning can be used to decompose a dual optimization problem into independent subproblems that could be solved in parallel. The performance of a multilevel implementation of the Dual Active Set algorithm is compared with CPLEX Simplex and Barrier codes using Netlib linear programming test problems. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1007/s10107-006-0022-3 | Math. Program. |
Keywords | Field | DocType |
barrier code,separable cost,linear constraint,multilevel optimization · dual optimization · dual separability · dual active set algorithm · parallel algorithms,netlib linear programming test,active set,linear equation,dual optimization problem,dual multilevel optimization,cplex simplex,sparsity structure,dual cost function,linear equations,graph partitioning,sparse matrices,cost function,linear program,parallel algorithm,optimization problem | Graph theory,Linear equation,Mathematical optimization,Active set method,Algorithm,Nested dissection,Linear code,Linear programming,Graph partition,Optimization problem,Mathematics | Journal |
Volume | Issue | ISSN |
112 | 2 | 1436-4646 |
Citations | PageRank | References |
4 | 0.85 | 22 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| TIMOTHY A. DAVIS | 1 | 1447 | 144.19 |
| William W. Hager | 2 | 1603 | 214.67 |