Tightening concise linear reformulations of 0-1 cubic programs
| Autor: | Richard J. Forrester |
|---|---|
| Rok vydání: | 2015 |
| Předmět: |
Scheme (programming language)
050210 logistics & transportation Mathematical optimization 021103 operations research Control and Optimization Linear programming Applied Mathematics 05 social sciences 0211 other engineering and technologies 02 engineering and technology Management Science and Operations Research Solver Quadratic equation Linearization Knapsack problem Linear form 0502 economics and business Relaxation (approximation) computer Mathematics computer.programming_language |
| Zdroj: | Optimization. 65:877-903 |
| ISSN: | 1029-4945 0233-1934 |
| DOI: | 10.1080/02331934.2015.1091821 |
| Popis: | A common strategy for solving 0-1 cubic programs is to reformulate the non-linear problem into an equivalent linear representation, which can then be submitted directly to a standard mixed-integer programming solver. Both the size and the strength of the continuous relaxation of the reformulation determine the success of this method. One of the most compact linear representations of 0-1 cubic programs is based on a repeated application of the linearization technique for 0-1 quadratic programs introduced by Glover. In this paper, we develop a pre-processing step that serves to strengthen the linear programming bound provided by this concise linear form of a 0-1 cubic program. The proposed scheme involves using optimal dual multipliers of a partial level-2 RLT formulation to rewrite the objective function of the cubic program before applying the linearization. We perform extensive computational tests on the 0-1 cubic multidimensional knapsack problem to show the advantage of our approach. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|