Application of the 0-1 Programming Model for Cost-Effective Regression TestHirohisa Aman
Graduate School of Science and Engineering,
Ehime UniversityMatsuyama, Japan
Email: aman@cs.ehime-u.ac.jp

Manami Sasaki, Kei Kureishi and Hideto Ogasawara
Corporate Software Engineering Center,Toshiba CorporationKawasaki, Japan
Email: {manami.sasaki, kei.kureishi, hideto.ogasawara}@toshiba.co.jp

Abstract—This paper reports an application of the 0-1
programming model to the regression testing plan for anindustrial software. The key idea is to formulate a testingplan as a 0-1 programming problem (Knapsack problem).
The empirical study shows that the 0-1 programming method
can produce a cost-effective testing plan in which all potential
regressions are found at only 22% of the cost of running all
test cases.
Keywords-testing; regression; 0-1 programming model; costeffectiveness

I. I NTRODUCTION
System testing—testing behaviors of software—is a crucial activity to develop high-quality software. Any bugs
overlooked during system testing may cause failures in theoperational phase. Test engineers usually prepare many test
cases to check various functions and conditions.
During system testing, many minor upgrades to fix bugs
may appear. Then, test engineers should run test cases again
to check whether they have regressions (bugs) or not, i.e.,regression testing [1]. While it is ideal to run all test cases
again for each minor upgrade, such a thorough regression
test would be difficult due to realistic limitations such as lackof time and/or manpower. Thus, test engineers have to plana cost-effective regression test under realistic limitations.
Test engineers often assign some values (worth to betested) to their test cases in order to prioritize them. Then,
those test cases can be selected in descending order of worth.
Such a strategy is called the “greedy method” in the fieldof algorithm theory. While the greedy method is simple andeasy-to-perform, it cannot consider testing costs properly.
To take into account both the testing worth and the testing
cost, Aman [2] proposed to formulate such a testing plan
as a 0-1 programming problem (Knapsack problem [3]).
The contribution of this paper is to report the applicationof Aman’s method to industrial software.
II. H ISTORY-BASED W ORTH TO RUN R EGRESSION T EST
A. Test History Data
In a system testing for a software, we suppose that wehave N test cases Ti (for i = 1, . . . , N ) and M versions Vj(for j = 1, . . . , M ) to be tested. Then, let r(i, j) to be thetest result of running Ti for version Vj :⎧(failure),⎨ 0
1(success),r(i, j) =⎩NA (non-running).
These results can form a N × M matrix R = ( r(i, j) ),and the matrix is our test history data. It is ideal that allelements of the matrix are either 0 or 1; that is to say, alltest cases were executed for all versions. In reality, however,some tests are omitted (r(i, j) = NA) if their tests alreadypassed in the previous version, e.g., r(i, j − 1) = 1.
B. Worth to Run Regression Test
The test history of Ti is given as the i-th row of R:r(i, 1), r(i, 2), . . . , r(i, M ) .
Using the above history data, we will evaluate the worth torun Ti again (perform the regression test).
Now we will focus on consecutive NAs in the test history,
and we will consider that a test case having a long series ofNAs as needing to be tested again. We define Ti ’s worth tobe run again (to perform the regression test) as follows:
Suppose that Ti was run at version Vk , but it had neverbeen executed after that version, i.e., r(i, j) = NA (forj = k + 1, . . . , M ), so there are “M − k” consecutive NAs
until the latest version. Then, define Ti ’s worth to run theregression test, wi , aswi = M − k .
2The test case Ti with larger wi would have a higher riskof overlooking regressions because it has not been run for alonger time.
Table I shows an example of R with N = 3 and M = 5.
In the table, we obtain w1 = 2, w2 = 3 and w3 = 0. T1 andT2 have not been run since V4 and V3 , respectively. That is
to say, there are some possibilities of potential regressions
in the latest version. T3 has little or no worth to run again in
the latest version because it was just run in the same version.

Table I
S IMPLE EXAMPLE OF R, WHERE N = 3, M = 5.

