


Search published articles 


Showing 5 results for Subject: Discrete Optimization
M. ForghaniElahabad, N. MahdaviAmiri, Volume 4, Issue 2 (102013)
Abstract
A number of problems in several areas such as power transmission and distribution, communication and transportation can be formulated as a stochasticflow network (SFN). The system reliability of an SFN can be computed in terms of all the upper boundary points, called dMinCuts (dMCs). Several algorithms have been proposed to find all the dMCs in an SFN. Here, some recent studies in the literature on search for all dMCs are investigated. We show that some existing results and the corresponding algorithms are incorrect. Then, correct versions of the results are established. By modifying an incorrect algorithm, we also propose an improved algorithm. In addition, complexity results on a number of studies are shown to be erroneous and correct counts are provided. Finally, we present comparative numerical results in the sense of performance profile of Dolan and Moré showing the proposed algorithm to be more efficient than some existing algorithms.
Godfrey Chagwiza, Brian Jones, Senelani Hove Musekwa, Sobona Mtisi, Volume 5, Issue 2 (102014)
Abstract
We introduce a new way of generating cutting planes of a mixed integer programme by way of taking binary variables. Four binary variables are introduced to form quartic inequalities, which results in a reduced firstlevel mixed integer programme. A new way of weakening the inequalities is presented. An algorithm to carryout the separation of the inequalities, which are exponential in number, is developed. The proposed method of cuts generation, separation and strengthening is compared to the Gomory, linear branching and coordinated cutting plane methods. The computational results show that the proposed method is promising but becomes complicated as number of variables increases.
M Aman, J Tayyebi, Volume 5, Issue 2 (102014)
Abstract
Given an instance of the minimum cost flow problem, a version of the corresponding inverse problem, called the capacity inverse problem, is to modify the upper and lower bounds on arc flows as little as possible so that a given feasible flow becomes optimal to the modified minimum cost flow problem. The modifications can be measured by different distances. In this article, we consider the capacity inverse problem under the bottlenecktype and the sumtype weighted Hamming distances. In the bottlenecktype case, the binary search technique is applied to present an algorithm for solving the problem in O(nm log n) time. In the sumtype case, it is shown that the inverse problem is strongly NPhard even on bipartite networks
Sattar Sattari, Didehvar, Volume 6, Issue 1 (32015)
Abstract
The routing cost of a spanning tree in a weighted and connected graph is defined as the total length of paths between all pairs of vertices. The objective of the minimum routing cost spanning tree problem is to find a spanning tree such that its routing cost is minimum. This is an NPHard problem that we present a GRASP with pathrelinking metaheuristic algorithm for it. GRASP is a multistart algorithm that in each iteration constructs a randomized greedy solution and applies local search to it. Pathrelinking stores elite solutions and to find better solutions explores the paths between different solutions. Experimental results show the performance of our algorithm on many benchmark problems compared to the other algorithms.
Prof. Kourosh Eshghi, Mr. Mohsen Salarrezaei, Volume 7, Issue 1 (42016)
Abstract
First, an integer programming model is proposed to find an αlabeling for quadratic graphs. Then, a Tabu search algorithm is developed to solve large scale problems. The proposed approach can generate αlabeling for special classes of quadratic graphs, not previously reported in the literature. Then, the main theorem of the paper is presented. We show how a problem in graph theory can be modeled and solved by an integer programming model and a metaheuristic approach.

