Rounding-based heuristics for nonconvex MINLPs
We propose two primal heuristics for nonconvex mixed-integer nonlinear programs. Both are based on the idea of rounding the solution of a continuous nonlinear program subject to linear constraints. Each rounding step is accomplished through the solution of a mixed-integer linear program. Our heurist...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Springer Berlin Heidelberg
2016
|
| Online Access: | http://hdl.handle.net/1721.1/105215 |
| _version_ | 1826197115564457984 |
|---|---|
| author | Nannicini, Giacomo Belotti, Pietro |
| author2 | Sloan School of Management |
| author_facet | Sloan School of Management Nannicini, Giacomo Belotti, Pietro |
| author_sort | Nannicini, Giacomo |
| collection | MIT |
| description | We propose two primal heuristics for nonconvex mixed-integer nonlinear programs. Both are based on the idea of rounding the solution of a continuous nonlinear program subject to linear constraints. Each rounding step is accomplished through the solution of a mixed-integer linear program. Our heuristics use the same algorithmic scheme, but they differ in the choice of the point to be rounded (which is feasible for nonlinear constraints but possibly fractional) and in the linear constraints. We propose a feasibility heuristic, that aims at finding an initial feasible solution, and an improvement heuristic, whose purpose is to search for an improved solution within the neighborhood of a given point. The neighborhood is defined through local branching cuts or box constraints. Computational results show the effectiveness in practice of these simple ideas, implemented within an open-source solver for nonconvex mixed-integer nonlinear programs. |
| first_indexed | 2024-09-23T10:42:44Z |
| format | Article |
| id | mit-1721.1/105215 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T10:42:44Z |
| publishDate | 2016 |
| publisher | Springer Berlin Heidelberg |
| record_format | dspace |
| spelling | mit-1721.1/1052152022-09-27T14:27:19Z Rounding-based heuristics for nonconvex MINLPs Nannicini, Giacomo Belotti, Pietro Sloan School of Management Nannicini, Giacomo We propose two primal heuristics for nonconvex mixed-integer nonlinear programs. Both are based on the idea of rounding the solution of a continuous nonlinear program subject to linear constraints. Each rounding step is accomplished through the solution of a mixed-integer linear program. Our heuristics use the same algorithmic scheme, but they differ in the choice of the point to be rounded (which is feasible for nonlinear constraints but possibly fractional) and in the linear constraints. We propose a feasibility heuristic, that aims at finding an initial feasible solution, and an improvement heuristic, whose purpose is to search for an improved solution within the neighborhood of a given point. The neighborhood is defined through local branching cuts or box constraints. Computational results show the effectiveness in practice of these simple ideas, implemented within an open-source solver for nonconvex mixed-integer nonlinear programs. 2016-11-04T20:33:54Z 2016-11-04T20:33:54Z 2011-09 2010-08 2016-08-18T15:37:07Z Article http://purl.org/eprint/type/JournalArticle 1867-2949 1867-2957 http://hdl.handle.net/1721.1/105215 Nannicini, Giacomo, and Pietro Belotti. “Rounding-Based Heuristics for Nonconvex MINLPs.” Mathematical Programming Computation 4.1 (2012): 1–31. en http://dx.doi.org/10.1007/s12532-011-0032-x Mathematical Programming Computation Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. Springer and Mathematical Optimization Society application/pdf Springer Berlin Heidelberg Springer Berlin Heidelberg |
| spellingShingle | Nannicini, Giacomo Belotti, Pietro Rounding-based heuristics for nonconvex MINLPs |
| title | Rounding-based heuristics for nonconvex MINLPs |
| title_full | Rounding-based heuristics for nonconvex MINLPs |
| title_fullStr | Rounding-based heuristics for nonconvex MINLPs |
| title_full_unstemmed | Rounding-based heuristics for nonconvex MINLPs |
| title_short | Rounding-based heuristics for nonconvex MINLPs |
| title_sort | rounding based heuristics for nonconvex minlps |
| url | http://hdl.handle.net/1721.1/105215 |
| work_keys_str_mv | AT nannicinigiacomo roundingbasedheuristicsfornonconvexminlps AT belottipietro roundingbasedheuristicsfornonconvexminlps |