Order selection on a single machine with high set-up costs

We study the problem of allocating a limited quantity of a single manufacturing resource to produce a subset of possible part-types. Customer orders require one or more part-types. We assume that revenue is received for an order only if it is completely filled, and that set-up costs and order revenues dominate the variable costs of production. We present a heuristic for the solution of our problem, as well as families of cutting-planes for an integer programming formulation. Computational results on a set of random test problems indicate that the heuristic is quite effective in producing near optimal solutions. The cutting-planes appear to be quite useful in reducing the number of linear programming solutions required by branch-and-bound.     

Approximations to the Log-Likelihood Function in the Nonlinear Mixed-Effects Model

Abstract

Nonlinear mixed-effects models have received a great deal of attention in the statistical literature in recent years because of the flexibility they offer in handling the unbalanced repeated-measures data that arise in different areas of investigation, such as pharmacokinetics and economics. Several different methods for estimating the parameters in nonlinear mixed-effects model have been proposed. We concentrate here on two of them—maximum likelihood and restricted maximum likelihood. A rather complex numerical issue for (restricted) maximum likelihood estimation in nonlinear mixed-effects models is the evaluation of the log-likelihood function of the data, because it involves the evaluation of a multiple integral that, in most cases, does not have a closed-form expression. We consider here four different approximations to the log-likelihood, comparing their computational and statistical properties. We conclude that the linear mixed-effects (LME) approximation suggested by Lindstrom and Bates, the Laplacian approximation, and Gaussian quadrature centered at the conditional modes of the random effects are quite accurate and computationally efficient. Gaussian quadrature centered at the expected value of the random effects is quite inaccurate for a smaller number of abscissas and computationally inefficient for a larger number of abscissas. Importance sampling is accurate, but quite inefficient computationally.     

The continuous collapsing Knapsack problem

A Collapsing Knapsack is a container whose capacity diminishes as the number of items it must hold is increased. This paper focuses on those cases in which the decision variables are continuous, i.e., can take any non-negative value. It is demonstrated that the problem can be reduced to a set of two dimensional subproblems. Strategies for elimination of subproblems and conditions permitting reduction to a set of one dimensional problems are also considered. Computational results indicate that the procedure is quite efficient. Even for large problems only a small number of subproblems have to be solved.     

多次分组会议安排的最佳混合方案

本文在仔细分析问题条件和要求的基础上,运用了运筹学、图论、矩阵理论和置换等方面的知识和技巧,建立了一个布尔规划模型。     

An Integer Goal Programming Model for Determining Military Aircraft Expenditures

The decision-making process involved in the procurement of military weapon systems, although quite critical and complex, still encompasses the basic characteristics of a capital budgeting problem. Given a number of expenditure items and a limited budget, it is desired to procure those weapon systems that will achieve the goals and objectives of the government and/or military in the most efficient manner. Since these objectives are typically numerous and diverse, traditional decision-making techniques are not applicable. As such, integer goal programming is suggested as a technique to be employed to determine the number of military aircraft to be procured, given conflicting expenditure, budget and effectiveness goals. This method is demonstrated via a case example in which the solution results are presented.     

The Evolution in Space and Time of Nonlinear Waves in Parallel Shear Flows

It is shown, using a quite general formulation, that the amplitude evolution equation for slowly varying finite amplitude waves is usually first order in both space and time. One advantage of the present formulation is that it becomes possible to easily identify, from their linear eigensolutions, interesting exceptional cases in which the amplitude evolves according to a partial differential equation that is second order in either space or time. The theory is applied to a number of specific problems, including flows with broken line profiles, and inviscid shear flows having nonlinear critical layers.     

The not-quite non-atomic game: Normal approximation

Measure games with a large number of players are frequently approximated by nonatomic games. In fact, however, while it is true that values of large measure games will, under certain reasonable circumstances, converge to the value of a non-atomic game, it is also true that this convergence is quite slow. Using the multi-linear extension and the central limit theorem, we obtain an approximation which (because it is based on the normal distribution) we call the normal approximation. We show that, for two examples with several hundred and several thousand players respectively, the normal approximation is much better than the non-atomic approximation.     

Mechanics of transition in an axisymmetric laminar boundary layer on a circular cylinder

