Virginia Tech
    • Log in
    View Item 
    •   VTechWorks Home
    • College of Engineering (COE)
    • Grado Department of Industrial and Systems Engineering
    • Scholarly Works, Industrial and Systems Engineering
    • View Item
    •   VTechWorks Home
    • College of Engineering (COE)
    • Grado Department of Industrial and Systems Engineering
    • Scholarly Works, Industrial and Systems Engineering
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Enhancing Lagrangian dual optimization for linear programs by obviating nondifferentiability

    Thumbnail
    View/Open
    Main article (260.9Kb)
    Downloads: 346
    Date
    2007
    Author
    Sherali, Hanif D.
    Lim, C.
    Metadata
    Show full item record
    Abstract
    We consider non differentiable optimization problems that arise when solving Lagrangian duals of large-scale linear programs. Different from traditional subgradient-based approaches, we design two new methods that attempt to circumvent or obviate the nondifferentiability of the objective function, so that standard differentiable optimization techniques could be used. These methods, called the perturbation technique and the barrier-Lagrangian reformulation, are implemented as initialization procedures to provide a warm start to a theoretically convergent nondifferentiable optimization algorithm. Our computational study reveals that this two-phase strategy produces much better solutions with less computation in comparison with both the stand-alone nondifferentiable optimization procedure employed, and the popular Held-Wolfe-Crowder subgradient heuristic. Furthermore, the best version of this composite algorithm is shown to consume only about 3.19% of the CPU time required by the commercial linear programming solver CPLEX 8.1 (using the dual simplex option) to produce the same quality solutions. We also demonstrate that this initialization technique greatly facilitates quick convergence in the primal space when used as a warm start for ergodic-type primal recovery schemes.
    URI
    http://hdl.handle.net/10919/25834
    Collections
    • Scholarly Works, Industrial and Systems Engineering [207]

    If you believe that any material in VTechWorks should be removed, please see our policy and procedure for Requesting that Material be Amended or Removed. All takedown requests will be promptly acknowledged and investigated.

    Virginia Tech | University Libraries | Contact Us
     

     

    VTechWorks

    AboutPoliciesHelp

    Browse

    All of VTechWorksCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

    My Account

    Log inRegister

    Statistics

    View Usage Statistics

    If you believe that any material in VTechWorks should be removed, please see our policy and procedure for Requesting that Material be Amended or Removed. All takedown requests will be promptly acknowledged and investigated.

    Virginia Tech | University Libraries | Contact Us