On the Multiplicity Problem and the Isomorphism Problem for the Four Subspace Algebra

Let Λ be the four subspace algebra. We show that for any Λ-module M there exists an algorithm (up to the problem of finding roots of the so-called characteristic polynomial of M) with relatively low polynomial complexity of determining multiplicities of all direct summands of M. Moreover, we give a fully algorithmic criterion for deciding if two Λ-modules M and N are isomorphic.     

A school bus scheduling problem

This paper introduces a school bus scheduling problem wherein trips for each school are given. A trip consists of a sequence of bus stops and their designated school. Each school has its fixed time window within which trips should be completed. A school bus can serve multiple trips for multiple schools. The school bus scheduling problem seeks to optimize bus schedules to serve all the given trips considering the school time windows. We first model the problem as a vehicle routing problem with time windows (VRPTW) by treating a trip as a virtual stop. Two assignment problem based exact approaches are then proposed for special cases and a heuristic algorithm is proposed for more general cases. Benchmark problems and computational experiments are presented. Computational experiments show the effectiveness of the proposed approaches.     

C运输问题

在传统的运输问题中 ,总假设所有产地 (发点 )的产量之和或所有销地 (收点 )的销量之和就是货物的总运输量 .但在实践中 ,特别是在一些与环境有关的资源、稀有资源或不可再生资源的开发利用过程中 ,由于受环境保护或政策限制 ,常常对这些资源的开采和运输有一定的数量限制 .这一类对总运输量有数量限制的运输问题不同于 A运输问题和 B运输问题 ,我们把它称为 C运输问题 .事实上 ,C运输问题是 A运输问题和 B运输问题的推广 .将给出 C运输问题的数学模型和求解方法 .     

The Markov power moment problem in problems of controllability and frequency extinguishing for the wave equation on a half-axis

In this paper necessary and sufficient conditions of null-controllability and approximate null-controllability are obtained for the wave equation on a half-axis. Controls solving these problems are found explicitly. Moreover, bang-bang controls solving the approximate null-controllability problem are constructed with the aid of solutions of a frequency extinguishing problem in the restricted band (−a,a) for this equation and the Markov power moment problem.     

Interface Problems for Elliptic Systems

Interface problems for elliptic systems of second order partial differential equations are studied. The main result is that the solution in the neighborhood of the singular point can be divided into two parts one of which is a solution to the homogeneous system with constant coefficients, and the other one possesses higher regularity.     

Robust absolute single machine makespan scheduling-location problem on trees

We investigate a robust single machine scheduling-location problem with uncertainty in edge lengths. Jobs are located at the vertices of a given tree. Given a location for a single machine, the jobs travel to the location and are processed there sequentially. The goal is to find a location of the machine and simultaneously a sequence to minimize the makespan value in the worst-case. We use the concept of gamma-robustness to model uncertainty. Our main result is a polynomial time algorithm.     

下料问题的优化模型及其快速算法

结合生产实际中具体的下料问题,本文建立了该类问题的优化模型,并提出下料方式的遴选三准则,即高利用率优先准则,长度优先准则和时间优先准则.运用本文的算法对一维下料的利用率高达99.6%,机器时间4秒.对二维的利用率为98.9%,机器时间约7秒.     

Minimum power multicasting problem in wireless networks

In this paper we deal with the minimum power multicasting (MPM) problem in wireless ad-hoc networks. By using an appropriate choice of the decision variables and by exploiting the topological properties of the problem, we are able to define an original formulation based on a Set Covering model. Moreover, we propose for its solution two exact procedures that include a preprocessing technique that reduces the huge number of the model’s constraints. We also report some experimental results carried out on a set of randomly generated test problems.     

APPROXIMATE BIFURCATION OF OBSTACLE PROBLEMS WITH OUT-VOLUME FORCE

In this paper we are concerned with the bifurcation of obstacle problem with outer volume force. Existence theorems of bifurcation points and approximate bifurcation points are given. Moreover the convergence of approximate method is discussed, and numerical results are presented.     

Capacitated transportation problem with bounds on RIM conditions

Motivated by dead-mileage problem assessed in terms of running empty buses from various depots to starting points, we consider a class of the capacitated transportation problems with bounds on total availabilities at sources and total destination requirements. It is often difficult to solve such problems and the present paper establishes their equivalence with a balanced capacitated transportation problem which can be easily solved by existing methods. Sometimes, total flow in transportation problem is also specified by some external decision maker because of budget/political consideration and optimal solution of such problem is of practical interest to the decision maker and has motivated us to discuss such problem. Various situations arising in unbalanced capacitated transportation problems have been discussed in the present paper as a particular case of original problem. In addition, we have discussed paradoxical situation in a balanced capacitated transportation problem and have obtained the paradoxical solution by solving one of the unbalanced problems. Numerical illustrations are included in support of theory.     

