Nonconvex quadratically constrained programs (QCPs) are generally NP-hard and challenging problems. In this paper, we propose two novel mixed-integer linear programming (MILP) approximations for a nonconvex QCP. Our method begins by utilizing an eigenvalue-based decomposition to express the nonconvex quadratic function as the difference of two convex functions. We then introduce an additional variable to partition each nonconvex constraint into a second-order cone (SOC) constraint and the complement of an SOC constraint. We employ two polyhedral approximation approaches to approximate the SOC constraint. The complement of an SOC constraint is approximated using a combination of linear and complementarity constraints. As a result, we approximate the nonconvex QCP with two linear programs with complementarity constraints (LPCCs). More importantly, we prove that the optimal values of the LPCCs asymptotically converge to that of the original nonconvex QCP. By proving the boundedness of the LPCCs, we further reformulate the LPCCs as MILPs. We demonstrate the effectiveness of our approaches via numerical experiments by applying our proposed approximations to randomly generated instances and two application problems: the joint decision and estimation problem and the two-trust-region subproblem. The numerical results show significant advantages of our approaches in terms of solution quality and computational time compared with existing benchmark approaches. History: Accepted by Pascal Van Hentenryck, Area Editor for Computational Modeling: Methods & Analysis. Funding: K. Pan was supported in part by the Research Grants Council of Hong Kong [Grant 15503723]. J. Cheng and B. Yang were supported in part by the Office of Naval Research [Grant N00014-20-1-2154]. J. Cheng was supported in part by the National Science Foundation [Grant ECCS-2404412]. B. Yang was supported in part by the Air Force Office of Scientific Research [Grant FA9550-23-1-0508]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2024.0719 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2024.0719 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

Recently, Multi-Contrast MR Reconstruction (MCMR) has emerged as a hot research topic that leverages high-quality auxiliary modalities to reconstruct undersampled target modalities of interest. However, existing methods often struggle to generalize across different k-space undersampling patterns, requiring the training of a separate model for each specific pattern, which limits their practical applicability. To address this challenge, we propose UniFS, a Unified Frequency-Spatial Fusion model designed to handle multiple k-space undersampling patterns for MCMR tasks without any need for retraining. UniFS integrates three key modules: a Cross-Modal Frequency Fusion module, an Adaptive Mask-Based Prompt Learning module, and a Dual-Branch Complementary Refinement module. These modules work together to extract domain-invariant features from diverse k-space undersampling patterns while dynamically adapt to their own variations. Another limitation of existing MCMR methods is their tendency to focus solely on spatial information while neglect frequency characteristics, or extract only shallow frequency features, thus failing to fully leverage complementary cross-modal frequency information. To relieve this issue, UniFS introduces an adaptive prompt-guided frequency fusion module for k-space learning, significantly enhancing the model's generalization performance. We evaluate our model on the BraTS and HCP datasets with various k-space undersampling patterns and acceleration factors, including previously unseen patterns, to comprehensively assess UniFS's generalizability. Experimental results across multiple scenarios demonstrate that UniFS achieves state-of-the-art performance. Our code is available at https://github.com/LIKP0/UniFS.

With the growing number of patients experiencing knee-related conditions, total knee arthroplasty (TKA) has become a common procedure, where a 3D visualisation of the patient’s tibia and fibula is essential for preoperative planning. Traditional imaging techniques, such as computed tomography (CT), often expose patients to high levels of radiation or impose significant financial costs. As an alternative, this paper proposes a novel approach that reconstructs a 3D model of the tibia and fibula using only two X-ray images (taken from the coronal and sagittal planes) and a general template, significantly reducing radiation exposure and financial burden. Our algorithm of 3D reconstruction for patient-specific anatomies combines point-based deformation with deep learning techniques. Initially, the general model undergoes a preliminary deformation to match the patient tibia and fibula dimensions. This pre-deformed model then serves as a template, followed by a fine deformation process via a self-supervised graph convolutional network (GCN), whose parameters are trained iteratively by comparing the template projection and the X-ray measurements. Following tests in simulations, cadaver experiments, and in-vivo experiments, our proposed algorithm demonstrates state-of-the-art accuracy and exceptional robustness across different evaluation metrics. Our code is available at https://github.com/DrKaiPan/tfDeform_GCN.git

