X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/ThesisAli.git/blobdiff_plain/c4dbe9342864e9fb1a9d2de25bc652d2ba194b54..5b873620b230517c1592c89c4c8dd5dba2818339:/CHAPITRE_03.tex?ds=inline diff --git a/CHAPITRE_03.tex b/CHAPITRE_03.tex index 25a2405..8d7ebc2 100644 --- a/CHAPITRE_03.tex +++ b/CHAPITRE_03.tex @@ -20,7 +20,8 @@ For this reason, several problems are modeled by an optimization problem for ins %Therefore, in order to get the optimal solutions for these mathematical optimization problems, the optimization solver is the best candidate tool to solve them. The optimization solver takes mathematical optimization problem descriptions in a certain file format and calculates their optimal solution. Optimization solvers dedicated to specific resolution methods (meta-heuristics, linear programming, etc) are required. %Many important real-world problems have formulated as integer programming problems. -In this dissertation, we use linear programming because we used integer programs to optimize the coverage and the lifetime in WSNs. +%In this dissertation, we use linear programming because we used integer programs to optimize the coverage and the lifetime in WSNs. +In this dissertation, we optimize the coverage and the lifetime in WSNs and the problem is formulated through linear programming. These kind of models allow to obtain optimal solutions satisfying an objective (for instance, maximize coverage) under constraints (for instance, available remaining energy). The remainder of this chapter is organized as follows. The next section is devoted to the evaluation tools for evaluating and validating the performance of proposed algorithms and protocols. Section \ref{ch3:3} gives the most popular free and commercial linear optimization solvers to solve the linear programming problems. Finally, we give concluding remarks in section \ref{ch3:4}. @@ -256,12 +257,12 @@ lp$\textunderscore$solve~\cite{ref215,ref213} is a free linear (integer) program \item \textbf{CLP:} -The COIN-OR Linear Programming (CLP)~\cite{ref216,ref217} is a free, open-source, linear programming solver written in C++ programming language. It is reliable and able to tackle the very large linear optimization problems. The CLP is a part of the Coin-OR project that aims at creating open software for the operations research community. COIN-OR projects such as SYMPHONY, BCP (Branch Cut and Price), and CBC (COIN-OR Branch and Cut) also used CLP. It includes Dual and Primal Simplex algorithms, but it also contains an Interior Point algorithm. The CLP is available under the Eclipse Public License version 1.0, and the users interact with it through either an interactive command line or through a C++ API. The CLP is able to use the input MPS, Free MPS, and LP file formats. +The COIN-OR Linear Programming (CLP)~\cite{ref216,ref217} is a free, open-source, linear programming solver written in C++ programming language. It is reliable and able to tackle the very large linear optimization problems. The CLP is a part of the Coin-OR project that aims at creating open software for the operations research community. COIN-OR projects such as SYMPHONY, BCP (Branch Cut and Price), and CBC (COIN-OR Branch and Cut) also uses CLP. It includes Dual and Primal Simplex algorithms, but it also contains an Interior Point algorithm. The CLP is available under the Eclipse Public License version 1.0, and the users interact with it through either an interactive command line or through a C++ API. The CLP is able to use the input MPS, Free MPS, and LP file formats. \item \textbf{CPLEX:} -The IBM ILOG CPLEX Optimization Studio (often informally referred to simply as CPLEX)~\cite{ref218,ref211} is a commercial, analytical decision support, and optimization software toolkit for fast development of optimization models using mathematical and constraint programming. It combines an integrated development environment (IDE) with the powerful Optimization Programming Language (OPL) and high-performance ILOG CPLEX optimizer solvers. The CPLEX is developed by IBM and is designed to tackle the large-scale (mixed integer) linear problems. The CPLEX optimizer includes a modeling layer called "Concert" that provides interfaces to the C++, C$\#$, Python, and Java languages. Furthermore, it provides a connection to Microsoft Excel and MATLAB. The CPLEX is capable of optimizing the business decisions with high-performance optimization engines. It develops and deploys optimization models quickly by using flexible interfaces and pre-constructed deployment scenarios. In addition, it creates real-world applications. +The IBM ILOG CPLEX Optimization Studio (often informally referred to simply as CPLEX)~\cite{ref218,ref211} is a commercial, analytical decision support, and optimization software toolkit for fast development of optimization models using mathematical and constraint programming. It combines an integrated development environment (IDE) with the powerful Optimization Programming Language (OPL) and high-performance ILOG CPLEX optimizer solvers. The CPLEX is developed by IBM and is designed to tackle the large-scale (mixed integer) linear problems. The CPLEX optimizer includes a modeling layer called "Concert" that provides interfaces to the C++, C$\#$, Python, and Java languages. Furthermore, it provides a connection to Microsoft Excel and MATLAB. The CPLEX is capable of optimizing the business decisions with high-performance optimization engines. It develops and deploys optimization models quickly by using flexible interfaces and pre-constructed deployment scenarios. %In addition, it creates real-world applications. \item \textbf{Gurobi:} @@ -274,7 +275,7 @@ The Gurobi Optimizer~\cite{ref219,ref220,ref211} is a commercial optimization so B. Meindl and M. Templ~\cite{ref212} studied the efficiency of above optimization solvers. They used a set of instances of difficult optimization problems called the attacker problems in order to achieve a performance comparison of GLPK, lp$\_$solve, CLP, GUROBI, and CPLEX optimization solvers. They considered a total of 200 problem instances for this study, 100 of these problem instances are based on problems with two dimensions, and 100 problem instances are three-dimensional. -In tables~\ref{my-label1}, \ref{my-label2}, and \ref{my-label3} we report the result of their comparison the running times of the five linear program solvers to find solutions to the 200 two-dimensional, 200 three-dimensional, and all 400 problem instances. In order to solve the attacker’s problem for a given problem instance, it is needed to both minimize and maximize any given problem. Therefore, a total of 400 problem instances had been solved when only 200 problem instances have been generated. The running time of the fastest solver has been scaled to one and the running times of the other linear solvers were scaled to reflect this scaling. +In tables~\ref{my-label1}, \ref{my-label2}, and \ref{my-label3} we report the result of their comparisons the running times of the five linear program solvers to find solutions to the 200 two-dimensional, 200 three-dimensional, and all 400 problem instances. In order to solve the attacker’s problem for a given problem instance, it is needed to both minimize and maximize any given problem. Therefore, a total of 400 problem instances had been solved when only 200 problem instances have been generated. The running time of the fastest solver has been scaled to one and the running times of the other linear solvers were scaled to reflect this scaling. \begin{table}[h] @@ -329,11 +330,11 @@ The results in tables~\ref{my-label1}, \ref{my-label2}, and \ref{my-label3} indi \item The GLPK comes with a stand-alone solver, a callable library, and the modeling language GMPL. The GMPL is compatible with AMPL and is extremely easy to learn. \item Modeling language and solver can be used independently. \item GUI is available for Windows, Mac OS X, and Linux. Java, Python, and Matlab interfaces are available. -\item Database support and formatted text output. -\item Exact simplex algorithm and branch-and-bound method are integrated with GLPK. +%\item Database support and formatted text output. +%\item Exact simplex algorithm and branch-and-bound method are integrated with GLPK. \end{enumerate} \section{Conclusion} \label{ch3:4} -\indent In this chapter, an overview of the evaluation tools for wireless sensor networks and optimization solvers has been presented. Major testbeds for wireless sensor network have been demonstrated. We have found that most researchers in the field of WSNs use the simulators to evaluate theirs works because they are free, easy to use, more flexible, and scalable for large WSNs. Several simulators for wireless sensor networks are described. The comparison among some types of network simulators show that OMNeT++ simulator is a good candidate to be used as performance evaluation tool to evaluate the efficiency of our protocols in this dissertation. This chapter also highlightes the optimization problem in WSNs and the most popular free and commercial linear optimization solvers. The commercial optimization solvers outperform the free optimization solvers. GLPK has been chosen as a good candidate to solve the proposed optimization problems in this dissertation because it is free, easy to use, and better than some other free optimization solvers. \ No newline at end of file +\indent In this chapter, an overview of the evaluation tools for wireless sensor networks and optimization solvers has been presented. Major testbeds for wireless sensor network have been demonstrated. We have found that most researchers in the field of WSNs use the simulators to evaluate theirs works because they are free, easy to use, more flexible, and scalable for large WSNs. Several simulators for wireless sensor networks are described. The comparison among some types of network simulators show that OMNeT++ simulator is a good candidate to be used as performance evaluation tool to evaluate the efficiency of our protocols in this dissertation. This chapter also highlights the optimization problem in WSNs and the most popular free and commercial linear optimization solvers. The commercial optimization solvers outperform the free optimization solvers. GLPK has been chosen as a good candidate to solve the proposed optimization problems in this dissertation because it is free, easy to use, and better than some other free optimization solvers. \ No newline at end of file