T1
T2
T3

V1

V2V3V4V5NA100111NANANANA0NANA1

III. 0-1 P ROGRAMMING M ODELWe have introduced the notion of worth to run regression
tests in the previous section. Using such worth, we canselect test cases in descending order; such a scheme isreferred to as the “greedy method.” While the greedy method
is simple and easy-to-perform, it would not produce theoptimal solution when the available time or effort is limited.
To consider not only the testing worth but also the testing
cost, Aman [2] proposed to formulate the testing plan as the0-1 programming problem as follows:Nwi · xi ,maximize
i=1

subject toandNi=1

ci · xi ≤ L,xi ≤ xj

xi ∈ {0, 1},

if Ti requires to run Tj ,where ci is the cost needed to run Ti , and xi is the 0-1
variable showing whether we run Ti or not; xi = 1 if werun it, otherwise xi = 0. L denotes our upper limit of total
cost available for our regression testing.
2The above inequality xi ≤ xj represents a causal connection between Ti and Tj . Whenever Ti is selected to berun, Tj is also selected since xi = 1 and xi ≤ xj imply
xj = 1. Test engineers can make any causal connections
depending on their situation. The authors have empiricallyused the following co-occurrence relation to make such acausal connection: whenever Ti is run, Tj is also run, weconsider that Ti requires running Tj . For example, T3 isalways run when T2 is run in Table I, so we have x2 ≤ x3
as one of our constraints.
The key contribution of the 0-1 programming model is totake into account “testing costs” reasonably. Such a notionof cost can always be crucial matter in the development ofindustry software.
IV. E MPIRICAL S TUDY
To evaluate the effectiveness of the above 0-1 model, we
conducted an empirical study with a software system which
has been developed and maintained by the authors’ company.
Using 300(= N ) test cases, we tested 13(= M ) versionsof the software during system testing. Now we consider thetest cost to be the testing time (the unit is minute), andconducted the following comparison experiment:

Table IIN UMBER OF REGRESSIONS FOUND IN EMPIRICAL WORK .
methodgreedy
0-1 modelL
1h (60min)
2h (120min)
3h (180min)

8
14
14

16
2222

Method to select test cases:
1) greedy method1,
2) 0-1 programming method (0-1 model).
• Cost Limit (L):1) 1 hour (60 min),2) 2 hours (120 min),3) 3 hours (180 min).
•2
Table II shows the number of regressions found by running the selected test cases. For all L, the 0-1 model could
find more regressions than the greedy method. Therefore, the0-1 model would be more useful in planning cost-effective
regression tests.
In order to discuss the efficiency of the above methods,
we also performed all 300 test cases in 554 minutes. As aresult, 22 regressions were found. Thus, the 0-1 model could
find all regressions in only two hours, which corresponds toabout 22% of total costs needed to run all test cases2 . While
the greedy method is a simple and effective method, the 0-1
model seems to be much more effective.
V. C ONCLUSION
This paper reported an application of 0-1 model to theregression testing plan for an industrial software. The 01 model could produce a more cost-effective testing plan
than the conventional greedy method, and could find all
regressions at only 22% of the costs to run all test cases
again. Our future work includes further data collectionand experiments for comparing the 0-1 model with otherintelligent methods (not only greedy one).
R EFERENCES[1] J. Richardson and W. Gwaltney, Jr., Ship It!: A Practical Guideto Successful Software Projects, Pragmatic Bookshelf: O’Reilly
Media, CA, 2005.
[2] H. Aman, Planning of Priority Review using 0-1 Programming
Model with Logical Constraints, Computer Software, vol.29,no.3, pp.115–120, Iwanami Shoten, Tokyo, 2012 (in Japanese).
[3] M.R. Garey and D.S. Johnson, Computers and Intractability:
A Guide to the Theory of Np-Completeness, W.H.Freeman andCompany, NY, 1979.
1 The co-occurrence relation is considered as well. That is to say, if Tirequires running Tj , then both Ti and Tj are selected whenever Ti isselected.
2 120/554  0.22