Graph-Based Modeling for Optimal Strategy in Online Buying


  • Ruffiana Tarigan Universitas Sumatera Utara
  • Mardiningsih universitas sumatera utara
  • Saib Suwilo universitas sumatera utara




Discount is a type of online purchase promotion that is presented based on the total value of consumer purchases. In this paper, an online purchase optimization problem will be studied, where a buyer is interested in buying several items (x≥2) by considering the total value discounts from different retailers, so that result in significant cost savings. The comparison shopping websites can be an alternative for consumers to find and compare information on items they want to buy from many online retailers. An integer programming formulation is proposed to obtain a near-optimal model of the online purchase problem. Then this formulation was developed into a graph-based modeling which was presented to build an optimization model (OptiGraph). The OptiGraph model obtained consists of the OptiNode set (subgraph) SG_a,SG_b,SG_c (retailer a, b, and c which contains nodes m_1 and m_2 in each subgraph representing the item to be purchased) and the OptiEdge set which describes the relationship between nodes in the subgraph. All nodes and edges contain the constraint function properties of the integer programming formulation of the online purchase problem with discount.


GS Cited Analysis


Download data is not yet available.


Blazewicz, J., Bouvry, P., Kovalyov, M. Y. & Musial, J. (2014). Internet shopping with price sensitive discounts. 4OR, 12(1), 35–48.

Błażewicz, J., Kovalyov, Y. M., Musiał, J., Urbański, A. P. & Wojciechowski, A. (2010). Internet shopping optimization problem.

Błażewicz, J. & Musiał, J. (2011). E-commerce evaluation–multi-item internet shopping. Optimization and heuristic algorithms. In Operations Research Proceedings 2010 (pp. 149–154). Springer.

Jalving, J., Shin, S. & Zavala, V. M. (2020). A graph-based modeling abstraction for optimization: Concepts and implementation in plasmo.jl. ArXiv Preprint ArXiv:2006.05378.

Kameshwaran, S. & Benyoucef, L. (2008). Optimal buying from online retailers offering total value discounts. Proceedings of the 10th International Conference on Electronic Commerce, 1–5.

Khattak, U. F., Mustapha, A., Yaseen, M., Shah, M. A. & Shahzad, A. (2019). Enhancing Integrity Technique Using Distributed Query Operation. In Recent Trends and Advances in Wireless and IoT-enabled Networks (pp. 139–146). Springer.

Musial, J., Pecero, J. E., Lopez-Loces, M. C., Fraire-Huacuja, H. J., Bouvry, P. & Blazewicz, J. (2016). Algorithms solving the Internet shopping optimization problem with price discounts. Bulletin of the Polish Academy of Sciences: Technical Sciences, 505–516.


Crossmark Updates

How to Cite

Tarigan, R., Mardiningsih, & Suwilo, S. (2022). Graph-Based Modeling for Optimal Strategy in Online Buying. Sinkron : Jurnal Dan Penelitian Teknik Informatika, 7(3), 2096-2102.