This paper proposes an uncertain multi-period bi-level network interdiction problem with uncertain arc capacities. It is proved that there exists an equivalence relationship between uncertain multi-period network interdiction problem and the obtained deterministic correspondent. Application of the generalized Benders’ decomposition algorithm is considered as the solution approach to the resulting mixed-integer nonlinear programming problem. Finally, a numerical example is presented to illustrate the model and the algorithm.
It is a well-known fact that finding a minimum dominating set and consequently finding the domination number of a general graph is an NP-complete problem. Here, we first model this problem as nonlinear binary optimization problems and then extract two closely related semidefinite relaxations. For each of these relaxations, different rounding algorithms are exploited to produce near-optimal dominating sets. Feasibility of the generated solutions and efficiency of the algorithms are analyzed.
Cash is the driving power of all business and cash-flow statement is one of the major issues of institutions, especially in crisis. Optimal cash-flow plan of a company could be one of the most important indicators of that business’s financial health and can be considered as its financial analysts’ ability and skill. Linear optimization (LO) is one of the mathematical tools in modeling the cash-flow problem and its rich literature helps analysts to devise the optimal one when the situation satisfies the requirements of the LO model. However, the situation is always due to variation and the optimal solution arisen from the LO model have to be analyzed according to measurable variation of input data. Sensitivity analysis and parametric programming is the tool to this analysis. Using the Simplex method to find a basic optimal solution and having multiple optimal solutions is one of the reasons that different solvers lead to different optimal solutions. In these situations, sensitivity analysis may produce confusing results. Moreover, there are different points of views to sensitivity analysis such as optimal basis invariancy, optimal partition invariancy, support set invariancy to name some examples. Here, we briefly review different approaches to sensitivity analysis in LO and a short term cash-flow problem of a dummy institution is modeled as an LO problem. It is shown that the problem has multiple optimal solutions which are degenerate, the situation that usually occurs in practice and causes of ambiguous and unclear results. The confusing results in analyzing the sensitivity of these solutions are highlighted in this example. Then, a strictly complementary optimal solution is provided and its useful interpretation in sensitivity analysis is mentioned in a nutshell. In the sequel, the concept of the results arising in different points of views to sensitivity analysis is analyzed.
Common carrier pipelines are the best suited mode for transporting large volumes of petroleum products from production areas to long-distance terminals. In such pipelines, batches of refined petroleum products are pumped back-to-back, without any physical barrier separating them. The problem addressed in this paper deals with the scheduling of a real world multi-product, single source pipeline system that must supply the products to several offtake terminals. Most contributions on the scheduling of single-source multiproduct pipeline operations deal with the sequence deliveries in distribution terminals i.e., at any time only one terminal is connected to the pipeline. Practically, pipeline operators usually carry out simultaneous deliveries to multiple terminals to cut down the number of pipeline stoppages and pump switchings so as to reduce the energy consumed for resuming flow in idle pipeline segments, and the pump maintenance costs. This paper introduces a novel continuous mathematical approach, mixed integer linear programming to solve the short-term operational planning by allowing the execution of simultaneous deliveries to multiple receiving terminals during a pumping operation. Contrarily to previous continuous approaches that perform the pipeline input/output operations in two hierarchical stages, the new formulation aims to find both of them in a single step. The objective of this work is to find the optimal sequence of input and output operations that satisfy terminal requirements at minimum total costs. As compared to previous works, significantly improvement in solution quality has been achieved. Especially, the proposed formulation leads to better utilization of the pipeline capacity, and consequently, a substantial reduction in the amount of required time for satisfying all of the specified product deliveries, i.e., the pipeline running time. The main results are presented.
Mother-infant vocalization from distance in some animal species such as bats, gulls and penguins is a basic tool to find the other’s location. It is referred to echolocation or bio-sonar characteristics which is important for the mother to nd exactly its own baby in a large colony. Moreover, the baby uses it to better conduction the mother in getting back to the nest without knowing its exact location. This natural fact is the motivation of the current study to devise a novel metaheuristic algorithm in solving optimization problems. The proposed methodology was tested on some continuous functions and led to promising results on convergence.
This paper addresses the optimal scheduling of straight pipelines featuring multiple intermediate nodes acting as dual-purpose stations,with a continuous-time Mixed-Integer Linear Programming formulation partly derived from Generalized Disjunctive Programming. The new model allows for an intermediate station to act as an output and input terminal at the same time so as to reduce the number of segment switches between active and idle, and consequently decrease operating costs. Contrary to previous approaches, decisions related to batch sizing, batch sequencing and timing are determined in a single step. Several examples of growing complexity are solved to illustrate the effectiveness and computational advantage of the proposed model in both solution quality and CPU time.
This paper considers a novel formulation of the multi-period network interdiction problem. In this model, delivery of the maximum ow as well as the act of interdiction happens over several periods, while the budget of resource for interdiction is limit. It is assumed that when an edge is interdicted in a period, the evader considers a rate of risk of detection at consequent periods. Application of the generalized Benders decomposition algorithm considers
solving the resulting mixed-integer nonlinear programming problem. Computational experiences denote reasonable consistency with expectations.
Floods as natural phenomena exist and will continue to occur. No manmade project can stop a flood from happening, but there are several effective methods to reduce its risk, aftermath and consequences. This paper considers a novel formulation of the network interdiction problem with application on controlling floods. The aim of this work is to identify those arcs prone for flood, and implementing flood-control projects on these arcs, while required budget for deriving all these operations is bounded. the model is tested on a real-world case in Tabriz-Iran, and results are visualized.
Indeterminacy is an intrinsic characteristics of real-world data. Where they originate from credible experiments, probability theory is a robust tool to manipulate this type of indeterminacy. However, this is not always the case, and referring to the domain expert belief is an alternative approach. Baoding Liu initiated an axiomatic basis of uncertainty theory to answer this kind of indeterminacy. Dominating set with its different versions has a wide range of applications in many fields, while the practice suffers indeterminacy with no reliable data in most cases. In this paper, we investigate the minimum weighted dominating set with indeterministic weights in two cases. The weights in the first one have probability distribution and in the other one uncertainty distribution which they are based on the belief degree of the domain expert. In both cases, the objective function of model is not defined. To overcome this difficulty, based on probability and uncertainty theory, deterministically two different models are constructed. The first model considers an α-chance method, and the second exploits the expected value of the uncertain variables. Both models are converted to deterministic ones resulting to the so-called α-minimum weighted dominating set, and the uncertain minimum weighted dominating set, respectively. A prototype application in earthquake relief management is provided, and the performance of models is experimented in a concrete illustrative example.
Detailed scheduling of long-distance multiproduct pipelines has received growing attention in the past few years. It helps the planner to reduce the number of pump and segment switches between active and idle conditions to obtain savings on pump operating and maintenance costs. Most contributions on the detailed scheduling of multiproduct pipelines concern networks with a single straight line. Large-scale pipeline networks, however, usually have a treelike configuration, featuring a mainline and several secondary lines, transporting smaller volumes of refined petroleum products over shorter distances. This work addresses the scheduling of a multiproduct treelike pipeline through a continuous-time mixed integer linear programming (MILP) model that allows the execution of simultaneous deliveries from a unique refinery to multiple downstream terminals so as to get a substantial increase in transportation capacity. Contrary to previous contributions on treelike pipeline systems, the new model solves batch sizing and sequencing problems in a single step, generating a detailed delivery schedule. It also handles flow rate limitations in downstream pipeline segments originated from a lower diameter. Three case studies including one real life problem are used to illustrate the efficacy of the proposed model.
Understanding the effect of variation of the coefficient matrix in linear optimization problem on the optimal solution and the optimal value function has its own importance in practice. However, most of the published results are on the effect of this variation when the current optimal solution is a basic one. There is only a study of the problem
for special perturbation on the coefficient matrix, when the given optimal solution is strictly complementary and the optimal partition (in some sense) is known. Here, we consider an arbitrary direction for perturbation of the coefficient matrix and present an effective method based on generalized inverse and singular values to detect invariancy intervals and corresponding transition points.
Common carrier pipelines are one of the most economic modes for transportation of petroleum refined products
over land, especially when huge amounts of these products have to be pumped toward long-distance terminals. This paper introduces a novel Mixed Integer Linear Programming (MILP)-based approach for the long-term scheduling of a real world multiproduct pipeline connecting a unique refinery to several distribution centers. This approach allows consideration of multiple due dates for demands at period ends, flow rate limitation on pipeline segments, and simultaneous deliveries at distribution centers. The proposed model results in substantial reduction in pump operation and maintenance costs in comparison with the available models. Computational results and data are reported.
Grouping datasets play an important role in many scientific research works. Depending on the data features and applications, different constraints are imposed on groups, while having groups with similar members is always a main criterion. In this paper, we propose an algorithm for grouping the objects with random labels, nominal features having too many nominal attributes. In addition, the size constraint on groups is necessary. These conditions lead to a mixed integer optimization problem that is neither convex nor linear. It is an NP-hard problem, and exact solution methods are computationally costly. Our motivation to solve such a problem comes along with grouping the insurance data, which is essential for fair pricing. The proposed algorithm includes two phases. First, we rank random labels using fuzzy numbers. Afterwards, an adjusted -means algorithm is used to produce the homogenous groups satisfying a cluster size constraint. Fuzzy numbers are used to compare random labels, in both the observed values and their chance of occurrence. Moreover, an index is defined to find the similarity of multi-valued attributes without perfect information with those accompanied with perfect information. Since all ranks are scaled into the interval , the result of ranking random labels does not require rescaling techniques. In the adjusted K-means algorithm, the optimum number of clusters is found using the coefficient of variation instead of the Euclidean distance. Experiments demonstrate that our proposed algorithm produces fairly homogenous and significantly different groups having the requisite mass.
In deterministic DEA models, precise values are assigned to input and output data while they are intrinsically subjected to some degree of uncertainty. Most studies in this area are based on the assumption that inputs and outputs are equipped with some pre-known knowledge that enables one to use probability theory or fuzzy theory. In the lack of such data, one has to trust on the experts’ opinions, which can be considered as a sort of uncertainty. In this situation, the axiomatic approach of uncertainty theory initiated by Liu (Uncertainty theory. Berlin: Springer, 2007) could be an adequate powerful tool.Applying this theory,Wen et al. (J Appl Math, 2014; Soft Comput 1987–1996, 2015) suggested an uncertain DEA model while it has the disadvantage of pessimism. In this paper,we introduce another uncertain DEA
model with the objective of acquiring the highest belief degree that the evaluated DMU is efficient.We also apply this model in ranking of the evaluated DMUs. Implementation of the model on different illustrative examples reveals that the ranks of DMUs are almost-stable
in our model. This observation states that the rank of a DMU may roughly alternate with respect to the variation of minimum belief degrees. Our proposed model also compensates the rather optimistic point of view in the Wen et al.model that identifies all DMUs as efficient for higher belief degrees.