A transformation of hard (equality constrained) knapsack problems into constrained shortest path problems

The purpose of this paper is to show how hard (equality constrained) knapsack problems may be converted into constrained shortest path problems. Several directions along which such a transformation might be exploited for algorithmic purposes are suggested.     

Auxiliary problem principles for equilibria

The auxiliary problem principle allows solving a given equilibrium problem (EP) through an equivalent auxiliary problem with better properties. The paper investigates two families of auxiliary EPs: the classical auxiliary problems, in which a regularizing term is added to the equilibrium bifunction, and the regularized Minty EPs. The conditions that ensure the equivalence of a given EP with each of these auxiliary problems are investigated exploiting parametric definitions of different kinds of convexity and monotonicity. This analysis leads to extending some known results for variational inequalities and linear EPs to the general case together with new equivalences. Stationarity and convexity properties of gap functions are investigated as well in this framework. Moreover, both new results on the existence of a unique solution and new error bounds based on gap functions with good convexity properties are obtained under weak quasimonotonicity or weak concavity assumptions.     

On solution strategies to Saint-Venant problem

Different solution strategies to the relaxed Saint-Venant problem are presented and comparatively discussed from a mechanical and computational point of view. Three approaches are considered; namely, the displacement approach, the mixed approach, and the modified potential stress approach. The different solution strategies lead to the formulation of two-dimensional Neumann and Dirichlet boundary-value problems. Several solution strategies are discussed in general, namely, the series approach, the reformulation of the boundary-value problems for the Laplace's equations as integral boundary equations, and the finite-element approach. In particular, the signatures of the finite-element weak solutions—the computational costs, the convergence, the accuracy—are discussed considering elastic cylinders whose cross sections are represented by piece-wise smooth domains.     

A modified quasi-boundary value method for ill-posed problems

In this paper, we study a final value problem for first order abstract differential equation with positive self-adjoint unbounded operator coefficient. This problem is ill-posed. Perturbing the final condition we obtain an approximate nonlocal problem depending on a small parameter. We show that the approximate problems are well posed and that their solutions converge if and only if the original problem has a classical solution. We also obtain estimates of the solutions of the approximate problems and a convergence result of these solutions. Finally, we give explicit convergence rates.     

Random homogenization of an obstacle problem

We study the homogenization of an obstacle problem in a perforated domain, when the holes are periodically distributed and have random shape and size. The main assumption concerns the capacity of the holes which is assumed to be stationary ergodic.     

On an inverse problem for acoustic and seismic waves

Two basic inverse problems for determining the constitutive relation in an attenuating medium from given absorption behavior of plane waves in the medium are dealt with in the frequency domain by methods of complex analysis. In particular the case of a prescribed constant internal friction function over the seismic frequencies is considered in detail.     

Two regularization methods for a Cauchy problem for the Laplace equation

A Cauchy problem for the Laplace equation in a rectangle is considered. Cauchy data are given for y=0, and boundary data are for x=0 and x=π. The solution for 0<y?1 is sought. We propose two different regularization methods on the ill-posed problem based on separation of variables. Both methods are applied to formulate regularized solutions which are stably convergent to the exact one with explicit error estimates.     

Boundary Value Problems of the Theory of Analytic Functions with Displacements

Integral representations are constructed for functions holomorphic in a strip. Using these representations an effective solution of Carleman type problem is given for a strip.     

The Solution of a Free Boundary Problem Related to Environmental Management Systems

Abstract

Explicit solutions of free boundary problems are notoriously difficult to find. In this article, we consider two log-normal diffusions. One represents the level of pollution, or degradation, in some environmental area. The second models the social, political, or financial cost of the pollution. A single control parameter is considered that reduces the rate of pollution. The optimal time to implement the change in the parameter is found by explicitly solving a free boundary problem. The novelty is that the smooth pasting conditions, which are difficult to justify, are not used in the derivation.     

Branch-and-bound for the Precedence Constrained Generalized Traveling Salesman Problem

The Precedence Constrained Generalized Traveling Salesman Problem (PCGTSP) combines the Generalized Traveling Salesman Problem (GTSP) and the Sequential Ordering Problem (SOP). We present a novel branching technique for the GTSP which enables the extension of a powerful pruning technique. This is combined with some modifications of known bounding methods for related problems. The algorithm manages to solve problem instances with 12–26 groups within a minute, and instances with around 50 groups which are denser with precedence constraints within 24 h.