Vittorio Maniezzo
Moreno Marzolla
Skip Abstract Section
Abstract
Mobile platforms have matured to a point where they can provide the infrastructure required to support sophisticated optimization codes. This opens the possibility to envisage new interest for distributed application codes and the opportunity to intensify research on optimization algorithms requiring limited computational resources, as provided by mobile platforms.
In this article, we report on some exploratory experience in this area. We illustrate some practical, real-world cases where running optimization programs on mobile or embedded devices can be useful, with particular emphasis on matheuristics approaches. Then, we discuss a practical use case involving the feasibility version of the generalized assignment problem (GAP). We present a JavaScript implementation of a GAP solver that can be executed inside an ordinary browser supporting ECMAScript. We tested the code on different smartphones of varying age and power, as well as on desktop PCs and other embedded devices. Our experiments confirm the viability of mobile devices for computational intensive tasks.
- L. Atzori, A. Iera, and G. Morabito. 2010. The internet of things: A survey. Comput. Netw. 54, 15 (2010), 2787--2805. Google Scholar
Digital Library
- J. E. Beasley. 1993. Lagrangian relaxation. In Modern Heuristic Techniques for Combinatorial Problems, Colin R. Reeves (Ed.). John Wiley 8 Sons, New York, NY, 243--303. Google ScholarDigital Library
- M. A. Boschetti, V. Maniezzo, and M. Roffilli. 2011. A fully distributed Lagrangian solution for a peer-to-peer overlay network design problem. INFORMS J. Comput. 23, 1 (2011), 90--104. Google ScholarDigital Library
- M. A. Boschetti and V. Maniezzo. 2009. Benders decomposition, Lagrangian relaxation and metaheuristic design. J. Heuristics 15, 3 (June 2009), 283--312. Google ScholarDigital Library
- M. A. Boschetti, V. Maniezzo, M. Roffilli, and A. Bolufé Röhler. 2009. Matheuristics: Optimization, simulation and control. In Hybrid Metaheuristics, María J. Blesa, Christian Blum, Luca Di Gaspero, Andrea Roli, Michael Sampels, and Andrea Schaerf (Eds.). Springer Berlin, 171--177. Google ScholarDigital Library
- D. Cattrysse, M. Salomon, and L. N. Van Wassenhove. 1994. A set partitioning heuristic for the generalized assignment problem. Europ. J. Op. Res. 72 (1994), 167--174.Google ScholarCross Ref
- L. Chen. 2018. Keras.js. Retrieved from https://github.com/transcranial/keras-js.Google Scholar
- J. W. Chinneck, B. Kristjansson, and M. J. Saltzman. 2009. Operations Research and Cyber-Infrastructure. Springer, Boston, MA. Google ScholarDigital Library
- P. C. Chu and J. E. Beasley. 1997. A genetic algorithm for the generalised assignment problem. Comput. Op. Res. 24 (1997), 17--23. Google ScholarDigital Library
- M. Chui, M. Loeffler, and R. Roberts. 2010. The internet of things. Retrieved from http://www.mckinsey.com/industries/high-tech/our-insights/the-internet-of-things.Google Scholar
- W. J. Cook. 2012a. Concorde TSP solver for iOS. Retrieved from http://www.math.uwaterloo.ca/tsp/iphone/index.html.Google Scholar
- W. J. Cook. 2012b. In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation. Princeton University Press, Princeton, NJ.Google Scholar
- J. Czyzyk, M. P. Mesnier, and J. J. Moré. 1998. The NEOS Server. IEEE J. Comput. Sci. Eng. 5, 3 (1998), 68--75. Google ScholarDigital Library
- J. de Jong. 2018. Mathjs: An extensive math library for JavaScript and Node.js. Retrieved from http://mathjs.org/.Google Scholar
- J. Dongarra and P. Luszczek. 2012. Anatomy of a globally recursive embedded LINPACK benchmark. In Proceedings of the IEEE Conference on High Performance Extreme Computing. 1--6.Google Scholar
- Economist IoT 2017. The internet of things business index 2017—Transformation in motion. Retrieved from https://www.eiuperspectives.economist.com/sites/default/files/EIU-ARM-IBM%20IoT%20Business%20Index%202017%20copy.pdf.Google Scholar
- Euro PhD School (EPS). 2016. Retrieved from https://sites.google.com/site/eps2016matheuristics/.Google Scholar
- S. Farokhi, P. Jamshidi, I. Brandic, and E. Elmroth. 2015. Self-adaptation challenges for cloud-based applications: A control theoretic perspective. In Proceedings of the 10th International Workshop on Feedback Computing.Google Scholar
- R. Fourer. 2010. Cyberinfrastructure and optimization. In A Long View of Research and Practice in Operations Research and Management Science—The Past and the Future, ManMohan S. Sodhi and Christopher S. Tang (Eds.). Volume 148 of International Series in Operations Research and Management Science, 219--229.Google Scholar
- R. Gabrielli, A. Guidazzi, M. A. Boschetti, V. Maniezzo, and M. Roffilli. 2006. Practical origin-destination traffic flow estimation. In Proceedings of the 3rd International Workshop on Freight Transportation and Logistics (Odysseus’06).Google Scholar
- B. Golden. 2017. Where will IoT computing reside? Retrieved from https://insights.hpe.com/articles/where-will-iot-computing-reside-1702.html.Google Scholar
- Google. 2018. Progressive web apps: A new way to deliver amazing user experiences on the web. Retrieved from https://developers.google.com/web/progressive-web-apps/.Google Scholar
- Google Maps 2018. Google Maps help: Download areas and navigate offline. Retrieved from https://support.google.com/maps/answer/6291838?co=GENIE.Platform%3DAndroid8hl=en.Google Scholar
- D. Guinard, V. Trifa, T. Pham, and O. Liechti. 2009. Towards physical mashups in the web of things. In Proceedings of the 6th International Conference on Networked Sensing Systems (INSS’09). IEEE Press, Piscataway, NJ, 196--199. Google ScholarDigital Library
- Gurobi Optimization 2018. Gurobi Instant Cloud. Retrieved from http://www.gurobi.com/products/gurobi-cloud.Google Scholar
- M. Halpern, Y. Zhu, and V. J. Reddi. 2016. Mobile CPU’s rise to power: Quantifying the impact of generational mobile CPU design trends on performance, energy, and user satisfaction. In Proceedings of the IEEE International Symposium on High Performance Computer Architecture (HPCA’16). IEEE, 64--76.Google Scholar
- M. Held, P. Wolfe, and H. P. Crowder. 1974. Validation of subgradient optimization. Math. Prog. 6, 1 (Dec. 1974), 62--88. Google ScholarDigital Library
- Here WeGo. 2018. Offline maps 8 GPS. Retrieved from https://play.google.com/store/apps/details?id=com.here.app.maps.Google Scholar
- D. Herman, L. Wagner, and A. Zakai. 2014. Asm.js. Working draft. Retrieved from http://asmjs.org/spec/latest/.Google Scholar
- O. Hersent, D. Boswarthick, and O. Elloumi. 2012. The Internet of Things: Key Applications and Protocols (2nd ed.). John Wiley 8 Sons. Google ScholarDigital Library
- IBM. 2018. IBM Decision Optimization on Cloud. Retrieved from https://www.ibm.com/us-en/marketplace/decision-optimization-cloud.Google Scholar
- M. López-Ibáñez, J. Dubois-Lacoste, L. Pérez Càceres, M. Birattari, and T. Stützle. 2016. The irace package: Iterated racing for automatic algorithm configuration. Op. Res. Persp. 3 (2016), 43--58.Google ScholarCross Ref
- V. Maniezzo. 2018a. Bridging the GAP, some generalized assignment problem instances. Retrieved from http://astarte.csr.unibo.it/gapdata/gapinstances.html.Google Scholar
- V. Maniezzo. 2018b. JavaScript GAP solver. Retrieved from http://astarte.csr.unibo.it/GAPJS/.Google Scholar
- V. Maniezzo, M. A. Boschetti, and W. J. Gutjahr. 2017. Stochastic pre-marshalling of block stacking warehouses. Working paper.Google Scholar
- V. Maniezzo, M. A. Boschetti, and M. Roffilli. 2009. Matheuristics in simulation: A case study in water supply management. In Proceedings of the 8th Metaheuristic International Conference (MIC’09), M. Caserta and S. Voß (Eds.). 1--10.Google Scholar
- V. Maniezzo, T. Stützle, and S. Voß (Eds.). 2010. Matheuristics: Hybridizing Metaheuristics and Mathematical Programming. Springer. Google ScholarDigital Library
- S. Martello and P. Toth. 1990. Knapsack Problems: Algorithms and Computer Implementations. John Wiley 8 Sons. Google ScholarDigital Library
- NEOS Server 2018. NEOS Server: state-of-the-art solvers for numerical optimization. Retrieved from https://neos-server.org/neos/.Google Scholar
- NSF. 2004. An operations cyberinfrastructure: Using cyberinfrastructure and operations research to improve productivity in the enterprise. Retrieved from http://www.optimization-online.org/OCI/OCI.pdf.Google Scholar
- Numeric JavaScript. 2018. Numericjs. Retrieved from http://numericjs.com/numeric/benchmark.html.Google Scholar
- I. H. Osman. 1995. Heuristics for the generalised assignment problem: Simulated annealing and tabu search approaches. Op.-Res.-Spektrum 17, 4 (Dec. 1995), 211--225. Google ScholarDigital Library
- B. T. Polyak. 1969. Minimization of unsmooth functionals. U. S. S. R. Comput. Math. and Math. Phys. 9 (1969), 14--29.Google ScholarCross Ref
- D. Raggett, K. Ashimura, and Y. Chen. 2016. W3C white paper for the web of things. Retrieved from https://www.w3.org/2016/08/wot-white-paper/.Google Scholar
- S. Remde. 2018. Node-lp_solve: A NodeJS module for creating and solving simple linear programs using lp_solve. Retrieved from https://github.com/smremde/node-lp_solve.Google Scholar
- A. Rossberg. 2018. WebAssembly Core Specification. W3C Working Draft. Retrieved from https://www.w3.org/TR/2018/WD-wasm-core-1-20180215/.Google Scholar
- A. Russell, J. Song, J. Archibald, and M. Kruisselbrink. 2017. Service Workers 1. W3C Working Draft. Retrieved from https://www.w3.org/TR/service-workers/.Google Scholar
- N. Z. Shor. 1985. Minimization Methods for Non-differentiable Functions. Springer-Verlag. Google Scholar
- Stdlib. 2018. Stdlib: A standard library for JavScript and Node.js. Retrieved from https://stdlib.io/.Google Scholar
- TensorFlow. 2018. TensorFlow. Retrieved from https://js.tensorflow.org/.Google Scholar
- TensorFlow.js. 2018. Tensorflow.js. Retrieved from https://js.tensorflow.org/.Google Scholar
- Three.js. 2018. Three.js. Retrieved from https://threejs.org/.Google Scholar
- J. A. Tompkins, J. A. White, Y. A. Bozer, and J. M. A. Tanchoco. 2010. Facilities Planning. John Wiley 8 Sons.Google Scholar
- J. Vaillant. 2018a. Glpk.js. Retrieved from https://github.com/jvail/glpk.js.Google Scholar
- J. Vaillant. 2018b. Spatiasql.js. Retrieved from https://github.com/jvail/spatiasql.js.Google Scholar
- S. Walter. 2016. The (not so) secret powers of the mobile browser. Smash. Mag. (Dec. 2016). Retrieved from https://www.smashingmagazine.com/2016/12/the-not-so-secret-powers-of-the-mobile-browser/.Google Scholar
- Wikipedia. 2018. Comparison of smartphones. Retrieved from https://en.wikipedia.org/wiki/Comparison_of_smartphones.Google Scholar
- J. Wolcott. 2018. JavaScript LP solver. Retrieved from https://github.com/JWally/jsLPSolver.Google Scholar
- L. D. Xu and W. He. 2014. Internet of things in industries: A survey. IEEE Trans. Industr. Inform. 10 (Nov. 2014), 2233--2243.Google ScholarCross Ref
- M. Yagiura, T. Ibaraki, and F. Glover. 2004. An ejection chain approach for the generalized assignment problem. INFORMS J. Comput. 16, 2 (2004), 133--151. Google ScholarDigital Library
Index Terms
- Client-side Computational Optimization
Recommendations
Improving Legacy Applications with Client-Side Augmentations
Web EngineeringAbstractMobile devices have become the most prominent channel to access Web applications. While every mobile device platform like Android or iOS has their own application ecosystem, they are also often used to access Web sites which are not property ...
Set-based discrete particle swarm optimization and its applications: a survey
Particle swarm optimization (PSO) is one of the most popular population-based stochastic algorithms for solving complex optimization problems. While PSO is simple and effective, it is originally defined in continuous space. In order to take advantage of ...
On the Invariance of Ant Colony Optimization
Ant colony optimization (ACO) is a promising metaheuristic and a great amount of research has been devoted to its empirical and theoretical analysis. Recently, with the introduction of the hypercube framework, Blum and Dorigo have explicitly raised the ...
Comments