Integer Programming, low complexity Heuristics, and Gaussian instances for the Internet Shopping Optimization Problem with multiple item Units (ISHOP-U)

Abstract

The Internet Shopping Optimization Problem with multiple item Units (ISHOP-U) is a recently proven NP-Hard variant of the classical ISHOP, which considers buying more than one unit of the same product. In this work, we propose a new set of instances where the prices of the products follow a Gaussian distribution, which is more realistic in a competitive market than the original instances with random uniform prices. We compute the optimal values of the previous uniform and new Gaussian instances using an Integer Programming formulation in CPLEX. In addition, we also propose two new low-complexity heuristics, the first not metaheuristics approaches proposed for the ISHOP-U, which use a linear representation instead of the original matrix candidate solution, achieving better results than the previous Evolutionary Algorithms for the ISHOP-U from the state-of-the-art.