A rounding procedure for semidefinite optimization

Mohammad-Nezhad and Terlaky studied the identification of the optimal partition for semidefinite optimization. An approximation of the optimal partition was obtained from a bounded sequence of solutions on, or in a neighborhood of the central path. We use the approximation of the optimal partition in a rounding procedure to generate an approximate maximally complementary solution. From an interior solution, sufficiently close to the optimal set, the procedure rounds to a conic feasible solution, while the equality constraints are slightly violated.     

An easy way to teach interior-point methods

In this paper the duality theory of Linear Optimization (LO) is built up based on ideas emerged from interior-point methods (IPMs). All we need is elementary calculus. We will embed the LO problem and its dual in a self-dual skew-symmetric problem. Most duality results, except the existence of a strictly complementary solution, are trivial for this embedding problem. The existence of the central path and its convergence to the analytic center of the optimal face will be proved. The proof is based on an elementary, careful analysis of a Newton step.We show also that if an almost optimal solution on the central path is known, then a simple strongly polynomial rounding procedure provides an exact strictly complementary optimal solution.The all-one vector is feasible for the embedding problem and it is an interior-point on the central path. This way an elegant solution to the initialization of IPMs is obtained as well. This approach allows to apply any IPM to the embedding problem while complexity results obtained for feasible IPMs are preserved.     

MEASURING OPTIMAL CONNECTIONS IN LARGE NETWORKS: A NEW ALGORITHM AND ITS APPLICATIONS

Researchers have identified several problems in measuring the strongest path connecting pairs of actors in valued graphs. To address these problems, it has been proposed that average path value be used to indicate optimal connections between dyads. However, a lack of proper computer algorithm and its implementation has hindered a wide-range application of the proposed solution. In this paper we develop a computer algorithm and fully implement it with four JAVA programs, which are available on request. These programs produce an optimal connection matrix, which is subsequently inputted into UCINET for further multidimensional scaling and clustering analysis. We demonstrate this procedure with a data matrix containing 38 organizations in information technology. We discuss the methodological implications of the application of our algorithm to future social network studies.     

Maximizing the Sum of Superdiagonal Matrix Elements in Local Variational Problems with a Singular Integrand

We show that the extremum of the local variational problem with a singular nonlinear integrand found by the optimal path continuation procedure is in fact a local extremum. Conditions simplifying the search for a global extremum are identified. Translated from Prikladnaya Matematika i Informatika, No. 3, pp. 11–19, 1999.     

Assortment planning for vertically differentiated products under a consider-then-choose model

Consider-then-choose models, borne out by empirical literature in marketing and psychology, note that customers follow a two-stage procedure to choose among alternatives. In this paper, we consider the assortment optimization problem of a retailer who manages a category of vertically differentiated products under customers’ consider-then-choose behavior. We characterize some structural results of the optimal assortment and find that the problem can be solved as the shortest path problem. Also, we develop an efficient algorithm to identify an optimal assortment.     

An analysis of the efficacy and efficiency of hierarchical procedures for computing trajectories over complex surfaces

A set of hierarchically-organized, heuristic path-finding procedures were applied to two subareas of a complex surface. These procedures typically found paths that were very close to optimal in terms of satisfying a minimum integral constraint. The procedures were one to two orders of magnitude less costly to apply than a set of similar, non-hierarchical procedures that found optimal paths. A systematic evaluation of hierarchical procedures having varying topologies and heuristic guidance functions, and employing different surface representations, was made. No procedure examined minimized both path traversal and path computation costs, and the choice of a best procedure was found to depend significantly on the nature of the surface traversed.     

A branch and cut algorithm for the hierarchical network design problem

The Hierarchical Network Design Problem consists of locating a minimum cost bi-level network on a graph. The higher level sub-network is a path visiting two or more nodes. The lower level sub-network is a forest connecting the remaining nodes to the path. We optimally solve the problem using an ad hoc branch and cut procedure. Relaxed versions of a base model are solved using an optimization package and, if binary variables have fractional values or if some of the relaxed constraints are violated in the solution, cutting planes are added. Once no more cuts can be added, branch and bound is used. The method for finding valid cutting planes is presented. Finally, we use different available test instances to compare the procedure with the best known published optimal procedure, with good results. In none of the instances we needed to apply branch and bound, but only the cutting planes.     

Optimal control of a finite dam with a sample path constraint

In this paper, we discuss the 2-stage output procedure of a finite dam under the condition that water must be released by a fixed time. From this standpoint, the reservoir model we consider is subject to a sample path constraint and has a more general cost function than the earlier contributions. We analytically derive explicit formulas for the long-run average and the expected total discounted costs for an infinite time span and numerically calculate the optimal control policy. Finally, the optimal policy is compared with one by Zuckerman [1] and the effect of the fixed release time is discussed further.     

A branch and bound algorithm for locating input and output points of departments on the block layout

We consider the problem of locating input and output (I/O) points of each department for a given layout. The objective of the problem is to minimise the total distance of material flows between the I/O points. Here, distances between the I/O points are computed as the lengths of the shortest path (not the rectilinear distances) between the I/O points. We developed a procedure to eliminate dominated candidate positions of I/O points that do not need to be considered. With this procedure, a large number of dominated candidate positions can be eliminated. A linear programming (LP) model for minimising the total rectilinear distance of flows is used to obtain a lower bound. Using the elimination procedure and the LP model, a branch and bound algorithm is developed to find an optimal location of the I/O points. Results from computational experiments show that the suggested algorithm finds optimal solutions in a very short time even for large-sized problems.     

The shortest path problem with two objective functions

