integer programming

We exhibit a polynomial time algorithm that computes the Clar number of any nanotube. This algorithm can be easily extended to one that computes the Clar number of fullerene whose pentagon-clusters are all of even size.It is known that computing the Clar number of planar graphs is NP-hard. It is not known if computing the Clar number of fullerenes is a tractable problem. We show that the latter problem can be suitably approximated in polynomial time, and we also discuss the existence of fpt-algorithms for this important problem of Cheminformatics.

The inherent feature of real-world data is uncertainty. If data is generated in valid experiments or standard collections, probability theory or fuzzy theory is a powerful tool for analyzing them. But data is not always reliable, especially when it is not possible to perform a reliable test or data collection multiple times. In this situations, referring to the beliefs of experts in the field in question is an alternative approach and uncertainty theory is a tool by which the beliefs of experts can be mathematically incorporated into the problem-solving structure. In this paper, we investigate the finding minimum weighted maximal matching with uncertain weights. For this purpose, we offer two methods. In the first method, by introducing the concept of chance constraint, we obtain model with definite coefficients. The second method is based on the concept of uncertain expected value. Finally, a numerical example for these two methods is presented.

We consider a family of problems that combine network design and facility location. Such problems arise in many practical applications in different fields such as telecommunications, transportation networks, logistic, and energy supply networks. In facility location problems, we want to decide which facilities to open and how to assign clients to the open facilities so as to minimize the sum of the facility opening costs and client connection costs. These problems typically do not involve decisions concerning the routing of the clients’ demands to the open facilities; once we decided on the set of open facilities, each client is served by the closest open facility. In network design problems, on the other hand, we generally want to design and dimension a minimum-cost routing network providing sufficient capacities to route all clients’ demands to their destinations. These problems involve deciding on the routing of each client’s demand. But, in contrast to facility location problems, demands’ destinations are predetermined. In many modern day applications, however, all these decisions are interdependent and affect each other. Hence, they should be taken simultaneously. The aim of this work is to survey models, algorithmic approaches and methodologies concerning such combined network design facility location problems.

Linear Programming as a practical technique for solving optimization problems with linear objective functions and linear constraint plays an essential role in mathematical programming. Most of the real-world problems are included in inconsistent and astute uncertainty. That's why the optimal solution can't be found easily. The Neutrosophic theory, as an extension of fuzzy set theory, is a powerful instrument to handle inconsistent, indeterminate, and incomplete information. This paper presents an applied approach for solving Interval Neutrosophic Integer Programming problems. By using the proposed approach, we can handle both incomplete and indeterminate data. In this respect, using a ranking function, we present a technique to convert the Interval Neutrosophic Integer Programming problem into a crisp model and then solve it by standard methods.

Using fossil fuels in transportation sector has caused many environmental and economic problems. Therefore, the use of alternative fuel vehicles is necessary. Since such vehicles have limited fuel tank capacities, hence, frequent refueling is required. Regarding the possibility of the existence of different fuel costs in various refueling stations, the selection of suitable stations with the purpose of minimizing total cost of refueling is important. Moreover, minimizing the number of refuelings could be considered as another important criterion in refueling operations of a given trip. In this paper an integer bi-objective model is proposed to select suitable refueling stations considering two criteria of minimizing the total cost of refueling and minimizing the number of refuelings. To solve the proposed model, a new algorithm is suggested and its performance is compared with the weighted sum method of multi-objective optimization literature. The results show the superiority of the proposed solution approach.

Assigning available resources to fire stations is a main task of fire depart ment’s administrator in a city. The importance of this problem increases when the number of available resources are inadequate. In this situation, the goal is to assign the limited available resources to fire stations such that the associated penalties of the shortages are minimized. Here, we first give a mathematical approach to consider some penalties for the shortage. Next, we give an integer program to minimize the sum of associated penalties. The proposed model can be used in many other problems arisen from health services, emergency management, and so on. We also propose a heuristic to efficiently solve the problem in a reasonable time. Our proposed heuristic has two phases. In the first phase, using a greedy approach, our proposed heuristic constructs a proper feasible solution. Next, in the second phase, we propose a local search to improve the quality of the solution constructed in the first phase. To show the efficiency of our proposed heuristic, we com pare our proposed heuristic with CPLEX based on the running time and the quality of obtained solutions on two groups of problems (real-word problems and randomly generated problems). The numerical results show that on the 80% of benchmark problems, the obtained solution is the same as CPLEX’s solutions. Also, the running time of our proposed algorithm is almost 10 times better than CPLEX’s running time, in average.