Applications of neural network energy functions in solving integer programming models | |
| Author | Komgrit Leksakul |
| Call Number | AIT Diss. no.ISE-05-03 |
| Subject(s) | Neural networks (Computer science) Integer programming |
| Note | A dissertation submitted in partial fulfillment of the requirements for the degree of Doctor of Engineering, School of Advanced Technologies |
| Publisher | Asian Institute of Technology |
| Series Statement | Dissertation ; no. ISE-05-03 |
| Abstract | In this research, we propose to solve integer programs (IPs) by the applications of neural network energy functions. Firstly, we address the single-machine sequencing problem that minimizes either single- or multi-objectives, specifically total tardiness, total flowtime, maximimum tardiness, maximum flowtime, and number of tardy jobs. We formulate correspondingly nonlinear integer models, for each of which a quadratic energy function, a neural network, and a system of differential equations are derived. Simulation results based on solving the nonlinear differential equations demonstrate that this approach can effectively solve the sequencing problems to optimality in most cases and near optimality in a few cases. The algorithm is also implemented on a parallel computing network, resulting in significant runtime savings over the optimization approach. Secondly, we address a general binary integer program whose integrality constraints are reformulated into either nonlinear sine or sine square function. Subsequently, the energy function incorporated with weighted quadratic penalty terms are proposed and solved by the Runge-Kutta steepest-descent method of order 4. To further improve the quality of solution, we apply, in the solution procedure, the subgradient optimization method using different step functions to iteratively update values of penalty weights in the energy function. The proposed method with different step size functions are implemented and evaluated on standard multidimensional knapsack problems. The computational results show that among six evaluated models, the energy function model using the sine integrality function and Held et al. (1974)'s step size rule in the solution algorithm consistently yields the best results at significantly lower computational efforts, although with the maximum gap of 0.143% from optimality. Finally, we extend the integrality constraints of sine or sine square functions and their corresponding energy functions in solving general integer programs. Besides the original sine and sine square functions, the subgradient optimization method using Held et al. (1974) step functions which has provided the best solution previously is initially applied in solving the general integer programming problems. The experimental results show that the search algorithm generally converges to some local minimum, which is of inferior quality when compared with the desired global minimum. Subsequently, we apply the stochastic gradient optimization by introducing random fluctuations or noise into the search system in order to avoid being trapped at a local minimum. To evaluate and compare the effectiveness and efficiency of the algorithms, several combined solution methods are implemented and tested on standard literature integer linear programming problems. Their experimental results show that despite a longer runtime than other deterministic models considered, the stochastic Langevin neural network energy function using the sine integrality function, combined with the subgradient optimization approach to adjust penalty weights using Held et al. (1974)'s step size rule is the most effective heuristic approach, when compared with other evaluated techniques including the optimization method. It can achieve in many small cases 0% gap to optimality and in large cases better solutions than those obtained from LINGO, an optimization package. |
| Year | 2005 |
| Corresponding Series Added Entry | Asian Institute of Technology. Dissertation ; no. ISE-05-03 |
| Type | Dissertation |
| School | School of Advanced Technologies (SAT) |
| Department | Department of Industrial Systems Engineering (DISE) |
| Academic Program/FoS | Industrial Systems Engineering (ISE) |
| Chairperson(s) | Anulark Techanitisawad; |
| Examination Committee(s) | Huynh Ngoc Phien;Manukid Parnichkun;Haddawy, Peter;Mayr, Ernst Wilhelm; |
| Scholarship Donor(s) | Royal Thai Government; |
| Degree | Thesis (Ph.D.) - Asian Institute of Technology, 2005 |