Measurements of the growth of artificially generated turbulent spots and intermittency distribution in the transition region on a circular cylinder in axial flow show that the instability Reynolds number of 11,000 has a marked effect on the properties. In particular, it is found that the spot production in the initial region when a single turbulent spot has not yet wrapped around the cylinder and the propagation is essentially two-dimensional, is significantly altered. But the transition in the downstream or latter region, where most of the turbulent spots propagate onedimensionally (like the turbulent plugs in a pipe), is not affected. When the radius Reynolds number is more than 11,000, the intermittency law in the initial region is essentially the same as in twodimensional flow on a flat plate and in the latter region it is the one-dimensional flow in a pipe, the demarcation between the two regions being quite sharp.     

A spline collocation approach for a generalized wave equation subject to non-local conservation condition

In the present paper, a collocation finite element approach based on cubic splines is presented for the numerical solution of a generalized wave equation subject to non-local conservation condition. The efficiency, accuracy and stability of the method are assessed by applying it to a number of test problems. The results are compared with the existing closed-form solutions; the scheme demonstrates that the numerical outcomes are reliable and quite accurate when contrasted with the analytical solutions and an existing numerical method.     

The Aim of Justification and Epistemic Difference-Making Principles

The idea that truth is the aim of justification is one that is often defended by theorists who uphold different views about the nature of epistemic justification. Despite its prevalence, however, it is not quite clear how one is to cash out the metaphor that justification aims at truth. Some theorists, for example, have objected that the thesis would leave no room for justified false beliefs and unjustified true beliefs. In this paper, I offer an account of what it is for justification to aim at truth using the recently revived idea of difference-making according to which facts often make a difference to other facts. It will be argued that, thus understood, the thesis can illuminate a number of controversial debates in epistemology and that, given its explanatory power, it has a lot to recommend it.     

Rainbow Connections of Graphs: A Survey

The concept of rainbow connection was introduced by Chartrand et?al. [14] in 2008. It is interesting and recently quite a lot papers have been published about it. In this survey we attempt to bring together most of the results and papers that dealt with it. We begin with an introduction, and then try to organize the work into five categories, including (strong) rainbow connection number, rainbow k-connectivity, k-rainbow index, rainbow vertex-connection number, algorithms and computational complexity. This survey also contains some conjectures, open problems and questions.     

On the Modification of Rouche's Theorem for the Queueing Theory Problems

In analytic queueing theory, Rouche's theorem is frequently used to prove the existence of a certain number of zeros in the domain of regularity of a given function. If the theorem can be applied it leads in a simple way to results concerning the ergodicity condition and the construction of the solution of the functional equation for the generating function of the stationary distribution. Unfortunately, the verification of the conditions needed to apply Rouche's theorem is frequently quite difficult. We prove the theorem which allows to avoid some difficulties arising in applying classical Rouche's theorem to an analysis of queueing models.     

Textbooks revealing the development of a concept—the case of the number line in the analytic geometry (1708–1829)

The purpose of this paper is to use historical textbooks to explore the number line, a mathematical object common to our time, contextualizing its use during its initial development period in the seventeenth century until its current use as in the nineteenth century. Relevant analytic geometry textbooks are explored, mainly from France and from Germany of that time, to understand when and how this notion was used. Additionally, pertinent entries from encyclopedias of that time are used to contrast with what was not sufficiently explained in the aforementioned textbooks, until, finally, we can identify this object as it is currently characterized. I analyze how the negative numbers were used to constitute the number line and survey several number line diagrams, which were sometimes similar, but most often quite different from each other. The intention is to understand the historical contexts that configure the emergence and development of the notion of the number line.     

Line integral methods which preserve all invariants of conservative problems

Recently, the class of Hamiltonian Boundary Value Methods (HBVMs) has been introduced with the aim of preserving the energy associated with polynomial Hamiltonian systems (and, more in general, with all suitably regular Hamiltonian systems). However, many interesting problems admit other invariants besides the Hamiltonian function. It would be therefore useful to have methods able to preserve any number of independent invariants. This goal is achieved by generalizing the line-integral approach which HBVMs rely on, thus obtaining a number of generalizations which we collectively name Line Integral Methods. In fact, it turns out that this approach is quite general, so that it can be applied to any numerical method whose discrete solution can be suitably associated with a polynomial, such as a collocation method, as well as to any conservative problem. In particular, a completely conservative variant of both HBVMs and Gauss collocation methods is presented. Numerical experiments confirm the effectiveness of the proposed methods.     

