Internet of things (IoT) technology have evolved tremendously over the past few years. Owing to the recent research and development in IoT and M2M communication. Wi-Fi, LiFi, Bluetooth, Cellular technologies and LPWANS are widely used for communication globally, to stay connected, with the main focus to interconnect things, devices altogether allowing people to manage and monitor the behavior of devices from anywhere in the world. Long-range (LoRa) is a communication technology operating in unlicensed frequency spectrum. However, modest data rates, extensively wide range and low-power requirement, makes it favorable technology for majority of the internet of things verticals. LoRa allows End Devices to dynamically select LoRa radio resources in vicinity of LoRa networks. Though, LoRaWAN communication technology is has revolutionized over past few years, most broadly used and fastest growing networks of IoT due to its attractive characteristics like low power consumption, low cost, fast long range bidirectional communication, less bandwidth requirement, License free ISM standard. Clearly, it's a very assuring technology and will be universally accepted in near future, yet we are not witnessing huge IoT deployment, this is, due to issues, such as networking, signal interference, massive deployment, security concerns and concurrent transmission collisions, which need to be addressed effectively. This paper aims at summarizing various wireless technologies, background of LoRa and LoRaWAN, use cases, literature review of the existing solutions to examine recent research works on LoRaWAN performance aspects like networking, scalability, inference, state of art solutions, and classifying the security issues. In addition, a brief summary on, future research directions for potential challenges, problem formulation and proposed methodology based on machine learning approach for dynamic resource allocation, minimize collision and enhance performance of LoRaWAN for effective massive IoT deployment under secure environment, is discussed.
10 Accesses
Explore all metrics
A graph is said to be two connected if between every pair of nodes there are at least two node-disjoint paths. Given weights on the edges of the graph, the two connected subgraph problem is to find a two connected spanning subgraph of G whose weight is minimum. This problem has many applications in telecommunications. In this paper we consider a new variant of this problem with additional disjunctive constraints (called also conflict constraints) related to the survivability of telecommunication networks. This can be called the Disjunctive Two-Connected Subgraph Problem (DTCSP). First, we give an extended formulation for the problem whose variables are the cycles of the graph. Then, we use a column generation algorithm to solve its linear relaxation, and further show that the pricing reduces to finding a specific cycle in the graph which can be formulated as an integer programming problem. We also describe several valid inequalities for the polytope. Moreover, we study the related separation problems and devise separation routines for these inequalities. Using this, we devise a Branch-and-Cut-and-Price algorithm for the problem along with an extensive experimental study.
This is a preview of subscription content, log in via an institution to check access.
Price includes VAT (Russian Federation)
Instant access to the full article PDF.
Rent this article via DeepDyve
Institutional subscriptions
Lift-and-project cuts for convex mixed integer nonlinear programs.
Baïou, M., & Mahjoub, A. R. (1997). Steiner 2-edge connected subgraph polytopes on series-parallel graphs. SIAM Journal on Discrete Mathematics, 10 (3), 505–514.
Article Google Scholar
Barahona, F., & Mahjoub, A. R. (1995). On two connected subgraph polytopes. In Discrete Mathematics , (pp. 19–34).
Ben Salem, M., Hanafi, S., Taktak, R., & Ben-Abdallah, H. (2017). Probabilistic tabu search with multiple neighborhoods for the disjunctively constrained knapsack problem. RAIRO-Operations Research, 51 (3), 627–637.
Ben Salem, M., Taktak, R., Mahjoub, A. R., & Ben-Abdallah, H. (2018). Optimization algorithms for the disjunctively constrained knapsack problem. Soft Computing, 22 (6), 2025–2043.
Bendali, F., Diarrassouba, I., Didi, Biha M., Mailfert, J., & Mahjoub, A. R. (2010). A Branch-and-Cut algorithm for the k-edge connected subgraph problem. Networks, 55 (1), 13–32.
Carrabs, F., Cerulli, R., Pentangelo, R., & Raiconi, A. (2021). Minimum spanning tree with conflicting edge pairs: A branchand-cut approach. Annals of Operations Research, 298 (1), 65–78.
Carrabs, F., & Gaudioso, M. (2021). A lagrangian approach for the minimum spanning tree problem with conflicting edge pairs. Networks, 78 (1), 32–45.
Cplex, I. I. (2020). V12. 9: User’s Manual for CPLEX. International Business Machines Corporation, 46 (53), 157.
Google Scholar
Darmann, A., Pferschy, U., Schauer, J., & Woeginger, G. J. (2011). Paths, trees and matchings under disjunctive constraints. Discrete Applied Mathematics, 159 (16), 1726–1735.
Diarrassouba, I., Mahjoub, A. R., & Kutucu, H. (2013). Two Node-Disjoint Hop-Constrained Survivable Network Design and Polyhedra. In Electronic Notes in Discrete Mathematics , (pp. 551–558).
Diarrassouba, I., Mahjoub, M., Mahjoub, A. R., & Taktak, R. (2016). The k-node connected subgraph problem: Polyhedral analysis and Branch-and-Cut. In Electronic Notes in Discrete Mathematics , (pp. 117–124).
Diarrassouba, I., Mahjoub, M., Mahjoub, A. R., & Yaman, H. (2016). k-node-disjoint hop-constrained survivable networks: polyhedral analysis and branch and cut. In Annals of Telecommunications , (pp. 5–28).
Diarrassouba, I, Mahjoub, M., Mahjoub, A. R., & Taktak, R. (2017). The survivable k-node-connected network design problem: Valid inequalities and Branch-and-Cut. In Computers and Industrial Engineering , (pp. 690–705).
Dixon, E. T., & Goodman, S. E. (1976). An algorithm for the longest cycle problem. In Networks , (pp. 139–149).
Ekici, A. (2021). Bin packing problem with conflicts and item fragmentation. Computers & Operations Research, 126 , 105–113.
Erickson, R. E., Monma, C. L., & Veinott, A. F. (1987). Send-and-Split Method for Minimum-Concave-Cost Network Flows. In Mathematics of Operations Research , (pp. 634–664).
Fortz, B., & Labbé, M. (2002). Polyhedral results for two-connected networks with bounded rings. In Mathematical Programming Journal , (pp. 27–54).
Gamrath, G., Anderson, D., Bestuzheva, K., Chen, W.K., Eifler, L., Gasse, M., Gemander, P., Gleixner, A., Gottwald, L., Halbig, K., and Hendel, G., and Hojny, C., Koch, T., Bodic, L., Maher, P. J., Matter, F., Miltenberger, M., Mühmer, E., Müller, B., Pfetsch, M.E., Schlösser, F., Serrano, F., Shinano, Y., Tawfik, C., Vigerske, S., Wegscheider, F., Weninger, D., & Witzig, J. (2020). The SCIP Optimization Suite 7.0. In Zuse Institute Berlin, March .
Garey, M.R., & Johnson, D.S. (1979). Computers and intractability: A guide to the theory of NP-completeness (series of books in the mathematical sciences) . W. H. Freeman & Co Ltd, First edition.
Goldberg, A.V., & Tarjan, R. E. (1986). A New Approach to the Maximum Flow Problem. In Proceedings of the Eighteenth Annual Association for Computing Machinery Symposium on Theory of Computing , (pp. 136–146).
Grötschel, M., & Monma, C.L. (1990). Integer Polyhedra Arising from Certain Network Design Problems with Connectivity Constraints. In SIAM Journal on Discrete Mathematics , (pp. 502-523).
Grötschel, M., Lovász, L., & Schrijver, A. (2012). Geometric algorithms and combinatorial optimization . Springer Science & Business Media.
Grötschel, M., Monma, C. L., & Stoer, M. (1992). Computational Results with a Cutting Plane Algorithm for Designing Communication Networks with Low-Connectivity Constraints. In Operations Research Journal , (pp. 309–330).
Grötschel, M., Monma, C. L., & Stoer, M. (1992). Facets for Polyhedra Arising in the Design of Communication Networks with Low-Connectivity Constraints. In SIAM Journal on Optimization , (pp. 474–504).
Grötschel, M., Monma, C. L., & Stoer, M. (1995). Polyhedral and computational investigations for designing communication networks with high survivability requirements. Operations Research, 43 , 1012–1024.
Gusfield, D. (1987). Very simple algorithms and programs for all pairs network flow analysis. In Technical report, Computer Science Division , University of California, Davis.
Gusfield, D. (1990). Very simple methods for all pairs network flow analysis. SIAM Journal of Computing, 19 (1), 143–155.
Karp, R. M. (1972). Reducibility among Combinatorial Problems. In Complexity of Computer Computations: Proceedings of a symposium on the Complexity of Computer Computations, held March 20–22, 1972, at the IBM Thomas J. Watson Research Center , (pp. 85–94).
Kerivin, H., & Mahjoub, A. R. (2005). On survivable network polyhedra. In Discrete Mathematics , (pp. 183–210).
Kerivin, H., Mahjoub, A. R., & Nocq, C. (2004). (1,2)-Survivable Networks: Facets and Branch & Cut. In The Sharpest Cut: the Impact of Manfred Padberg and his Work , (pp. 121–152). Mathematical Programming Society : Philadelphia.
Mahjoub, A. R. (1994). Two edge connected spanning subgraphs and polyhedra. In Mathematical Programming , (pp. 199–208).
Mahjoub, A. R. (1997). On Perfectly Two-Edge Connected Graphs. In Discrete Math. , (pp. 153–172). Elsevier Science Publishers B. V.
Mahjoub, A. R. (2010). Polyhedral approaches. In Vangelis Paschos, editor, Concepts of Combinatorial Optimization, ISTE- WIELY , (pp. 261–324).
Mahjoub, M. (2017). The Survivable Network Design Problems with High Node-Connectivity Constraints : Polyhedra and Algorithms. In Theses, Université Paris sciences et lettres , Université de Tunis El Manar.
Mahjoub, A. R., & Nocq, C. (1999). On the linear relaxation of the 2-node connected subgraph polytope. In Discrete Applied Mathematics , (pp. 389–416).
Mahjoub, A. R., & Pesneau, P. (2008). On the Steiner 2-edge connected subgraph polytope. In RAIRO , (pp. 259–283).
Mahjoub, A. R., Poss, M., Simonetti, L., & Uchoa, E. (2019). Distance Transformation for Network Design Problems. In SIAM Journal on Optimization , (pp. 1687–1713).
Mahjoub, A. R., Simonetti, L., & Uchoa, E. (2011). Hop-level flow formulation for the survivable network design with hop constraints problem. In Network optimization book , (pp. 171–179).
Menger, K. (1927). Zur allgemeinen Kurventheorie. Fundamenta Mathematicae, 10 (1), 96–115.
Monma, C. L., Munson, B. S., & Pulleyblank, W. R. (1990). Minimum-weight two-connected spanning networks. Mathematical Programming, 46 , 153–171.
Nemhauser, G. L., & Sigismondi, G. (1992). A Strong Cutting Plane/Branch-and-Bound Algorithm for Node Packing. In The Journal of the Operational Research Society , (pp. 443–457).
Öncan, T., Zhang, R., & Punnen, A. P. (2013). The minimum cost perfect matching problem with conflict pair constraints. Computers & Operations Research, 40 (4), 920–930.
Orlowski, S., Pióro, M., Tomaszewski, A., & Wessäly, R. (2007). SNDlib 1.0-Survivable Network Design Library. In Proceedings of the 3rd International Network Optimization Conference (INOC 2007) . Spa, Belgium.
Padberg, M. W. (1973). On the facial structure of set packing polyhedra. Mathematical Programming, 5 , 199–215.
Pferschy, U., & Schauer, J. (2013). The maximum flow problem with disjunctive constraints. Journal of Combinatorial Optimization, 26 (1), 109–119.
Reinelt, G. (1991). TSPLIB–A Traveling Salesman Problem Library. In ORSA Journal on Computing , (pp. 376–384).
Sadykov, R., & Vanderbeck, F. (2013). Bin packing with conflicts: a generic Branch-and-Price algorithm. INFORMS Journal on Computing, 25 (2), 244–255.
Samer, P., & Urrutia, S. (2015). A branch and cut algorithm for minimum spanning trees under conflict constraints. Optimization Letters, 9 (1), 41–55.
Senisuka, A., You, B., & Yamada, T. (2005). Reduction and exact algorithms for the disjunctively constrained knapsack problem. In International symposium, operational research Bremen . Citeseer.
Şuvak, Z., Altınel, I. K., & Aras, N. (2020). Exact solution algorithms for the maximum flow problem with additional conflict constraints. European Journal of Operational Research, 287 (2), 410–437.
Şuvak, Z., Altınel, I. K., & Aras, N. (2021). Minimum cost flow problem with conflicts. Networks, 78 (4), 421–442.
Talbi, E. G. (2009) Metaheuristics: From Design to Implementation . Wiley Publishing.
Winter, P. (1986). Generalized Steiner Problem in Series-Parallel Networks. In J. Algorithms , (pp. 549–566).
Winter, P. (1987). Steiner Problem in Halin Networks. In Discrete Applied Mathematics , (pp. 281–294).
Winter, P. (1985). Generalized Steiner problem in outerplanar networks. BIT, 25 , 485–496.
Yamada, T., Kataoka, S., & Watanabe, K. (2002). Heuristic and exact algorithms for the disjunctively constrained knapsack problem. Information Processing Society of Japan Journal , 43 (9).
Download references
Authors and affiliations.
Department of Statistics and Operations Research, College of Science, Kuwait University, Kuwait, Kuwait
Fatmah Almathkour
LMAH, Le Havre Normandie University, Le Havre, France
Ibrahima Diarrassouba
LIMOS, UMR CNRS 6158, Clermont Auvergne INP, 63178, Clermont-Ferrand, France
Youssouf Hadhbi
You can also search for this author in PubMed Google Scholar
Correspondence to Fatmah Almathkour .
Publisher's note.
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
Reprints and permissions
Almathkour, F., Diarrassouba, I. & Hadhbi, Y. Extended formulation and Branch-and-Cut-and-Price algorithm for the two connected subgraph problem with disjunctive constraints. Ann Oper Res (2024). https://doi.org/10.1007/s10479-024-06123-0
Download citation
Received : 21 July 2023
Accepted : 13 June 2024
Published : 28 June 2024
DOI : https://doi.org/10.1007/s10479-024-06123-0
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative
IMAGES
VIDEO
COMMENTS
Characteristics, Types, and Examples. August 22, 2023 Sunaina Singh. Knowing the basics of defining a research problem is instrumental in formulating a research inquiry. A research problem is a gap in existing knowledge, a contradiction in an established theory, or a real-world challenge that a researcher aims to address in their research.
A research problem that addresses important questions and has practical implications is more likely to be valuable to the academic community and beyond. Stakeholder Involvement: In some cases, involving relevant stakeholders early in the process of formulating a research problem can be beneficial.
A research problem is a specific issue or gap in existing knowledge that you aim to address in your research. You may choose to look for practical problems aimed at contributing to change, or theoretical problems aimed at expanding knowledge. Some research will do both of these things, but usually the research problem focuses on one or the other.
Feasibility: A research problem should be feasible in terms of the availability of data, resources, and research methods. It should be realistic and practical to conduct the study within the available time, budget, and resources. Novelty: A research problem should be novel or original in some way.
Formulation of research question (RQ) is an essentiality before starting any research. It aims to explore an existing uncertainty in an area of concern and points to a need for deliberate investigation. It is, therefore, pertinent to formulate a good RQ. ... [1,2,3,4] RQ identifies the problem to be studied and guides to the methodology. It ...
Download the exercise that also appears in your textbook to help you step-by-step in formulating your own research problem. You can also use this exercise to contribute to a final research portfolio or help guide discussions with your supervisor. Developing a research project: A set of exercises for beginners
A research problem can be theoretical in nature, focusing on an area of academic research that is lacking in some way. Alternatively, a research problem can be more applied in nature, focused on finding a practical solution to an established problem within an industry or an organisation. In other words, theoretical research problems are motivated by the desire to grow the overall body of ...
the research problem formulation. 5 Any research starts with a question, the answer to which is unknown or unavail - able. 5 The research is completed when the answer is found. One can say "a problem well put is a problem half solved." Chapter 4 · Formulating a Research Problem
The formulation of research problems is a cornerstone of reflective thinking in scientific inquiry. This process transforms issues into clear questions, laying the groundwork for research and ...
One of the most important steps in the research process is formulating a research problem. It establishes the framework for the whole study and directs the researcher in determining the research's emphasis, scope, and goals. An effective research technique may be created with the support of a clearly defined research topic, which also aids in ...
Formulating a research problem is a challenging and very important task, sometimes quite difficult. An accurately and correctly formulated problem (research question) may significantly help in finding the solution (answer to the research question). On the other hand, the problem vagueness may lead to the collection of much useless data that do ...
Unit 3 and Unit 4 intend to describe the research process in detail. Formulation of research problem, the first step in the research process, is considered as the most important phase of a research project. This step starts with the selection of a suitable problem from the field chosen by the researcher.
Research is a procedure based on a sequence and a research problem aids in following and completing the research in a sequence. Repetition of existing literature is something that should be avoided in research. Therefore research problem in a dissertation or an essay needs to be well thought out and presented with a clear purpose.
A research problem has two essential roles in setting your research project on a course for success. 1. They set the scope. The research problem defines what problem or opportunity you're looking at and what your research goals are. It stops you from getting side-tracked or allowing the scope of research to creep off-course.
research and, if it is sufficiently compelling, can even sustain that support through the sometimes fruitless periods that researchers experience. However, despite research problems' logical priority in inquiry, and their importance as a priori justifications, a problem's formulation, as John Dewey stresses, is in fact a "progressive ...
The first and most important step of a research is formulation of research problems. It is like the foundation of a building to be constructed. To solve a problem someone has to know about the ...
Formulating a research problem is the first step of the research process. That's because this is the issue that will guide your entire research work. You can't solve an unknown problem. And solving a problem is the core aim of every research. Thus, a problem forms the basis of every study.
A research problem is a specific issue or gap in existing knowledge that you aim to address in your research. You may choose to look for practical problems aimed at contributing to change, or theoretical problems aimed at expanding knowledge. Some research will do both of these things, but usually the research problem focuses on one or the other.
Formulating a research problem is usually done under the first step of research process, i.e., defining the research problem. Identification, clarification and formulation of a research problem is done using different steps as: You have already studied why it is important to clarify a research question.
A research problem, refers to some difficulty which a researcher identifies in the context of either a theoretical or practical situation and wants to obtain a solution/explanation for the same. It is the demarcation of a problem within a certain context involving the WHO or WHAT, the WHERE, the WHEN and the WHY of a problem situation.
In this chapter, we introduced the research process and explained problem formulation. Distinguishing between symptoms and underlying problems is an essential step at the beginning of the research process. Without the distinction, there is a great risk of studying the wrong thing.
5. Select and include important variables. A clear and manageable research problem typically includes the variables that are most relevant to the study. A research team summarizes how they plan to consider and use these variables and how they might influence the results of the study. Selecting the most important variables can help the study's ...
Identification and formulation of research problem. How to identify a problem, different sources of research problem and how to delimit and formulate a resea...
In addition, a brief summary on, future research directions for potential challenges, problem formulation and proposed methodology based on machine learning approach for dynamic resource allocation, minimize collision and enhance performance of LoRaWAN for effective massive IoT deployment under secure environment, is discussed.
A graph is said to be two connected if between every pair of nodes there are at least two node-disjoint paths. Given weights on the edges of the graph, the two connected subgraph problem is to find a two connected spanning subgraph of G whose weight is minimum. This problem has many applications in telecommunications. In this paper we consider a new variant of this problem with additional ...
A mathematical formulation is constructed for the MD-CVRP-OSA, and an efficient metaheuristics algorithm based on a variable neighborhood search (VNS) solution framework is designed to solve it. ... and Section 5 concludes the paper and indicates future research directions. 2. Problem Description and Mathematical Formulation. The MD-CVRP-OSA ...