China
Africa
Explore chapters and articles related to this topic
Introduction to Linear Programming
Published in Timothy R. Anderson, Optimization Modeling Using R, 2023
Our model has the three core elements of an optimization model: variables, constraints, and an objective function. Let's go ahead and solve model0g. The LP can be solved using different LP engines – we'll use glpk for now. The results of the solved model will be assigned to result0. glpk is the R package name for the “GNU Linear Programming Kit”, which is intended for solving large-scale linear programming (LP), mixed integer programming (MIP), and other related problems.
Inner approximation algorithm for solving linear multiobjective optimization problems
Published in Optimization, 2021
GLPK implements the simplex method by maintaining a set of mbase variables, an invertible matrix M so that the product MA contains (the permutation of) a unit matrix at column positions corresponding to the base variables. Furthermore, for each non-base variable there is a flag indicating whether it takes its lower bound or upper bound . Fixing the value of non-base variables according to these flags, the value of base variables can be computed from the equation MAx = Mc. If the values of the computed base variables fall between the corresponding lower and upper bounds, then the arrangement (base, M, flags) is primal feasible.1
A scalable Bayesian framework for large-scale sensor-driven network anomaly detection
Published in IISE Transactions, 2023
In all of our numerical experiments, each network is subject to only one anomaly. This is because the GraphScan model was not originally designed to find multiple anomalous subgraphs or the cases where there is no anomaly in the network. We conducted experiments for each of the 36 combinations of parameter setup based on N, J, and β. For each experiment, we simulated 100 networks for testing. Due to page limits, we only focus on regular networks and three key performance measures of overlap coefficient, source detection accuracy, and CPU time. We used the Rglpk package, which is a GNU solver based on an open source software GLPK developed for solving large-scale linear programming and mixed-integer linear programming. Our discussion below remains the same for other types of networks and performance measures. Results summarized in Figure 7 of the Supplemental Material verify that although the optimization-based models, perform the best in terms of detecting anomalies, our model performs very close to those models, particularly for larger values of sensor attributes and more powerful sensors. The binary classification model’s performance is the worst, as it does not incorporate the topological dependencies between the nodes. The biggest gaps between our model and the optimal values are when the number of sensor attributes is one. We believe the gap can potentially become smaller by modifying the stopping criterion of the sampler and fine-tuning the initialization hyperparameter. To better understand the key benefit of our model compared with the benchmark models, we calculated the average CPU time per network for the task of anomaly detection as shown in Table 4. Since the results did not vary too much over different scenarios of sensor properties, results are averaged over the four cases of It can be seen from the table that the binary classification model is the fastest, however, it cannot provide reasonable results at all. Our model is still very fast even for the network of size 20,000 nodes. Although the optimization-based models provide the best detection results, their long CPU times make them not scalable for larger networks and thus not always feasible in practice. About half of the CPU time for the optimization models is just to form the corresponding optimization models, which can potentially improve by forming them offline and using more advanced optimization solvers. However, even after that, the CPU time remains unreasonable for large networks. In addition to the above comparison, we should point out that our model outperforms these benchmark models from the following aspects: our model can be used to detect both normal networks (with no anomalous nodes) or networks with multiple anomalies. Also, due to the Bayesian nature of the proposed approach, the uncertainty of detection results can be utilized to provide more informed insights.