A Constant-Potential Infeasible-Start Interior-Point Algorithm with Computational Experiments and Applications

We present a constant-potential infeasible-start interior-point (INFCP) algorithm for linear programming (LP) problems with a worst-case iteration complexity analysis as well as some computational results.The performance of the INFCP algorithm is compared to those of practical interior-point algorithms. New features of the algorithm include a heuristic method for computing a good starting point and a procedure for solving the augmented system arising from stochastic programming with simple recourse. We also present an application to large scale planning problems under uncertainty.     

On some computational problems in finite abelian groups

We present new algorithms for computing orders of elements, discrete logarithms, and structures of finite abelian groups. We estimate the computational complexity and storage requirements, and we explicitly determine the -constants and -constants. We implemented the algorithms for class groups of imaginary quadratic orders and present a selection of our experimental results. Our algorithms are based on a modification of Shanks' baby-step giant-step strategy, and have the advantage that their computational complexity and storage requirements are relative to the actual order, discrete logarithm, or size of the group, rather than relative to an upper bound on the group order.

     

Roundoff analyses and sparse data

Summary Techniques are emerging which automatically determine the effects of rounding error upon numerical methods of a certain type. Meaningful testing presupposes a reasonable basis for comparison. Typically, the error's effects upon a given method are compared either (i) with the effects of perturbing the computational problem or (ii) with the effects of rounding error upon a competing method. We show that the result of a type (ii) comparison often remains valid when the two methods are adapted for sparse data, though the comparison might be based upon a model of error propagation which requires that special care be taken. This observation sometimes provides a rationale for preferring comparisons (ii), since the results of type (i) comparisons may well not carry over to sparse data.Partially supported by NSF Grants GJ-42968 and MCS 76-13561 A01     

The Two-Period Travelling Salesman Problem Applied to Milk Collection in Ireland

We describe a new extension to the Symmetric Travelling Salesman Problem (STSP) in which some nodes are visited inboth of 2 periods and the remaining nodes are visited in either 1 ofthe periods. A number of possible Integer Programming Formulationsare given. Valid cutting plane inequalities are defined for thisproblem which result in an, otherwise prohibitively difficult, modelof 42 nodes becoming easily solvable by a combination of cuts andBranch-and-Bound. Some of the cuts are entered in a pool andonly used when it is automatically verified that they are violated.Other constraints which are generalisations of the subtour and combinequalities for the single period STSP, are identified manuallywhen needed. Full computational details of solution process aregiven.     

A Deterministic Approach to Linear Programs with Several Additional Multiplicative Constraints

We consider a global optimization problem of minimizing a linear function subject to p linear multiplicative constraints as well as ordinary linear constraints. We show that this problem can reduce to a 2p-dimensional reverse convex program, and present an algorithm for solving the resulting problem. Our algorithm converges to a globally optimal solution and yields an -approximate solution in finite time for any > 0. We also report some results of computational experiment.     

Simulation optimization of buffer allocations in production lines with unreliable machines

We use a recent simulationbased optimization method, sample path optimization, to find optimal buffer allocations in tandem production lines where machines are subject to random breakdowns and repairs, and the product is fluidtype. We explore some of the functional properties of throughput of such systems and exploit these properties to prove the almost sure convergence of our optimization technique, under a regularity condition on the steady state. Utilizing a generalized semiMarkov process (GSMP) representation of the system, we derive recursive expressions to compute onesided directional derivatives of throughput, from a single simulation run. Finally, we give computational results for lines with up to 50 machines. We also compare results for smaller lines with the results from a more conventional method, stochastic approximation, whenever applicable. In these numerical studies, our method performed quite well on problems that are considered difficult by current computational standards.     

On representation and aggregation of social evaluations in computational trust and reputation models