We present methods to find the shortest path in a network where each path is associated with two objectives. We describe how to obtain the nondominated paths and the extreme nondominated paths, and compare the expected complexity of the methods. An improvement in efficiency can be obtained when quasiconcave or quasiconvex utility functions are assumed. In the first case, we describe how to find the optimal extreme nondominated path and bounds for the optimal path value. Then the optimal path can be located by calculating the k-th shortest path. In the second case we suggest a branch and bound method to solve the problem.     

On Well Definedness of the Central Path

We study the well definedness of the central path for a linearly constrained convex programming problem with smooth objective function. We prove that, under standard assumptions, existence of the central path is equivalent to the nonemptiness and boundedness of the optimal set. Other equivalent conditions are given. We show that, under an additional assumption on the objective function, the central path converges to the analytic center of the optimal set.     

Optimal paths in bi-attribute networks with fractional cost functions

An important routing problem is to determine an optimal path through a multi-attribute network which minimizes a cost function of path attributes. In this paper, we study an optimal path problem in a bi-attribute network where the cost function for path evaluation is fractional. The problem can be equivalently formulated as the “bi-attribute rational path problem” which is known to be NP-complete. We develop an exact approach to find an optimal simple path through the network when arc attributes are non-negative. The approach uses some path preference structures and elimination techniques to discard, from further consideration, those (partial) paths that cannot be parts of an optimal path. Our extensive computational results demonstrate that the proposed method can find optimal paths for large networks in very attractive times.     

A Tabu Search Heuristic Procedure for Solving the Transportation Problem with Exclusionary Side Constraints

A new heuristic procedure for the transportation problem with exclusionary side constraints is developed and implemented. Tabu search, a meta-heuristic method, is used to guide the search to follow a path selectively to prevent from being trapped at local optimal solutions in order to find a global optimal or near global optimal solution. The simplex method on a graph is employed to lead the search from one solution to an adjacent solution in order to take advantage of the underlying network structure of the problem. In the procedure, net changes in cost and in infeasibility are used to measure the attractiveness of a move, and strategic oscillation is used to implement the intensification and diversification functions. A computational experiment was conducted to test the performance of the heuristic procedure and substantial computational results are reported. These results show that the new heuristic procedure finds very good quality solutions and outperforms an existing heuristic procedure in terms of both solution quality and CPU time.     

Conditions for graphs to be path partition optimal

The path partition number of a graph is the minimum number of edges we have to add to turn it into a Hamiltonian graph, and the separable degree is the minimum number of edges we have to add to turn it into a 2-connected graph. A graph is called path partition optimal if its path partition number is equal to its separable degree. We study conditions that guarantee path partition optimality. We extend several known results on Hamiltonicity to path partition optimality, in particular results involving degree conditions and induced subgraph conditions.     

A depth-first search routing algorithm for star graphs and its performance evaluation

A fault-tolerant routing algorithm has been developed for star graph interconnection topology by using a depth-first search strategy. The proposed algorithm routes a message from the source to the destination along an optimal path with a very high probability and is guaranteed to trace a path as long as the source and the destination are not disconnected. We derive exact mathematical expressions for the probabilities that the algorithm will compute an optimal path for a given number of faulty links in the network. The analysis reveals many interesting topological properties of the star graphs.     

Optimal design of a manpower system

An equilibrium model of a manpower system is developed based on the notion of a career flow. Institutional constraints and measures of system performance are linear functions of the career flow. A typical optimal design problem is formulated and a solution procedure is developed. The optimization problem is a generalized linear program in which columns are generated by solving a shortest path problem. Upper and lower bounds on the optimal value function can be developed at each stage of the calculations.This research was supported by ONR grant N00014-75-C-0619.     

The grid refinement technique

The grid refinement technique is a discrete iterative procedure which generates sequences of approximate solutions to two-point variational problems defined on continuous fields. The approximate solutions are obtained by calculating the optimal path through discrete grids constructed throughout the continuous field. Convergence of the series of discrete approximating paths is obtained by successively decreasing the mesh size of the grids.     

The Inventory Lot-Sizing Problem with Continuous Time-Varying Demand and Shortages

In this study, we develop and analyse an optimal solution procedure for the inventory lot-sizing problem with a general class of time-varying demand functions. The objective of the procedure is to determine the optimal replenishment schedule over a finite planning horizon during which shortages are allowed and are completely backordered. We show that the procedure yields a unique optimal replenishment schedule for both increasing and decreasing demand patterns. We also discuss two particular cases of linear and non-linear demand trend models, and we illustrate the optimal solution procedure with four numerical examples.     

Seasonal forcing in stochastic epidemiology models

The goal of this paper is to motivate the need and lay the foundation for the analysis of stochastic epidemiological models with seasonal forcing. We consider stochastic SIS and SIR epidemic models, where the internal noise is due to the random interactions of individuals in the population. We provide an overview of the general theoretic framework that allows one to understand noise-induced rare events, such as spontaneous disease extinction. Although there are many paths to extinction, there is one path termed the optimal path that is probabilistically most likely to occur. By extending the theory, we have identified the quasi-stationary solutions and the optimal path to extinction when seasonality in the contact rate is included in the models. Knowledge of the optimal extinction path enables one to compute the mean time to extinction, which in turn allows one to compare the effect of various control schemes, including vaccination and treatment, on the eradication of an infectious disease.     

检测网络社团结构的基于最短路径的$k$-均值算法

我们考虑复杂网络社团结构的检测问题,即检测出那些具有高于平均密度的边所连接的节点的集合.本文我们利用模拟退火策略来极大化可表示为稳定效益函数的模量(modularity),并结合基于最短路径的$k$-均值迭代过程来对网络进行分区.该算法不仅能检测出社团,而且能够识别出在最短路径度量下,该社团中位于中心位置的节点.社团的最优数目可以在无需任何关于网络结构的先验信息下自动确定.对人工生成网络和真实世界中的网络的成功应用表明了算法的有效性.