An improved test set approach to nonlinear integer problems with applications to engineering design

作     者：Gago-Vargas, J. Hartillo, I. Puerto, J. Ucha, J. M. 

作者机构：Univ Seville Dept Algebra E-41080 Seville Spain Univ Seville Dept Matemat Aplicada 1 ETS Ingn Informat E-41012 Seville Spain Univ Seville Fac Matemat Dept Estadist & Invest Operat E-41012 Seville Spain 

出 版 物：《COMPUTATIONAL OPTIMIZATION AND APPLICATIONS》 (计算优化及其应用)

年 卷 期：2015年第62卷第2期

页      面：565-588页

核心收录：

学科分类：1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070104[理学-应用数学] 0701[理学-数学] 

基　　金：Junta de Andalucia [FQM-5849] Ministerio de Ciencia e Innovacion [MTM2010-19336, MTM2010-19576, MTM2013-46962-C2-1-P] FEDER 

主　　题：Non-linear integer programming Test set Grobner basis Chance constrained programming 

摘      要：Many problems in engineering design involve the use of nonlinearities and some integer variables. Methods based on test sets have been proposed to solve some particular problems with integer variables, but they have not been frequently applied because of computation costs. The walk-back procedure based on a test set gives an exact method to obtain an optimal point of an integer programming problem with linear and nonlinear constraints, but the calculation of this test set and the identification of an optimal solution using the test set directions are usually computationally intensive. In problems for which obtaining the test set is reasonably fast, we show how the effectiveness can still be substantially improved. This methodology is presented in its full generality and illustrated on two specific problems: (1) minimizing cost in the problem of scheduling jobs on parallel machines given restrictions on demands and capacity, and (2) minimizing cost in the series parallel redundancy allocation problem, given a target reliability. Our computational results are promising and suggest the applicability of this approach to deal with other problems with similar characteristics or to combine it with mainstream solvers to certify optimality.