An optimal capacity assignment for the robust design problem in capacitated flow networks

This paper proposes an exact algorithm to solve the robust design problem in a capacitated flow network in which each edge has several possible capacities. A capacitated flow network is popular in our daily life. For example, the computer network, the power transmission network, or even the supply chain network are capacitated flow networks. In practice, such network may suffer failure, partial failure or maintenance. Therefore, each edge in the network should be assigned sufficient capacity to keep the network functioning normally. The robust design problem (RDP) in a capacitated flow network is to search for the minimum capacity assignment of each edge such that the network still survived even under the edge’s failure. However, how to optimally assign the capacity to each edge is not an easy task. Although this kind of problem was known of NP-hard, this paper proposes an efficient exact algorithm to search for the optimal solutions for such a network and illustrates the efficiency of the proposed algorithm by numerical examples.     

A new implementation of an algorithm for the optimal assignment problem: An improved version of Munkres' algorithm

Existing implementations of Munkres' algorithm for the optimal assignment problem are shown to requireO(n ⁴) time in the worstn×n case. A new implementation is presented which runs in worst-case timeO(n ³) and compares favorably in performance with the algorithm of Edmonds and Karp for this problem.The results of this paper were obtained by the author while at the Department of Computer Science, Cornell University. This work was supported in part by a Vanderbilt University Research Council Grant.     

Optimizing the marriage market: An application of the linear assignment model

Research shows that the success of marriages and other intimate partnerships depends on objective attributes such as differences in age, cultural background, and educational level. This article proposes a mathematical approach to optimizing marriage by allocating spouses in such a way as to reduce the likelihood of divorce or separation. To produce our optimization model, we use the assumption of a central “agency” that would coordinate the matching of couples. Based on a representative and longitudinal sample of 1074 cohabiting and married couples living in Switzerland, we estimate various objective functions corresponding to age, education, ethnicity, and prior divorce concerning every possible combination of men and women. Our results show that the current state of marriages or partnerships is well below the social optimum. We reallocate approximately 68% of individuals (7 out of 10) to a new couple that we posit has a higher likelihood of survival. From this selection of new partners, we obtain our final “optimal” solutions, with a 21% reduction in the objective function.     

An Upper Bound for the w-Weak Global Dimension of Pullbacks

Let R be a commutative ring with identity and I0 an ideal of R.We introduce and study the c-weak global dimension c-w.gl.dim(R/I0) of the factor ring R/I0.Let T be a w-linked extension of R,and we also introduce the wR-weak global dimension wR-w.gl.dim(T) of T.We show that the ring T with wR-w.gl.dim(T) =0 is exactly a field and the ring T with wR-w.gl.dim(T) ≤ 1 is exactly a PwRMD.As an application,we give an upper bound for the w-weak global dimension of a Cartesian square (RDTF,M).More precisely,if T is w-linked over R,then w-w.gl.dim(R) ≤ max{wR-w.gl.dim(T) + w-fdR T,c-w.gl.dim(D) + w-fdn D}.Furthermore,for a Milnor square (RDTF,M),we obtain w-w.gl.dim(R) ≤ max{wR-w.gl.dim(T) + w-fdR T,w-w.gl.dim(D) + w-fdR D}.     

An optimal control model and algorithm for the deviated well’s trajectory planning

This paper presents a nonlinear piecewise smooth dynamical system of the trajectory of deviated wells according to engineering background. An optimal control model is established and the necessary conditions for optimality are proved via maximum principle. The optimal control problem is solved by a revised Hooke–Jeeves algorithm. The uniform design technique has been incorporated into the revised Hooke–Jeeves algorithm to handle the multimodal function. Computer simulation is used for this paper, and the numerical example illustrates the validity and efficiency of the algorithm. The procedure demonstrates its advantages in practical applications in Liaohe Oil Field.     

On changing the spaces in Lagrange multiplier rules for the optimal control of non-linear operator equations

In this paper it is shown, how Lagrange multiplier rules for nonlinear optimal control problems in Banach spaces can be transferred by a simple device from the initial space to a more useful Banach space, in order to avoid unhandy dual spaces. The method is applied to state-equations of the type x-K(x,u)= 0, where the Fréchet-derivative of K has a certain smoothing property which is typical for integral operators.     

An optimal algorithm for generating equivalence relations on a linear array of processors

We describe a cost-optimal parallel algorithm for enumerating all partitions (equivalence relations) of the set {1, ...,n}, in lexicographic order. The algorithm is designed to be executed on a linear array of processors. It usesn processors, each having constant size memory and each being responsible for producing one element of a given set partition. Set partitions are generated with constant delay leading to anO(B _n) time solution, whereB _n is the total number of set partitions. The same method can be generalized to enumerate some other combinatorial objects such as variations. The algorithm can be made adaptive, i.e. to run on any prespecified number of processors. To illustrate the model of parallel computation, a simple case of enumerating subsets of the set {1, ...,n}, having at mostm (n) elements is also described.The research is partialy supported by NSERC operating grant OGPIN 007.