JUCS - Journal of Universal Computer Science 31(3): 298-309, doi: 10.3897/jucs.150245

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

Fernando Ornelas^‡, Alejandro H. García^‡, Alejandro Santiago^‡, Salvador Ibarra Martínez^‡, José Antonio Castán Rocha^‡, Fausto Balderas^§, Julio Laria-Menchaca^‡, Mayra Guadalupe Treviño-Berrones^‡

‡ Autonomous University of Tamaulipas, Tampico, Mexico§ Instituto Tecnológico de Ciudad Madero, Ciudad Madero, Mexico

Corresponding author: Alejandro Santiago ( alx.santiago@gmail.com )

This is an open access article distributed under the terms of the Creative Commons Attribution License (CC BY 4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.

Citation: Ornelas F, García AH, Santiago A, Ibarra Martínez S, Castán Rocha JA, Balderas F, Laria-Menchaca J, Treviño-Berrones MG (2025) Integer Programming, low complexity Heuristics, and Gaussian instances for the Internet Shopping Optimization Problem with multiple item Units (ISHOP-U). JUCS - Journal of Universal Computer Science 31(3): 298-309. https://doi.org/10.3897/jucs.150245

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.

Keywords

The Internet Shopping Optimization Problem with Multiple Item Units (ISHOP-U), Integer Linear Programming (ILP), Instances, Benchmark, Testbed