no. 6
Designing screen layout in multimedia applications through integer programming and metaheuristic
RAIRO. Operations Research, Tome 55 (2021) no. 6, pp. 3379-3397

Binding audiovisual content into multimedia applications requires the specification of each media item, including its size and position, to define a screen layout. The multimedia application author must plan the application’s screen layout (ASL), considering a variety of screen sizes where the application shall be executed. An ASL that maximizes the area occupied by media items on the screen is essential, given that screen space is a valuable asset for media broadcasters. In this paper, we introduce the Application Screen Layout Optimization Problem, and present its 𝒩P-hardness. Besides, two integer programming formulations and an Iterated Local Search (ILS) metaheuristic are proposed to solve it. The efficiency of the proposed methods is evaluated, showing that the metaheuristic achieves better results and is at least 12 times faster, on average, than the mathematical formulations. Also, the proposed approaches were compared to a layout design algorithm, showing their effectiveness.

DOI : 10.1051/ro/2021160
Classification : 90-05
Keywords: Screen layout planning, integer programming, ILS 
@article{RO_2021__55_6_3379_0,
     author = {Gonz\'alez, Pedro Henrique and Amorim, Glauco and Souza, Ueverton S. and Morais, Igor and dos Santos, Joel and Guimar\~aes, Vanessa de A. and Ribeiro, Glaydston M.},
     title = {Designing screen layout in multimedia applications through integer programming and metaheuristic},
     journal = {RAIRO. Operations Research},
     pages = {3379--3397},
     year = {2021},
     publisher = {EDP-Sciences},
     volume = {55},
     number = {6},
     doi = {10.1051/ro/2021160},
     mrnumber = {4338796},
     language = {en},
     url = {https://www.numdam.org/articles/10.1051/ro/2021160/}
}
TY  - JOUR
AU  - González, Pedro Henrique
AU  - Amorim, Glauco
AU  - Souza, Ueverton S.
AU  - Morais, Igor
AU  - dos Santos, Joel
AU  - Guimarães, Vanessa de A.
AU  - Ribeiro, Glaydston M.
TI  - Designing screen layout in multimedia applications through integer programming and metaheuristic
JO  - RAIRO. Operations Research
PY  - 2021
SP  - 3379
EP  - 3397
VL  - 55
IS  - 6
PB  - EDP-Sciences
UR  - https://www.numdam.org/articles/10.1051/ro/2021160/
DO  - 10.1051/ro/2021160
LA  - en
ID  - RO_2021__55_6_3379_0
ER  - 
%0 Journal Article
%A González, Pedro Henrique
%A Amorim, Glauco
%A Souza, Ueverton S.
%A Morais, Igor
%A dos Santos, Joel
%A Guimarães, Vanessa de A.
%A Ribeiro, Glaydston M.
%T Designing screen layout in multimedia applications through integer programming and metaheuristic
%J RAIRO. Operations Research
%D 2021
%P 3379-3397
%V 55
%N 6
%I EDP-Sciences
%U https://www.numdam.org/articles/10.1051/ro/2021160/
%R 10.1051/ro/2021160
%G en
%F RO_2021__55_6_3379_0
González, Pedro Henrique; Amorim, Glauco; Souza, Ueverton S.; Morais, Igor; dos Santos, Joel; Guimarães, Vanessa de A.; Ribeiro, Glaydston M. Designing screen layout in multimedia applications through integer programming and metaheuristic. RAIRO. Operations Research, Tome 55 (2021) no. 6, pp. 3379-3397. doi: 10.1051/ro/2021160

G. F. Amorim, J. A. F. Dos Santos and D. C. Muchaluat-Saade, Providing adjustable and dynamic spatial layouts for multimedia applications with style. Multimed. Tools. Appl. 79 (2020) 25989–26021. | DOI

A. Atamtürk, G. L. Nemhauser and M. W. P. Savelsbergh, Conflict graphs in solving integer programming problems. Eur. J. Oper. Res. 121 (2000) 40–55. | MR | Zbl | DOI

R. G. A. Azevedo, E. C. Araújo, B. Lima, L. F. G. Soares and M. F. Moreno, Composer: meeting non-functional aspects of hypermedia authoring environment. Multimed. Tools Appl. 70 (2014) 1199–1228. | DOI

J. E. Beasley, An exact two-dimensional non-guillotine cutting tree search procedure. Oper. Res. 33 (1985) 49–64. | MR | Zbl | DOI

D. Bulterman, P. Cesar and R. L. Guimaraes, Socially-aware multimedia authoring: Past, present, and future. ACM Trans. Multimedia Comput. Commun. Appl. (TOMCCAP) 9 (2013) 35.

A. Caprara and M. Monaci, On the two-dimensional knapsack problem. Oper. Res. Lett. 32 (2004) 5–14. | MR | Zbl | DOI

N. Clube, A liberdade de desenvolver e compartilhar conteúdo interativo (2011). http://clube.ncl.org.br/

M. Cygan, F. V. Fomin, Ł. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk and S. Saurabh, Parameterized algorithms, Vol. 4. Springer (2015). | MR | DOI

R. S. De Abreu, D. Mattos, Jd Santos, G. Ghinea and D. C. Muchaluat-Saade, Toward content-driven intelligent authoring of mulsemedia applications. IEEE MultiMed. 28 (2021) 7–16. | DOI

D. P. De Mattos and D. C. Muchaluat-Saade, Steve: Spatial-temporal view editor for authoring hypermedia documents. In: Proceedings of the 22Nd Brazilian Symposium on Multimedia and the Web, ACM, New York, NY, USA, Webmedia ‘16 (2016) 63–70. DOI: | DOI

A. M. Del Valle, T. A. De Queiroz, F. K. Miyazawa and E. C. Xavier, Heuristics for two-dimensional knapsack and cutting stock problems with items of irregular shape. Expert Syst. Appl. 39 (2012) 12589–12598. | DOI

R. G. Downey and M. R. Fellows, Fundamentals of parameterized complexity, vol. 4. Springer (2013). | MR | Zbl | DOI

K. A. Dowsland and W. B. Dowsland, Packing problems. Eur. J. Oper. Res. 56 (1992) 2–14. | Zbl | DOI

P. H. Gonzalez and J. Brandão, A biased random key genetic algorithm to solve the transmission expansion planning problem with re-design. In: 2018 IEEE Congress on Evolutionary Computation (CEC), IEEE (2018) 1–7.

P. H. Gonzalez, L. Simonetti, P. Michelon, C. Martinhon and E. Santos, A variable fixing heuristic with local branching for the fixed charge uncapacitated network design problem with user-optimal flow. Comput. Oper. Res. 76 (2016) 134–146. | MR | Zbl | DOI

P. H. Gonzalez, A. F. U. S. Macambira, R. V. Pinto, L. Simonetti, M. Maculan and P. Michelon, New proposals for modelling and solving the problem of covering solids using spheres of different radii. RAIRO-Oper. Res. 54 (2020) 873–882. | MR | Zbl | Numdam | DOI

HbbTV Association (2018) (2018) HbbTV 2.0.2 Specification. https://www.hbbtv.org/resourcelibrary/#specifications Accessed 20 July (2018).

K. He, Y. Jin and W. Huang, Heuristics for two-dimensional strip packing problem with 90 rotations. Expert Syst. Appl. 40 (2013) 5542–5550. | DOI

E. Huang and R. E. Korf, Optimal rectangle packing: An absolute placement approach. J. Artif. Intell. Res. 46 (2013) 47–87. | MR | Zbl | DOI

ITU, Nested Context Language (NCL) and Ginga-NCL for IPTV services. http://www.itu.int/rec/T-REC-H.761-200904-S, iTU-T Recommendation H.761 Accessed Mar. 13, 2018 (2009).

ITU, Integrated broadcast-broadband systems. https://www.itu.int/pub/R-REP-BT.2267-8-2018, Report ITU-R BT.2267-8 Accessed 15 December, 2018 (2018).

R. M. Karp, Reducibility among combinatorial problems. In: Complexity of computer computations, Springer (1972) 85–103. | MR | Zbl | DOI

S. C. H. Leung and D. Zhang, A fast layer-based heuristic for non-guillotine strip packing. Expert Syst. Appl. 38 (2011) 13032–13042. | DOI

J. Li, T. Röggla, M. Glancy, J. Jansen and P. Cesar, A new production platform for authoring object-based multiscreen tv viewing experiences. In: Proceedings of the 2018 ACM International Conference on Interactive Experiences for TV and Online Video (2018) 115–126. | DOI

J. Li, Z. Zheng, B. Meixner, T. Röggla, M. Glancy and P. Cesar, Designing an object-based preproduction tool for multiscreen tv viewing. In: Extended Abstracts of the 2018 CHI Conference on Human Factors in Computing Systems (2018) 1–6.

H. Lourenço, O. Martin and T. Stutzle, Iterated local search. In “Handbook of Metaheuristics”, edited by F. Glover and G. Kochenberger. isorm 57 (2002) 321–353. | MR | Zbl

D. P. D. Mattos, D. C. Muchaluat-Saade and G. Ghinea, Beyond multimedia authoring: On the need for mulsemedia authoring tools. IEEE MultiMed. 54 (2021) 1–31.

R. Meirelles, C. Júlio and Á. M. Dias, Dias, Economia e Consumo na Era da Pandemia, Tech. rep., Locomotiva - Pesquisa e Estratégia (2020). DOI: . | DOI

E. Santos, L. S. Ochi, L. Simonetti and P. H. González, A hybrid heuristic based on iterated local search for multivehicle inventory routing problem. Electron. Notes Discrete Math. 52 (2016) 197–204. | MR | Zbl | DOI

G. Souto, I. Morais, G. R. Mauri, G. M. Ribeiro and P. H. González, A hybrid matheuristic for the two-stage capacitated facility location problem. Expert Syst. Appl. 185 (2021) 115501. | DOI

R. E. Tarjan and A. E. Trojanowski, Finding a maximum independent set. SIAM J. Comput. 6 (1977) 537–546. | MR | Zbl | DOI

W3C, Synchronized Multimedia Integration Language - SMIL 3.0 Specification. http://www.w3c.org/TR/SMIL3, world-Wide Web Consortium Recommendation Accessed Fev. 15, 2018 (2008).

W3C, HTML5: A vocabulary and associated APIs for HTML and XHTML. https://www.w3.org/TR/2010/WD-html5-20100624/, world-Wide Web Consortium Recommendation Accessed Mar. 12, 2018 (2014).

W3C, CSS Flexible Box Layout Module Level 1. https://www.w3.org/TR/css-flexbox-1/, w3C Candidate Recommendation Accessed Apr. 05, 2018 (2017).

W3C, CSS Grid Layout Module Level 1. https://www.w3.org/TR/css-grid/, w3C Candidate Recommendation Accessed Apr. 05, 2018 (2017).

Y. Wang and L. Chen, Two-dimensional residual-space-maximized packing. Expert Syst. Appl. 42 (2015) 3297–3305. | DOI

L. Wolsey, Integer Programming. Wiley Series in Discrete Mathematics and Optimization, Wiley (1998). | MR | Zbl

G. Wäscher, H. Haußner and H. Schumann, An improved typology of cutting and packing problems. Eur. J. Oper. Res. 183 (2007) 1109–1130. | Zbl | DOI

Z. Z. Zeng, X. G. Yu, K. He and Z. H. Fu, Adaptive tabu search and variable neighborhood descent for packing unequal circles into a square. Appl. Soft Comput. J. 65 (2018) 196–213. | DOI

B. Zhang, H. F. Teng and Y. J. Shi, Layout optimization of satellite module using soft computing techniques. Appl. Soft Comput. 8 (2008) 507–521. | DOI

Cité par Sources :