inicioir al DIIbuscar
relaxations and linearizations in nonlinear integer programming and application to several quadratic assignment problems
Computing tight bounds for nonlinear, especially quadratic, integer programming problems is known to be difficult. After describing an approach based on a combination of reformulation, linearization and relaxation, specifically an RLT approach used at different levels, we will present applications to several quadratic assignment problems: the standard QAP, the GQAP or generalized quadratic assignment problem, and the Q3AP, or 3 dimensional quadratic assignment problem. This last problem has recently become of interest. Indeed, algorithms for optimizing symbol mappings that minimize bit error rate in a hybrid Automatic Repeat reQuest (ARQ) scheme for enriching diversity among multiple packet transmissions in digital wireless communication systems require solving Q3AP's. We will present numerical results for these three problems.