Interest for computational trust and reputation models is on the rise. One of the most important aspects of these models is how they deal with information received from other individuals. More generally, the critical choice is how to represent and how to aggregate social evaluations. In this article, we make an analysis of the current approaches of representation and aggregation of social evaluations under the guidelines of a set of basic requirements. Then we present two different proposals of dealing with uncertainty in the context of the Repage system [J. Sabater, M. Paolucci, R. Conte, Repage: Reputation and image among limited autonomous partners, Journal of Artificial Societies and Social Simulation 9 (2). URL http://jasss.soc.surrey.ac.uk/9/2/3.html], a computational module for management of reputational information based on a cognitive model of imAGE, REPutation and their interplay already developed by the authors. We finally discuss these two proposals in the context of several examples.     

Epsilon Dominance and Constraint Partitioning in Multiple Objective Problems

In this paper we consider efficient sets of multiple objective problems, in which the feasible action set is the intersection of two other sets, and where one of these sets has a special structure, such as an assignment or transportation structure. The objective is to find the efficient set of the special structure set, and its intersection with the other set, and to examine how good an approximation this set is to the desired efficient set. The approximation set is called an -efficient solution set. Some theoretical partition results are given for a special constraint structure with upper bounds on the objective function levels. For the case of 0-efficient solution sets, and finite explicit sets, a computational cost analysis of two computational sequences is given. We also consider two other 0-efficient solution set cases. Then -efficiency is considered for linear problems. Finally, the approach is illustrated by a special multiple objective transportation problem.     

Discretization and Transference of Bisublinear Maximal Operators

We develop a general condition for automatically discretizing strong type bisublinear maximal estimates that arise in the context of the real line. In particular, this method applies directly to Michael Lacey’s strong type boundedness results for the bisublinear maximal Hilbert transform and for the bisublinear Hardy-Littlewood maximal operator, furnishing the counterpart of each of these two results (without changes to the range of exponents) for the sequence spaces We then take up some transference applications of discretized maximal bisublinear operators to maximal estimates and almost everywhere convergence in Lebesgue spaces of abstract measures. We also broaden the scope of such applications, which are based on transference from by developing general methods for transplanting bisublinear maximal estimates from arbitrary locally compact abelian groups.     

Dual coordinate step methods for linear network flow problems

We review a class of recently-proposed linear-cost network flow methods which are amenable to distributed implementation. All the methods in the class use the notion of-complementary slackness, and most do not explicitly manipulate any global objects such as paths, trees, or cuts. Interestingly, these methods have stimulated a large number of newserial computational complexity results. We develop the basic theory of these methods and present two specific methods, the-relaxation algorithm for the minimum-cost flow problem, and theauction algorithm for the assignment problem. We show how to implement these methods with serial complexities of O(N ³ logNC) and O(NA logNC), respectively. We also discuss practical implementation issues and computational experience to date. Finally, we show how to implement-relaxation in a completely asynchronous, chaotic environment in which some processors compute faster than others, some processors communicate faster than others, and there can be arbitrarily large communication delays.Supported by Grant NSF-ECS-8217668 and by the Army Research Office under grant DAAL03-86-K-0171. Thanks are due to David Castañon, Paul Tseng, and Jim Orlin for their helpful comments.     

BPPLIB: a library for bin packing and cutting stock problems

The bin packing problem (and its variant, the cutting stock problem) is among the most intensively studied combinatorial optimization problems. We present a library of computer codes, benchmark instances, and pointers to relevant articles for these two problems. The library is available at http://or.dei.unibo.it/library/bpplib. The computer code section includes twelve programs: seven are directly downloadable from the library page, while for the remaining five we provide addresses where they can be obtained or downloaded. Some of the codes for which we provide an original C++ implementation need an integer linear programming solver. For such cases, the library provides two versions: one that uses the commercial solver CPLEX, and one that uses the freeware solver SCIP. The benchmark section provides over six thousands instances (partly coming from the literature and partly randomly generated), together with the corresponding solutions. Instances that are difficult to solve to proven optimality are included. The library also includes a BibTeX file of more than 150 references on this topic and an interactive visual tool to manually solve bin packing and cutting stock instances. We conclude this work by reporting the results of new computational experiments on a number of computer codes and benchmark instances.     

One-parametric bottleneck transportation problems

We discuss the bottleneck transportation problem with one nonlinear parameter in the bottleneck objective function. A finite sequence of feasible basic solutions which are optimal in subsequent closed parameter-intervals is generated using a primal method for the nonparametric subproblems. The best among three primal codes for solving these subproblems is selected on extensive computational comparisons. We discuss computational experience with the sequential method for the case of linear and quadratic dependence on one parameter. Observed computational behaviour is O((n ·m)), with 2.     

Adding and removing an attribute in a DEA model: theory and processing

We present a theoretical and computational study of the impact of inserting a new attribute and removing an old attribute in a data envelopment analysis (DEA) model. Our objective is to obviate a portion of the computational effort needed to process such model changes by studying how the efficient/inefficient status of decision-making units (DMUs) is affected. Reducing computational efforts is important since DEA is known to be computationally intensive, especially in large-scale applications. We present a comprehensive theoretical study of the impact of attribute insertion and removal in DEA models, which includes sufficient conditions for identifying efficient DMUs when an attribute is added and inefficient DMUs when an attribute is removed. We also introduce a new procedure, HyperClimb, specially designed to quickly identify some of the new efficient DMUs, without involving LPs, when the model changes with the addition of an attribute. We report on results from computational tests designed to assess this procedure's effectiveness.     

Crashing a maximum-weight complementary basis

We consider the problem of finding a maximum-weight complementary basis of anm × 2m matrix. The problem arises naturally, for example, when a complementary set of columns is proposed as an initial basis for a warm start of Lemke's algorithm, but the set of columns is rank-deficient. We show that the problem is a special case of the problem of finding a maximum-weight common base of two matroids. Furthermore, we show how to efficiently implement an algorithm for the general problem in the present context. Finally, we give computational results demonstrating the practicality of our algorithm in a typical application.Supported by the Canadian Natural Science and Engineering Research Council.     

A first-order block-decomposition method for solving two-easy-block structured semidefinite programs

In this paper, we consider a first-order block-decomposition method for minimizing the sum of a convex differentiable function with Lipschitz continuous gradient, and two other proper closed convex (possibly, nonsmooth) functions with easily computable resolvents. The method presented contains two important ingredients from a computational point of view, namely: an adaptive choice of stepsize for performing an extragradient step; and the use of a scaling factor to balance the blocks. We then specialize the method to the context of conic semidefinite programming (SDP) problems consisting of two easy blocks of constraints. Without putting them in standard form, we show that four important classes of graph-related conic SDP problems automatically possess the above two-easy-block structure, namely: SDPs for $\theta $ -functions and $\theta _{+}$ -functions of graph stable set problems, and SDP relaxations of binary integer quadratic and frequency assignment problems. Finally, we present computational results on the aforementioned classes of SDPs showing that our method outperforms the three most competitive codes for large-scale conic semidefinite programs, namely: the boundary point (BP) method introduced by Povh et al., a Newton-CG augmented Lagrangian method, called SDPNAL, by Zhao et al., and a variant of the BP method, called the SPDAD method, by Wen et al.     

Orthomorphisms and the construction of projective planes

We discuss a simple computational method for the construction of finite projective planes. The planes so constructed all possess a special group of automorphisms which we call the group of translations, but they are not always translation planes. Of the four planes of order 9, three admit the additive group of the field as a group of translations, and the present construction yields all three. The known planes of order 16 comprise four self-dual planes and eighteen other planes (nine dual pairs); of these, the method gives three of the four self-dual planes and six of the nine dual pairs, including the ``sporadic' (not translation) plane of Mathon.

     

Generalized two-parameter Lebesgue-Stieltjes integrals and their applications to fractional Brownian fields

We consider two-parameter fractional integrals and Weyl, Liouville, and Marchaut derivatives and substantiate some of their properties. We introduce the notion of generalized two-parameter Lebesgue-Stieltjes integral and present its properties and computational formulas for the case of differentiable functions. The main properties of two-parameter fractional integrals and derivatives of Hölder functions are considered. As a separate case, we study generalized two-parameter Lebesgue-Stieltjes integrals for an integrator of bounded variation. We prove that, for Hölder functions, the integrals indicated can be calculated as the limits of integral sums. As an example, generalized two-parameter integrals of fractional Brownian fields are considered.Translated from Ukrainskyi Matematychnyi Zhurnal, Vol. 56, No. 4, pp. 435–450, April, 2004.     

Minimal projective resolutions

In this paper, we present an algorithmic method for computing a projective resolution of a module over an algebra over a field. If the algebra is finite dimensional, and the module is finitely generated, we have a computational way of obtaining a minimal projective resolution, maps included. This resolution turns out to be a graded resolution if our algebra and module are graded. We apply this resolution to the study of the -algebra of the algebra; namely, we present a new method for computing Yoneda products using the constructions of the resolutions. We also use our resolution to prove a case of the ``no loop' conjecture.

     

Monte Carlo path-integral calculations for two-point boundary-value problems

A computational technique based on the method of path integral is studied with a view to finding approximate solutions of a class of two-point boundary-value problems. These solutions are rough solutions by Monte Carlo sampling. From the computational point of view, however, once these rough solutions are obtained for any nonlinear cases, they serve as good starting approximations for improving the solutions to higher accuracy. Numerical results of a few examples are also shown.