Solving the Binary Linear Programming Model in Polynomial Time

The paper presents a technique for solving the binary linear programming model in polynomial time. The general binary linear programming problem is transformed into a convex quadratic programming problem. The convex quadratic programming problem is then solved by interior point algorithms. This settles one of the open problems of whether P = NP or not. The worst case complexity of interior point algorithms for the convex quadratic problem is polynomial. It can also be shown that every liner integer problem can be converted into binary linear problem.

SHFuzz:A Hybrid Fuzzing Method Assisted by Static Analysis for Binary Programs

Fuzzing is an effective technique to find security bugs in programs by quickly exploring the input space of programs.To further discover vulnerabilities hidden in deep execution paths,the hybrid fuzzing combines fuzzing and concolic execution for going through complex branch conditions.In general,we observe that the execution path which comes across more and complex basic blocks may have a higher chance of containing a security bug.Based on this observation,we propose a hybrid fuzzing method assisted by static analysis for binary programs.The basic idea of our method is to prioritize seed inputs according to the complexity of their associated execution paths.For this purpose,we utilize static analysis to evaluate the complexity of each basic block and employ the hardware trace mechanism to dynamically extract the execution path for calculating the seed inputs’weights.The key advantage of our method is that our system can test binary programs efficiently by using the hardware trace and hybrid fuzzing.To evaluate the effectiveness of our method,we design and implement a prototype system,namely SHFuzz.The evaluation results show SHFuzz discovers more unique crashes on several real-world applications and the LAVA-M dataset when compared to the previous solutions.

Toward Optimal Periodic Crowd Tracking via Unmanned Aerial Vehicle

Crowd management and analysis(CMA)systems have gained a lot of interest in the vulgarization of unmanned aerial vehicles(UAVs)use.Crowd tracking using UAVs is among the most important services provided by a CMA.In this paper,we studied the periodic crowd-tracking(PCT)problem.It consists in usingUAVs to follow-up crowds,during the life-cycle of an open crowded area(OCA).Two criteria were considered for this purpose.The first is related to the CMA initial investment,while the second is to guarantee the quality of service(QoS).The existing works focus on very specified assumptions that are highly committed to CMAs applications context.This study outlined a new binary linear programming(BLP)model to optimally solve the PCT motivated by a real-world application study taking into consideration the high level of abstraction.To closely approach different real-world contexts,we carefully defined and investigated a set of parameters related to the OCA characteristics,behaviors,and theCMAinitial infrastructure investment(e.g.,UAVs,charging stations(CSs)).In order to periodically update theUAVs/crowds andUAVs/CSs assignments,the proposed BLP was integrated into a linear algorithm called PCTs solver.Our main objective was to study the PCT problem fromboth theoretical and numerical viewpoints.To prove the PCTs solver effectiveness,we generated a diversified set of PCTs instances with different scenarios for simulation purposes.The empirical results analysis enabled us to validate the BLPmodel and the PCTs solver,and to point out a set of new challenges for future research directions.

Component reallocation and system replacement maintenance based on availability and cost in series systems

Component reallocation(CR)is receiving increasing attention in many engineering systems with functionally interchangeable and unbalanced degradation components.This paper studies a CR and system replacement maintenance policy of series repairable systems,which undergoes minimal repairs for each emergency failure of components,and considers constant downtime and cost of minimal repair,CR and system replacement.Two binary mixed integer nonlinear programming models are respectively established to determine the assignment of CR,and the uptime right before CR and system replacement with the objective of minimizing the system average maintenance cost and maximizing the system availability.Further,we derive the optimal uptime right before system replacement with maximization of the system availability,and then give the relationship between the system availability and the component failure rate.Finally,numerical examples show that the CR and system replacement maintenance policy can effectively reduce the system average maintenance cost and improve the system availability,and further give the sensitivity analysis and insights of the CR and system replacement maintenance policy.

Design of Resilient Sensor Networks Balancing Resilience and Efficiency

In recent years,the notion of resilience has been developed and applied in many technical areas,becoming exceptionally pertinent to disaster risk science.During a disaster situation,accurate sensing information is the key to efficient recovery efforts.In general,resilience aims to minimize the impact of disruptions to systems through the fast recovery of critical functionality,but resilient design may require redundancy and could increase costs.In this article,we describe a method based on binary linear programming for sensor network design balancing efficiency with resilience.The application of the developed framework is demonstrated for the case of interior building surveillance utilizing infrared sensors in both twoand three-dimensional spaces.The method provides optimal sensor placement,taking into account critical functionality and a desired level of resilience and considering sensor type and availability.The problem formulation,resilience requirements,and application of the optimization algorithm are described in detail.Analysis of sensor locations with and without resilience requirements shows that resilient configuration requires redundancy in number of sensors and their intelligent placement.Both tasks are successfully solved by the described method,which can be applied to strengthen the resilience of sensor networks by design.The proposed methodology is suitable for large-scale optimization problems with many sensors and extensive coverage areas.