A solar power plant provides green electricity to the public via a power grid. As governments worldwide have pledged to reduce carbon emissions and achieve carbon neutrality, large-scale grid-connected solar power plants are booming. Developing such a plant requires significant investment, a large proportion of which covers construction costs. Such costs, together with the energy yield, critically depend on the plant’s layout. The layout planning of a solar power plant involves a series of complex optimization problems such as district partitioning, photovoltaic (PV) component location, and cable routing problems in a solar power plant. These problems have received limited attention in the literature and are highly challenging because they involve large-scale instances, complex design principles, and complicated physical constraints. Motivated by our collaborative projects with an electrical engineering company in China, this paper specifically focuses on the integrated location and routing (ILR) problem, which involves locating service ways, inverters, combiner boxes, and routing cables to connect them. We develop exact algorithms to effectively solve the ILR problem via a decomposition framework (leading to a variant of Benders decomposition (BD)), which is proven to produce an optimal solution. We also develop an exact branch-and-cut scheme to solve each subproblem in the decomposition framework by incorporating cutting planes and separation algorithms. Our solution approach is evaluated on 50 real-world data instances via extensive numerical experiments. Compared with the manual method based on greedy heuristics used in practice, our approach reduces the total cost by approximately 20%. Our decomposition method also achieves an average gap of 0.02% between the obtained lower and upper bounds, significantly smaller than the 16.08% gap achieved with the traditional BD. History: Accepted by David Alderson, Area Editor for Network Optimization: Algorithms & Applications. Funding: This work was partially supported by the Research Grants Council of Hong Kong [Grant 15501221], the National Natural Science Foundation Program of China [Grants 72122006, 72471100, and 72131008], Huazhong University of Science and Technology Double First-Class Funds for Humanities and Social Sciences (Digital Intelligence Decision Optimization Innovation Team), the Interdisciplinary Research Program of HUST [Grant 5003300129], and the Fundamental Research Funds for the Central Universities [Grant 2023WKFZZX101]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2023.0223 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2023.0223 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

Due to time and cost limitations, Magnetic Resonance (MR) imaging often employs anisotropic scanning with large slice spacing and thickness. This causes blurring in views perpendicular to the slices, which adversely affects clinical diagnosis and research. Taking into account the complementary information from the reference modality, deep learning (DL) based multi-contrast methods have become a focal point of research. These methods aim to reconstruct the isotropic target MR image with the auxiliary high-resolution (HR) reference modality. However, most of the methods primarily concentrate on the structural restoration of the target low-resolution (LR) image, neglecting the crucial aspect that the coexisting structural and modality differences between target and reference modalities can impede effective restoration. Additionally, these methods are designed for a fixed upsampling scale, not accounting for the practical scenario of varying slice thickness. In this work, we propose a joint Super-resolution and Modality translation network (SMNet) for multi-contrast arbitrary-scale isotropic MRI reconstruction. The modality translation branch includes the Modality-Specific-Augmented Alignment (MSAA) block, which eliminates modality distribution disparities and enhances modality-specific regions on the reference feature before fusion. And the super-resolution branch employs the Reliability-based Spatial Fusion (RSF) block for the structural restoration of the target LR feature using a reliability prior. The outputs from these two branches are then ensembled to obtain the final reconstructed result. Extensive experiments on both a private dataset and the Brasts2021 dataset demonstrate the effectiveness and generalizability of the proposed method. Our code is available at https://github.com/11710615/smnet.