A convergent criss-cross method

Our paper presents a new Criss-Cross method for solving linear programming problems. Starting from a neither primal nor dual feasible solution, we reach an optimal solution in finite number of steps if it exists. If there is no optimal solution, then we show that there is not primal feasible or dual feasible solution, We prove the finiteness of this procedure. Our procedure is not the same as the primal or dual simplex method if we have a primal or dual feasible solution, so we have constructed a quite new procedure for solving linear programming problems.     

A highly efficient RPF-based broadcast protocol using a new two-level pruning mechanism

Reverse path forwarding (RPF) based data communication is one of the widely used data communication protocols in networks. The most attractive feature of RPF is that reasonably low amount of memory is needed per router for storing the routing information (DVR table). However, it generates quite a large number of duplicate packets resulting in poor bandwidth utilization. We have observed that if the location of the broadcast source is considered while forwarding a packet, considerable improvement of the bandwidth utilization can be achieved from the viewpoint of less number of duplicate packets generated. In this paper we have used this location aspect in the design of a novel hierarchical pruning mechanism to improve bandwidth utilization for broadcasting based on RPF mechanism for data communication. Experimental results support our theoretical findings and hence guarantee improvement of bandwidth utilization.     

Algorithms with Adaptive Smoothing for Finite Minimax Problems

We present a new feedback precision-adjustment rule for use with a smoothing technique and standard unconstrained minimization algorithms in the solution of finite minimax problems. Initially, the feedback rule keeps a precision parameter low, but allows it to grow as the number of iterations of the resulting algorithm goes to infinity. Consequently, the ill-conditioning usually associated with large precision parameters is considerably reduced, resulting in more efficient solution of finite minimax problems.The resulting algorithms are very simple to implement, and therefore are particularly suitable for use in situations where one cannot justify the investment of time needed to retrieve a specialized minimax code, install it on one's platform, learn how to use it, and convert data from other formats. Our numerical tests show that the algorithms are robust and quite effective, and that their performance is comparable to or better than that of other algorithms available in the Matlab environment.     

The alignment problem of visual cryptography schemes

Pixel expansion is an important parameter for Visual Cryptography Schemes (VCS). However, most papers in the literature are dedicated to reduce pixel expansion on the pixel level, i.e. to reduce the number of subpixels that represent a pixel in the original secret image. It is quite insufficient since the final size of the transparencies of the VCS is affected not only by the number of the subpixels, but also by the size of the subpixels in the transparencies. However, reducing the size of the subpixels in the transparencies results in difficulties of alignment of the transparencies. In this paper, we consider the alignment problem in VCS, and prove that in order to visually recover the original secret image, it is not necessary to align the transparencies precisely. This study is restricted to the case when only one transparency is shifted.      

Consistency method for measurements of the support function of a convex body in the metric of L<Subscript>∞</Subscript>

A new algorithm is proposed for estimation of convex body support function measurements in L _∞ metric, which allows us to obtain the solution in quadratic time (with respect to the number of measurements) not using linear programming. The rate of convergence is proved to be stable for quite weak conditions on input data. This fact makes the algorithm robust for a wider class of problems than it was previously. The implemented algorithm is stable and predictable unlike other existing support function estimation algorithms. Implementation details and testing results are presented.     

Use of the BATA algorithm and MIS to solve the mail carrier problem

This paper presents a management information system (MIS) related to a new meta-heuristic algorithm used for solving the mail carrier problem. Although the mail carrier problem involves both pick-ups and deliveries, the problem is stated as the capacitated vehicle routing problem (CVRP), using zero customer demands, since their quantity (number of letters) is not taken into consideration, due to negligible volume occupying in the boot of motor scooter used for distribution operations. The proposed meta-heuristic algorithm termed as backtracking adaptive threshold accepting (BATA) was tested on some known benchmark problems extracted from the literature and it was proved to be quite efficient.