Intelligent test case generation based on branch and bound

Path-oriented test case generation is in essence a constraint satisfaction problem （CSP） solved by search strategies, among which backtracking algorithms are widely used. In this article, the backtracking algorithm branch and bound （BB） is introduced to generate path-oriented test cases automatically. A model based on state space search is proposed to construct the search tree dynamically. The BB is optimized from two perspectives. Variable permutation with a heuristic rule to break ties is adopted for the branching operation, and interval computation with analysis on the monotony of branching conditions is utilized for the bounding operation. Empirical experiments show that the proposed method performs well with linear complexity, and reaches 100% coverage on some benchmark programs with an advantage over some static and dynamic algorithms.

Extracting optimal actionable plans from additive tree models

Although amazing progress has been made in ma- chine learning to achieve high generalization accuracy and ef- ficiency, there is still very limited work on deriving meaning- ful decision-making actions from the resulting models. How- ever, in many applications such as advertisement, recommen- dation systems, social networks, customer relationship man- agement, and clinical prediction, the users need not only ac- curate prediction, but also suggestions on actions to achieve a desirable goal （e.g., high ads hit rates） or avert an unde- sirable predicted result （e.g., clinical deterioration）. Existing works for extracting such actionability are few and limited to simple models such as a decision tree. The dilemma is that those models with high accuracy are often more complex and harder to extract actionability from. In this paper, we propose an effective method to extract ac- tionable knowledge from additive tree models （ATMs）, one of the most widely used and best off-the-shelf classifiers. We rigorously formulate the optimal actionable planning （OAP） problem for a given ATM, which is to extract an action- able plan for a given input so that it can achieve a desirable output while maximizing the net profit. Based on a state space graph formulation, we first propose an optimal heuris- tic search method which intends to find an optimal solution. Then, we also present a sub-optimal heuristic search with an admissible and consistent heuristic function which can re- markably improve the efficiency of the algorithm. Our exper- imental results demonstrate the effectiveness and efficiency of the proposed algorithms on several real datasets in the application domain of personal credit and banking.