Security-constrained unit commitment (SCUC) is one of the most fundamental optimization problems in power systems. The objective of SCUC is to minimize the operating cost while respecting both system-wide and generator-specific constraints. It leads to a large-scale and mixed-integer programming (MIP) model with a large number of binary decision variables which is difficult to solve. This paper, based on the convex hull theory of single-unit, proposes a linearization method for the hydro-thermal SCUC problem with decoupled thermal units and variable-head hydro units. Then, the strategy of embedding two types of convex hulls in a multi-unit commitment and the heuristic method of constructing a feasible solution are designed, by which the multi-UC is approximated from large-scale mixed-integer programming to linear programming that can be solved in polynomial time. Finally, we theoretically prove that the optimal solution of the proposed LP model is always better than that of the Lagrangian Relaxation model. Numerical experiments on several large-scale test systems demonstrate the effectiveness and efficiency of the proposed method. Note to Practitioners— This paper proposes a linear programming model for the SCUC problem by lifting up to a higher-dimensional space. It realizes an important innovation in reducing the computational complexity of SCUC from the perspective of linearization. The proposed method can be well applied to large-scale long-term unit commitment problems. To better use this method, the following two properties should be highlighted: 1) the error of the proposed method is less than the Lagrangian relaxation method and decreases with the increasing system scales and 2) the computational efficiency of the proposed method is 10-100 times faster than that of the MIP model. We have tested many practical power systems and find that the error of the proposed LP model is usually very small compared with the precise MIP while the computational performance is significantly improved. In some practical cases, the decision makers usually do not want to find the precise optimal solution while only an approximation under a fast speed, because the boundary condition is imprecise. The proposed method is useful. Besides, for the cases that need the precise optimal solution, the proposed method can provide a high-quality initial solution for the MIP model to accelerate the convergence.

The 3D reconstruction of patient specific bone models plays a crucial role in orthopaedic surgery for clinical evaluation, surgical planning and precise implant design or selection. This paper considers the problem of reconstructing a patient-specific 3D tibia and fibula model from only two 2D X-ray images and one 3D general model segmented from the lower leg CT scans of one randomly selected patient. Currently, the bone 3D reconstruction mainly relies on computed tomography (CT) and magnetic resonance imaging (MRI) scanning-based mode segmentation which result in high radiation exposure or expensive costs. While, the proposed algorithm can accurately and efficiently deform a 3D general model to achieve a patient-specific 3D model that matches the patient's tibia and fibula projections in two 2D X-rays. The algorithm undergoes a preliminary deformation, 2D contour registration, and opti-misation based on the deformation graph that represents the shape deformation of models. Evaluations using simulations, cadaver and in-vivo experiments demonstrate that the proposed algorithm can effectively reconstruct the patient's 3D tibia and fibula surface model with high accuracy.

