Discrete differential evolution algorithm for integer linear bilevel programming problems

A discrete differential evolution algorithm combined with the branch and bound method is developed to solve the integer linear bilevel programming problems, in which both upper level and lower level variables are forced to be integer. An integer coding for upper level variables is adopted, and then a discrete differential evolution algorithm with an improved feasibility-based comparison is developed to directly explore the integer solution at the upper level. For a given upper level integer variable, the lower level integer programming problem is solved by the existing branch and bound algorithm to obtain the optimal integer solution at the lower level. In the same framework of the algorithm, two other constraint handling methods, i.e. the penalty function method and the feasibility-based comparison method are also tested. The experimental results demonstrate that the discrete differential evolution algorithm with different constraint handling methods is effective in finding the global optimal integer solutions, but the improved constraint handling method performs better than two compared constraint handling methods.

Scenario-Based Stochastic Resource Allocation with Uncertain Probability Parameters

The stochastic resource allocation(SRA) problem is an extensive class of combinatorial optimization problems widely existing in complex systems such as communication networks and unmanned systems. In SRA, the ability of a resource to complete a task is described by certain probability,and the objective is to maximize the reward by appropriately assigning available resources to different tasks. This paper is aimed at an important branch of SRA, that is, stochastic SRA(SSRA) for which the probability for resources to complete tasks is also uncertain. Firstly, a general SSRA model with multiple independent uncertain parameters(GSSRA-MIUP) is built to formulate the problem. Then,a scenario-based reformulation which can address multi-source uncertainties is proposed to facilitate the problem-solving process. Secondly, in view of the superiority of the differential evolution algorithm in real-valued optimization, a discrete version of this algorithm was originally proposed and further combined with a specialized local search to create an efficient hybrid optimizer. The hybrid algorithm is compared with the discrete differential evolution algorithm, a pure random sampling method, as well as a restart local search method. Experimental results show that the proposed hybrid optimizer has obvious advantages in solving GSSRA-MIUP problems.