Binary Particle Swarm Optimization Based Hyper-Heuristic for Solving the Set-Union Knapsack Problem

The set-union knapsack problem(SUKP)is proved to be a strongly NP-hard problem,and it is an extension of the classic NP-hard problem:the 0-1 knapsack problem(KP).Solving the SUKP through exact approaches is computationally expensive.Therefore,several swarm intelligent algorithms have been proposed in order to solve the SUKP.Hyper-heuristics have received notable attention by researchers in recent years,and they are successfully applied to solve the combinatorial optimization problems.In this article,we propose a binary particle swarm optimization(BPSO)based hyper-heuristic for solving the SUKP,in which the BPSO is employed as a search methodology.The proposed approach has been evaluated on three sets of SUKP instances.The results are compared with 6 approaches:BABC,EMS,gPSO,DHJaya,b WSA,and HBPSO/TS,and demonstrate that the proposed approach for the SUKP outperforms other approaches.

Bin2vec:learning representations of binary executable programs for security tasks

Tackling binary program analysis problems has traditionally implied manually defining rules and heuristics,a tedious and time consuming task for human analysts.In order to improve automation and scalability,we propose an alternative direction based on distributed representations of binary programs with applicability to a number of downstream tasks.We introduce Bin2vec,a new approach leveraging Graph Convolutional Networks(GCN)along with computational program graphs in order to learn a high dimensional representation of binary executable programs.We demonstrate the versatility of this approach by using our representations to solve two semantically different binary analysis tasks–functional algorithm classification and vulnerability discovery.We compare the proposed approach to our own strong baseline as well as published results,and demonstrate improvement over state-of-the-art methods for both tasks.We evaluated Bin2vec on 49191 binaries for the functional algorithm classification task,and on 30 different CWE-IDs including at least 100 CVE entries each for the vulnerability discovery task.We set a new state-of-the-art result by reducing the classification error by 40%compared to the source-code based inst2vec approach,while working on binary code.For almost every vulnerability class in our dataset,our prediction accuracy is over 80%(and over 90%in multiple classes).

A novel technique for the optimal design of offshore wind farm electrical layout

The design of electrical layout is a key element in the offshore wind farm planning.We present a novel electrical layout design optimization method for offshore wind farms in this paper.The proposed method can be used to generate the network model based on fuzzy c-means(FCM)and binary integer programming(BIP)methods.It can automatically allocate wind turbines to the nearest substations and obtain the topology structure of cables utilized to connect wind turbines or turbine and substation.The objective of this optimization is to minimize the investment costs of cable connection and the transmission power losses.The results of case study clearly demonstrated the feasibility of the proposed method and showed that it can be used as a reliable tool for electrical layout design of offshore wind farms.

Approximation Algorithms for Discrete Polynomial Optimization

In this paper,we consider approximation algorithms for optimizing a generic multivariate polynomial function in discrete(typically binary)variables.Such models have natural applications in graph theory,neural networks,error-correcting codes,among many others.In particular,we focus on three types of optimization models:(1)maximizing a homogeneous polynomial function in binary variables;(2)maximizing a homogeneous polynomial function in binary variables,mixed with variables under spherical constraints;(3)maximizing an inhomogeneous polynomial function in binary variables.We propose polynomial-time randomized approximation algorithms for such polynomial optimizationmodels,and establish the approximation ratios(or relative approximation ratios whenever appropriate)for the proposed algorithms.Some examples of applications for these models and algorithms are discussed as well.

Weak bus-constrained PMU placement for complete observability of a connected power network considering voltage stability indices

Phasor measurement units(PMUs)are preferred for installation at weak buses in a power network.Therefore,the weak buses need to be located and the strategic locations of PMUs identified to ensure network observability.Thus,the primary aim of this work is to identify the placements of the maximum number of PMUs installed at the weak buses in the electrical network.The voltage collapse proximity indicator,line stability index,fast voltage stability index,and a new voltage stability indicator utilizing load flow measurement are used to determine the weak buses.A novel deterministic methodology based on a binary-integer linear programming model is then proposed to determine the optimal locations of PMUs.The effect of a single PMU outage considering the weak buses is also demonstrated.The effectiveness of the developed approach is tested and validated on the standard IEEE 14-,118-,300-,and New England 39-bus systems.The obtained results are also compared to those using different weak bus methodologies.