We consider the optimal sourcing problem when the available suppliers are subject to ambiguously correlated supply risks. This problem is motivated by the increasing severity of supply risks and difficulty evaluating common sources of vulnerability in upstream supply chains, which are problems reported by many surveys of goods-producing firms. We propose a distributionally robust model that accommodates (i) multiple levels of supply disruption, not just full delivery or no delivery, and (ii) can use data-driven estimates of the underlying correlation to develop sourcing strategies in situations where the true correlation structure is ambiguous. Using this framework, we provide analytical results regarding the form of a worst-case supply distribution and show that taking such a worst-case perspective is appealing due to severe consequences associated with supply chain risks. Moreover, we show how our distributionally robust model may be used to offer guidance to firms considering whether to exert additional effort in attempt to better understanding the prevailing correlation structure. Extensive computational experiments further demonstrate the performance of our distributionally robust approach and show how supplier characteristics and the type of supply uncertainty affect the optimal sourcing decision. History: Accepted by Pascal Van Hentenryck, Area Editor for Computational Modeling: Methods and Analysis. Funding: K. Pan was supported in part by the Research Grants Council of Hong Kong [Grant 15501920] and in part by the National Natural Science Foundation of China [Grant 72001185]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2022.1254 ) or is available from the IJOC GitHub software repository ( https://github.com/INFORMSJoC ) at http://dx.doi.org/10.5281/zenodo.7129356 .

Distributionally robust optimization (DRO) is a modeling framework in decision making under uncertainty in which the probability distribution of a random parameter is unknown although its partial information (e.g., statistical properties) is available. In this framework, the unknown probability distribution is assumed to lie in an ambiguity set consisting of all distributions that are compatible with the available partial information. Although DRO bridges the gap between stochastic programming and robust optimization, one of its limitations is that its models for large-scale problems can be significantly difficult to solve, especially when the uncertainty is of high dimension. In this paper, we propose computationally efficient inner and outer approximations for DRO problems under a piecewise linear objective function and with a moment-based ambiguity set and a combined ambiguity set including Wasserstein distance and moment information. In these approximations, we split a random vector into smaller pieces, leading to smaller matrix constraints. In addition, we use principal component analysis to shrink uncertainty space dimensionality. We quantify the quality of the developed approximations by deriving theoretical bounds on their optimality gap. We display the practical applicability of the proposed approximations in a production–transportation problem and a multiproduct newsvendor problem. The results demonstrate that these approximations dramatically reduce the computational time while maintaining high solution quality. The approximations also help construct an interval that is tight for most cases and includes the (unknown) optimal value for a large-scale DRO problem, which usually cannot be solved to optimality (or even feasibility in most cases). Summary of Contribution: This paper studies an important type of optimization problem, that is, distributionally robust optimization problems, by developing computationally efficient inner and outer approximations via operations research tools. Specifically, we consider several variants of such problems that are practically important and that admit tractable yet large-scale reformulation. We accordingly utilize random vector partition and principal component analysis to derive efficient approximations with smaller sizes, which, more importantly, provide a theoretical performance guarantee with respect to low optimality gaps. We verify the significant efficiency (i.e., reducing computational time while maintaining high solution quality) of our proposed approximations in solving both production–transportation and multiproduct newsvendor problems via extensive computing experiments.

The complexity of current electricity wholesale markets and the increased volatility of electricity prices because of the intermittent nature of renewable generation make independent power producers (IPPs) face significant challenges to submit offers. This challenge increases for those owning traditional coal-fired thermal generators and renewable generation. In this paper, an integrated stochastic optimal strategy is proposed for an IPP using the self-scheduling approach through its participation in both day-ahead and real-time markets (i.e., two-settlement electricity markets) as a price taker. In the proposed approach, the IPP submits an offer for all periods to the day-ahead market for which a multistage stochastic programming setting is explored for providing real-time market offers for each period as a recourse. This strategy has the advantage of achieving overall maximum profits for both markets in the given operational time horizon. Such a strategy is theoretically proved to be more profitable than alternative self-scheduling strategies as it takes advantage of the continuously realized scenario information of the renewable energy output and real-time prices over time. To improve computational efficiency, we explore polyhedral structures to derive strong valid inequalities, including convex hull descriptions for certain special cases, thus strengthening the formulation of our proposed model. Polynomial-time separation algorithms are then established for the derived exponential-sized inequalities to speed up the branch-and-cut process. Finally, both numerical and real case studies demonstrate the potential of the proposed strategy. Summary of Contribution: This paper develops innovative models and methods to study a family of practically important problems via the interactions of operations research and computing. Specifically, this paper provides in-depth analyses of innovative stochastic optimization modeling approaches and develops computationally efficient polyhedral results. The paper also verifies the effectiveness of proposed analyses via extensive computing experiments.

The electricity production of a thermal generator is often constrained by the available fuel supply. These fuel constraints impose a maximum bound on the energy output over multiple time periods. Fuel constraints are increasingly important in electricity markets because of two main reasons. First, as more natural gas-fired generators join the deregulated market, there is often competition for natural gas supply from other sectors (e.g., residential and manufacturing heating). Second, as more environmental and emission regulations are being placed on fossil fuel-fired generators, fuel supply is becoming more limited. However, there are few studies that consider the fuel constraints in the unit commitment problem from the perspective of computational analysis. To address the challenge faced by an independent power producer with a limited fuel supply, we study a fuel-constrained self-scheduling unit commitment (FSUC) problem where the production decisions are coupled across multiple time periods. We provide a complexity analysis of the FSUC problem and conduct a comprehensive polyhedral study by deriving strong valid inequalities. We demonstrate the effectiveness of our proposed inequalities as cutting planes in solving various multistage stochastic FSUC problems. History: Accepted by Pascal Van Hentenryck, Area Editor for Computational Modeling: Methods & Analysis. Funding: K. Pan was supported in part by the Research Grants Council of Hong Kong [Grant 15501920]. F. Qiu was supported in part by the U.S. Department of Energy Advanced Grid Modeling Program [Grant DE-OE0000875]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplementary Information [ https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2022.1235 ] or is available from the IJOC GitHub software repository ( https://github.com/INFORMSJoC ) at [ http://dx.doi.org/10.5281/zenodo.6896199 ].

With the increasing penetration of intermittent renewable energy and fluctuating electricity loads, power system operators are facing significant challenges in maintaining system load balance and reliability. In addition to traditional energy markets that are designed to balance power generation and load, ancillary service markets have been recently introduced to help manage the considerable uncertainty by reserving certain generation capacities against unexpected events. In this paper, we develop a multistage stochastic optimization model for system operators to efficiently schedule power-generation assets to co-optimize power generation and regulation reserve service (a critical ancillary service product) under uncertainty. In addition, to improve the computational efficiency of the proposed multistage stochastic integer program, we explore its polyhedral structure by investigating physical characteristics of individual generators, the system-wide requirements that couple all of the generators, and the scenario tree structure for our proposed multistage model. We start with the single-generator polytope and provide convex hull descriptions for the two-period case under different parameter settings. We then provide several families of multiperiod strong valid inequalities linking different scenarios and covering decision variables that represent both power generation and regulation reserve amounts. We further extend our study by exploring the multigenerator polytope and derive strong valid inequalities linking different generators and covering multiple periods. To enhance computational performance, polynomial-time separation algorithms are developed for the exponential number of inequalities. Finally, we verify the effectiveness of our proposed strong valid inequalities by applying them as user cuts under the branch-and-cut scheme to solve multistage stochastic network-constrained power generation scheduling problems.

In Online Social Networks (OSNs), privacy issue is a growing concern as more and more users are sharing their candid personal information and friendships online. One simple yet effective attack aims at private user data is to use socialbots to befriend the users and crawl data from users who accept the attackers' friend requests. With the attackers involving, individual users' preference and habit analysis is available, hence it is easier for the attackers to trick the users and befriend them. To better protect private information, some cautious, high-profile users may refer to their friends' decisions when receiving a friend request. The aim for this paper is to analyze the vulnerability of OSN users under this attack, in a more realistic setting that the high profile users having a different friend request acceptance model. Specifically, despite the existing probabilistic acceptance models, we introduce a deterministic linear threshold acceptance model for the cautious users such that they will only accept friend requests from users sharing at least a certain number of mutual friends with them. The model makes the cautious users harder to befriend with and complicates the attack. Although the new problem with multiple acceptance models is non-submodular and has no performance guarantee in general, we introduce the concept of adaptive submodular ratio and establish an approximation ratio under certain conditions. In addition, our results are also verified by extensive experiments in real-world OSN data sets.

Look-ahead unit commitment (LAUC) is recently introduced among independent system operators (ISOs) in the U.S. to increase generation capacity by committing more generators after day-ahead unit commitment when facing various uncertainties in the power system operations. However, as the share of intermittent renewable energy increases significantly in the power generation portfolio, the load continues to fluctuate, and unexpected events and market behaviors happen nowadays, the ISOs are facing new critical challenges to maintain the reliability of power system. To systematically manage these uncertainties and corresponding challenges, new advanced approaches are urgently required to improve current LAUC models and solution methods. Therefore, in this paper, we first propose a new formulation to represent forbidden zones and dynamic ramping rate limits, which help capture the system operation status more accurately and hedge against the uncertainties more effectively, and then correspondingly propose a data-driven risk-averse LAUC model. Our computational experiments show how the size of data influences operational decisions and how the inclusion of forbidden zones and dynamic ramping provide better decisions.

With fewer emissions, higher efficiency, and quicker response than traditional coal-fired thermal power plants, the combined-cycle units (CCUs), as gas-fired generators, have been increasingly adapted in the U.S. power system to enhance the smart grids operations. Meanwhile, due to the inherent uncertainties in the deregulated electricity market, e.g., intermittent renewable energy output, unexpected outages of generators and transmissions, and fluctuating electricity demands, the electricity price is volatile. As a result, this brings challenges for an independent power producer (served in the self-scheduling mode) owning CCUs to maximize the total profit when facing the significant price uncertainties. In this paper, a data-driven risk-averse stochastic self-scheduling approach is presented for the CCUs that participate in the real-time market. The proposed approach does not require the specific distribution of the uncertain real-time price. Instead, a confidence set for the unknown distribution is constructed based on the historical data. The conservatism of the proposed approach is adjustable based on the amount of available data. Finally, numerical studies show the effectiveness of the proposed approach.

In this paper, we introduce a novel algorithm aiming at maximizing the transmission capacity in wireless sensor networks (WSNs). Based on the Dijkstra algorithm and the max-flow theorem, the proposed algorithm solves the contradiction between the path length and forwarding capacity of various nodes, and thus scales up the relay capacity in terms of the number of transmitted packets from the source node to the sink node. Specifically, our algorithm first transforms the network from an undirected graph to a directed one, and then trims the excess paths in order to achieve the optimal capacity. We evaluate the proposed algorithm atop a testbed, and the experimental results show the significant performance enhancement by using the proposed algorithm.

In Content Centric Networking (CCN), registered data objects are frequently modified by users due to individual requirements, which results in downloading vulnerability to nodes. The overall consistency of data stored in multiple nodes is affected by two major factors, the changes in data content and the loss of data on each host, which significantly impacts the correctness and usability in the networks. To solve this problem, we apply optimization problem to minimize the overall transmission error of registered data delivered from the source node to the sink node in CCN. Specifically, we first describe the problems of transmission error rate and transmission time based on CCN. Then, we propose a specific strategy to unify the stored data and optimize system performance, and then achieve the minimized overall transmission fault for a certain amount of data. Finally, comprehensive simulations show that significant performance enhancement can be achieved by using our proposed scheme.

Testing database applications typically requires the generation of tests consisting of both program inputs and database states. Recently, a testing technique called Dynamic Symbolic Execution (DSE) has been proposed to reduce manual effort in test generation for software applications. However, applying DSE to generate tests for database applications faces various technical challenges. For example, the database application under test needs to physically connect to the associated database, which may not be available for various reasons. The program inputs whose values are used to form the executed queries are not treated symbolically, posing difficulties for generating valid database states or appropriate database states for achieving high coverage of query-result-manipulation code. To address these challenges, in this article, we propose an approach called SynDB that synthesizes new database interactions to replace the original ones from the database application under test. In this way, we bridge various constraints within a database application: query-construction constraints, query constraints, database schema constraints, and query-result-manipulation constraints. We then apply a state-of-the-art DSE engine called Pex for .NET from Microsoft Research to generate both program inputs and database states. The evaluation results show that tests generated by our approach can achieve higher code coverage than existing test generation approaches for database applications.

Emerging as an important potential approach to the operation of lossy communication networks, Network Coding (NC) has been proposed to combine with TCP called TCP-NC by MIT. However, the key parameter R that is brought in for sending redundant packets against random loss is preseted and stays constant, therefore, chances are that it may fail to work. In this paper, we proposed a dynamic redundancy algorithm to control the number of sending packets. The algorithm is executed at the time of every arrival of feedback and makes redundancy approximate the loss rate as much as possible. All of these is done by the sender who is completely unconscious of the network situation. Simulation results under hybrid networks show that our new protocol retains all the advantages of TCP-NC over TCP-Reno and TCP-Westwood in terms of channel utilization and overall throughput, and simultaneously outperforms TCP-NC in time-varying light-load hybrid networks.

Testing is essential for quality assurance of database applications. Achieving high code coverage of the database application is important in testing. In practice, there may exist a copy of live databases that can be used for database application testing. Using an existing database state is desirable since it tends to be representative of real-world objects' characteristics, helping detect faults that could cause failures in real-world settings. However, to cover a specific program code portion (e.g., block), appropriate program inputs also need to be generated for the given existing database state. To address this issue, in this paper, we propose a novel approach that generates program inputs for achieving high code coverage of a database application, given an existing database state. Our approach uses symbolic execution to track how program inputs are transformed before appearing in the executed SQL queries and how the constraints on query results affect the application's execution. One significant challenge in our problem context is the gap between program-input constraints derived from the program and from the given existing database state; satisfying both types of constraints is needed to cover a specific program code portion. Our approach includes novel query formulation to bridge this gap. Our approach is loosely integrated into Pex, a state-of-the-art white-box testing tool for .NET from Microsoft Research. Empirical evaluations on two real database applications show that our approach assists Pex to generate program inputs that achieve higher code coverage than the program inputs generated by Pex without our approach's assistance.

Bug-fixes are widely used for predicting bugs or finding risky parts of software. However, a bug-fix does not contain information about the change that initially introduced a bug. Such bug-introducing changes can help identify important properties of software bugs such as correlated factors or causalities. For example, they reveal which developers or what kinds of source code changes introduce more bugs. In contrast to bug-fixes that are relatively easy to obtain, the extraction of bugintroducing changes is challenging. In this paper, we present algorithms to automatically and accurately identify bug-introducing changes. We remove false positives and false negatives by using annotation graphs, by ignoring non-semantic source code changes, and outlier fixes. Additionally, we validated that the fixes we used are true fixes by a manual inspection. Altogether, our algorithms can remove about 38%~51% of false positives and 14%~15% of false negatives compared to the previous algorithm. Finally, we show applications of bug-introducing changes that demonstrate their value for research.

The change history of a software project contains a rich collection of code changes that record previous development experience. Changes that fix bugs are especially interesting, since they record both the old buggy code and the new fixed code. This paper presents a bug finding algorithm using bug fix memories: a project-specific bug and fix knowledge base developed by analyzing the history of bug fixes. A bug finding tool, BugMem, implements the algorithm. The approach is different from bug finding tools based on theorem proving or static model checking such as Bandera, ESC/Java, FindBugs, JLint, and PMD. Since these tools use pre-defined common bug patterns to find bugs, they do not aim to identify project-specific bugs. Bug fix memories use a learning process, so the bug patterns are project-specific, and project-specific bugs can be detected. The algorithm and tool are assessed by evaluating if real bugs and fixes in project histories can be found in the bug fix memories. Analysis of five open source projects shows that, for these projects, 19.3%-40.3% of bugs appear repeatedly in the memories, and 7.9%-15.5% of bug and fix pairs are found in memories. The results demonstrate that project-specific bug fix patterns occur frequently enough to be useful as a bug detection technique. Furthermore, for the bug and fix pairs, it is possible to both detect the bug and provide a strong suggestion for the fix. However, there is also a high false positive rate, with 20.8%-32.5% of non-bug containing changes also having patterns found in the memories. A comparison of BugMem with a bug finding tool, PMD, shows that the bug sets identified by both tools are mostly exclusive, indicating that BugMem complements other bug finding tools. Copyright ACM 2006.