A generic static analyzer for multithreaded Java programs

In this paper, we present heckmate , the first generic static analyzer of multithreaded Java programs based on abstract interpretation. heckmate can be tuned at different levels of precision and efficiency in order to prove various properties (e.g., absence of divisions by zero and data races), and it is sound for multithreaded programs. It supports all the most relevant features of Java multithreading, such as dynamic thread creation, runtime creation of monitors, and dynamic allocation of memory. The experimental results demonstrate that heckmate is accurate and efficient enough to analyze programs with some thousands of statements and a potentially infinite number of threads. Copyright © 2012 John Wiley & Sons, Ltd.     

Parametric tabu-search for mixed integer programs

A parametric form of tabu-search is proposed for solving mixed integer programming (MIP) problems that creates and solves a series of linear programming (LP) problems embodying branching inequalities as weighted terms in the objective function. The approach extends and modifies a parametric branch and bound procedure of Glover [Parametic branch and bound. OMEGA, The International Journal of Management Science 1978;6:1–9], replacing its tree search memory by the adaptive memory framework of tabu-search and introducing new associated strategies that are more flexible than the mechanisms of branch and bound.     

An algebra of mixed computation

Algebraic tools for mixed computation are presented. Some axioms for informational objects, program functions, inputs and outputs are introduced. These axioms are sufficient for the correct mixed computation of some basic program composition forms.     

Recursive central rounding for mixed integer programs

We introduce a new rounding heuristic for mixed integer programs. Starting from a fractional solution, the new approach is based on recursively fixing a subset of the discrete variables while using the analytic center to re-center the remaining ones. The proposed rounding approach can be used independently or integrated with other heuristics. We demonstrate both setups by first using the proposed approach to round the optimal solution of the linear programming relaxation. We then integrate the proposed rounding heuristic with the feasibility pump by replacing the original simple rounding function of the feasibility pump. We conduct computational testing on mixed integer problems from MIPLIB and CORAL and on mixed integer quadratic problems from MIQPLIB. The proposed algorithm is computationally efficient and provides good quality feasible solutions.     

A mixed finite element method for boundary flux computation

Most finite element schemes for thermal problems estimate boundary heat flux directly from the derivative of the finite element solution. The boundary flux calculated by this approach is typically inaccurate and does not guarantee a global heat balance.In this paper we present a mixed finite element method for calculating the boundary flux and show the superiority of this method through numerical examples of both diffusion and advection-diffusion problems.     

A hoare-like proof system for analysing the computation time of programs

Versions of Hoare logic have been introduced to prove partial and total correctness properties of programs. In this paper it is shown how a Hoare-like proof system for while programs may be extended to prove properties of the computation time as well. It should be stressed that the system does not require the programs to be modified by inserting explicit operations upon a clock variable. We generalize the notions of arithmetically sound and complete and show that the proof system satisfies these. Also we derive formal rules corresponding to the informal rules for determining the computation time of while programs. The applicability of the proof system is illustrated by an example, the bubble sorting algorithm.     

Denotational semantics of mixed computation processes for a structural programming language

Conclustions The paper formalizes two denotational models for mixed computation process in a structural programming language. A criterion of functional correctness is formulated and theorems are proved that show that the described models are functionally correct. The proposed models define more precisely the concept of mixed computations discussed in [1, 2], and make it, possible formally to prove their properties. Moreover, they can be regarded as formal specifications of the respective components of a mixed-computer software.Translated from Kibernetika, No. 1, pp. 16–27, 43, January–February, 1988.     

Computer programs for rapid computation of gravity effects of two-dimensional and three-dimensional bodies

A subroutine is presented which calculates the gravity effect of bodies of infinite strike length which have a polygonal cross section and uniform density. A second subroutine allows rapid calculation of end corrections, so approximating the effect of bodies of limited strike length. Modifications can be made which will allow the routines to be used for bodies asymmetrically positioned with respect to the line of observation.     

Challenging problems in partial evaluation and mixed computation

This paper collects together a variety of problems in partial evaluation and mixed computation that appear to be worth solving but as yet lack solutions or (in some cases) precise formulations. The problems come largely from discussions with and notes by participants in the 1987 workshop on Partial Evaluation and Mixed Computation.     

Algorithms and programs for the rapid computation of area and center of mass

Two algorithms are presented for the rapid and exact computation of the area within a closed polygonal boundary, and for determining the coordinates of the center of mass of that area. The algorithms are derived by a Stokes' Theorem transformation of the appropriate surface integrals to line integrals around the boundary. The algorithms are presented as a short FORTRAN subroutine and as a program for the Hewlett Packard Model HP-65 programmable calculator.     

Proving total correctness and generating preconditions for loop programs via symbolic-numeric computation methods

We present a symbolic-numeric hybrid method, based on sum-of-squares （SOS） relaxation and rational vec- tor recovery, to compute inequality invariants and ranking functions for proving total correctness and generating pre- conditions for programs. The SOS relaxation method is used to compute approximate invariants and approximate rank- ing functions with floating point coefficients. Then Gauss- Newton refinement and rational vector recovery are applied to approximate polynomials to obtain candidate polynomials with rational coefficients, which exactly satisfy the conditions of invariants and ranking functions. In the end, several exam- ples are given to show the effectiveness of our method.     

Proving total correctness and generating preconditions for loop programs via symbolic-numeric computation methods

We present a symbolic-numeric hybrid method, based on sum-of-squares (SOS) relaxation and rational vector recovery, to compute inequality invariants and ranking functions for proving total correctness and generating preconditions for programs. The SOS relaxation method is used to compute approximate invariants and approximate ranking functions with floating point coefficients. Then Gauss-Newton refinement and rational vector recovery are applied to approximate polynomials to obtain candidate polynomials with rational coefficients, which exactly satisfy the conditions of invariants and ranking functions. In the end, several examples are given to show the effectiveness of our method.     

Running programs backwards: The logical inversion of imperative computation

Imperative programs can be inverted directly from their forward-directed program code with the use of logical inference. The relational semantics of imperative computations treats programs as logical relations over the observable state of the environment, which is taken to be the state of the variables in memory. Program relations denote both forward and backward computations, and the direction of the computation depends upon the instantiation pattern of arguments in the relation. This view of inversion has practical applications when the relational semantics is treated as a logic program. Depending on the logic programming inference scheme used, execution of this relational program can compute the inverse of the imperative program. A number of nontrivial imperative computations can be inverted with minimal logic programming tools.     

Variable neighbourhood decomposition search for 0–1 mixed integer programs

In this paper we propose a new hybrid heuristic for solving 0–1 mixed integer programs based on the principle of variable neighbourhood decomposition search. It combines variable neighbourhood search with a general-purpose CPLEX MIP solver. We perform systematic hard variable fixing (or diving) following the variable neighbourhood search rules. The variables to be fixed are chosen according to their distance from the corresponding linear relaxation solution values. If there is an improvement, variable neighbourhood descent branching is performed as the local search in the whole solution space. Numerical experiments have proven that exploiting boundary effects in this way considerably improves solution quality. With our approach, we have managed to improve the best known published results for 8 out of 29 instances from a well-known class of very difficult MIP problems. Moreover, computational results show that our method outperforms the CPLEX MIP solver, as well as three other recent most successful MIP solution methods.     

Sequential approach to the solution of mixed linear programs

Cybernetics and Systems Analysis -