A successive relaxation algorithm to solve a MILP involving piecewise linear functions with application to road design

Dominique Monnet (), Warren Hare and Yves Lucet
Additional contact information
Dominique Monnet: Polytechnique Montréal
Warren Hare: University of British Columbia Okanagan
Yves Lucet: University of British Columbia Okanagan

Computational Optimization and Applications, 2022, vol. 81, issue 3, No 3, 767 pages

Abstract: Abstract This paper presents a new algorithm to build feasible solutions to a MILP formulation of the vertical alignment problem in road design. This MILP involves a large number of special ordered set of type 2 variables used to describe piecewise linear functions. The principle of the algorithm is to successively solve LPs adapted from the MILP by replacing the special ordered set of type 2 constraints by linear constraints. Proof that the solutions to the successive linear relaxations of the MILP converge to a feasible solution to the MILP is provided. Numerical results emphasize that the algorithm performs better than CPLEX for large scale vertical alignment problems.

Keywords: Mixed integer linear program; Piecewise linear functions; Road design; Vertical alignment proble (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10589-021-00347-7 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:coopap:v:81:y:2022:i:3:d:10.1007_s10589-021-00347-7

Ordering information: This journal article can be ordered from
http://www.springer.com/math/journal/10589

DOI: 10.1007/s10589-021-00347-7

Access Statistics for this article

Computational Optimization and Applications is currently edited by William W. Hager

More articles in Computational Optimization and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().