Reformulasi Kuadratik Konveks Kuat dengan Metode Faktorisasi Berulang pada Program Polinomial Integer Campuran

Abstract

This paper discusses solving Mixed-integer Polynomial Programs through convex quadratic reformulation. This quadratic reformulation is carried out using the factorization method. This method works by factoring high degree monomials into two multiplicative groups of variables. Each factor is replaced with a new variable called an auxiliary variable. This method will increase the variable di- mension and add the new constraint functions such that it can weaken relaxation. This research introduces a new procedure of factorization method called the ite- rative factorization method. This procedure works to reformulate a polynomial program into a quadratic program with a non-wide range of auxiliary variables and minimizes the use of auxiliary variables. Furthermore, the quadratic program is convexified through the -underestimator to build a convex quadratic program and solve it using the Lagrange Multiplier Method. As a result, the iterative facto- rization method can strengthen relaxation through reducing the range of auxiliary variables, maintaining the increase in variable dimensionality and adding new constraint functions.