NODE-BASED SEQUENTIAL IMPLICIT ENUMERATION METHOD AND SYSTEM THEREOF

摘要

A node-based sequential implicit enumeration method is provided, including: setting a multistate flow network, building an integer programming model of the multistate flow network, and finding a solution set of level number 1 and a number of elements in the solution set from the integer programming model according to the flow conservation law, then using one of the elements to sequentially find a solution set of a next level number and a number of elements in the solution set until the level number being N−1 to complete a new complete solution set, afterward, sequentially returning to the preceding level numbers to determine whether there are other elements in the solution set, and if so, repeating above steps to produce another new complete solution set until the solution sets of all level numbers have been checked, and determining the final complete solution set as a set of the minimal path satisfying the required flow, so as to find all d-MP in the integer programming model of the multistate flow network efficiently.

主权项

1. A node-based sequential implicit enumeration system, comprising:
a presetting module for setting a multistate flow network including N nodes and required flow; a building module for building an integer programming model of the multistate flow network, so as to set a complete solution set of the integer programming model as an empty set and set a level number as 1 in advance; and a computing module for obtaining a complete solution set of a minimal path satisfying the required flow, the computing module comprising:
a solution set unit that finds solution sets of each node in the integer programming model according to a flow conservation rule and excludes unsuitable ones, so as to find a number of elements in each of the solution sets;a recurring unit that adds 1 to the level number when the level number is determined being less than N−1, so as to use one of the elements in the solution set to sequentially find a solution set of a next level number and a number of elements in the solution set of the next level number through the solution set unit until the level number is equal to N−1; anda unifying unit that unifies the complete solution set and the solution set of the level number N−1, so as to generate a new complete solution set;wherein after the solution set of a level number N−1 is obtained, when the level number is larger than 1, the recurring unit subtracts 1 from the level number to determine whether other elements exist in the solution set of the level number, and if so, repeating procedures of the solution set unit, the recurring unit and the unifying unit to produce another new complete solution set, otherwise 1 is continuously subtracted from the level number until the level number is 1, such that a set of minimal path satisfying the required flow is obtained as a final complete solution set.