Modifying MINOS for Solving the Dual of a Linear Program

Abstract

In many situations it is advantageous to solve the dual of a linear program rather than the primal. For example, an approach to solve two stage stochastic linear programs with recourse employs Bender's decomposition (Dantzig and Glynn 1990). Within this algorithm, cuts (necessary conditions for the second stage costs) are added sequentially to the master problem. In the primal version of the master problem, cuts appear as new rows. In each iteration of Bender's decomposition algorithm, when a new row is added, the pervious solution of the master problem gets infeasible. However, when solving the dual of the master problem, a cut appears as a column. When adding a new column, the previous solution of the master problem remains feasible and the new optimal solution can be obtained within a few simplex iterations. This report describes the changes made by the author in the MINOS file MI35INPT, so MINOS could transform the given primal linear program, specified in an MPS file, to its dual, solve the dual and in addition, write another MPS file which contains the specification of the dual problem.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Aug 01, 1990
Accession Number
ADA226449

Entities

People

  • Eithan Schweitzer

Organizations

  • Stanford University

Tags

Communities of Interest

  • Energy and Power Technologies
  • Weapons Technologies

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Computer Programming
  • Decomposition
  • Evolutionary Algorithms
  • Hash Tables
  • Iterations
  • Linear Programming
  • Mathematical Programming
  • Military Research
  • Numbers
  • Operations Research
  • Personality
  • Precision
  • Procedures (Computers)
  • Specifications
  • Standards

Fields of Study

  • Mathematics

Readers

  • Computer Science.
  • Finite Element Method (FEM) for solving Partial Differential Equations (PDEs)
  • Graph Algorithms and Convex Optimization.