A Smart Structural Algorithm (SSA) Based on Infeasible Region to Solve Mixed Integer Problems

A Smart Structural Algorithm (SSA) Based on Infeasible Region to Solve Mixed Integer Problems

Mohammad Hassan Salmani (Sharif University of Technology, Tehran, Iran) and Kourosh Eshghi (Sharif University of Technology, Tehran, Iran)
Copyright: © 2017 |Pages: 21
DOI: 10.4018/IJAMC.2017010102

Abstract

Optimization is an important fields of study in science where researchers seek to make the best and most practical decisions. Solving real optimization problems is an intractable issue which calls for generating an approximate using meta-heuristic algorithms. This study proposes a meta-heuristic algorithm which mainly searches the infeasible region. In this approach, the authors start from an infeasible solution, and while they try to get near to the feasible region, they ensure that the best value is kept for the objective function. The algorithm examines the space in such terms as Infeasibility and Objective Functions, Neighborhood Limited Area, Random Smart Points, and the calculation of new solutions. The algorithm can convert an infeasible solution to an appropriate corresponding feasible solution by applying a simple mathematical methodology. Finally, to test the efficiency of our algorithm, a sample random MIP problem and a hard benchmark TSP instance are solved and discussed in detail.
Article Preview

1. Introduction

Optimization, as a field of study, has generated considerable interest and enthusiasm among scholars. This interest has, in turn, given rise to novel contributions to the field. A major part of the relevant literature has focused on solving methods of optimization problems including exact and approximate methods. It would be no exaggeration to claim that although developing concise, comprehensive, and effective mathematical models is an important issue, it is solving these models that has featured more prominently in the literature. A quick glance at the literature of optimization suggests that various methods have been proposed to develop optimization algorithms to decrease the running time (or complexity) of the algorithms and generate an appropriate final solution for optimization problems.

On the other hand, there are several problems and mathematical models that cannot be solved in a reasonable time using exact solving techniques (Hürlimann, 1999). Therefore, we need to change our attitude toward approximate algorithms in order to develop new approaches to generating appropriate solutions which are not necessarily global optima. Though there is no shortage of publications using meta-heuristic methods and touting them as innovative, novel, and highly efficient, many of them are flawed one way or another – vagueness, lack of conceptual elaboration, poor and ill-conceived experiments, and failure to mention the related literature are some of the problems undermining the quality and authenticity of those studies (Sörensen, 2013).

In general, most meta-heuristics are characterized by some properties, the most important of which are as follows (Blum & Roli, 2003):

  • Meta-heuristics are strategies that guide the search process.

  • The goal is to efficiently explore the search region in order to find near–optimal solutions.

  • Techniques which constitute meta-heuristic algorithms range from simple local search procedures to complex learning processes.

  • Meta-heuristic algorithms are approximate and usually non-deterministic.

  • Meta-heuristics are not problem-specific.

In the past couple of decades, a great number of articles have been written proposing different models and algorithms for optimization problems. However, none of them has paid attention to the infeasible region for solving the mathematical models. In other words, instead of feasible areas, we can develop an algorithm which starts to investigate infeasible areas while at the same time it tries to improve the objective function and get closer to the feasible region on the convex hull.

Searching in infeasible areas has considerable advantages. For one thing, we would not get caught in the local optimum points and, consequently, we would be presented with a wide region to search the space. For another, we can apply diverse search strategies for different points of the area. To clarify it, assume that we are searching for a person in a small alley. It is obvious that we need to use a completely different search approach compared to when we are searching for a person in a town. It means that based on the probability of including the optimum solution, we need to have different spaces and different moving steps.

Overall, this paper is structured as follows. To begin with, a concise and comprehensive review of relevant literature is given. The study, then, moves on to present particular basic definitions for the developed algorithms. This is followed by proposing the body of the algorithm in section four. Finally, computational results are presented and the major findings of the paper are summed up in the conclusion.

2. Literature Review

Several classifications of solving methods of optimization problems can be found in the literature. One of the most important ones is shown in Figure 1 (Talbi, 2009). As it can be seen in Figure 1, approximate methods which constitute the main part of this paper are juxtaposed with exact methods.

Figure 1.

A general assortment for solving methods

Complete Article List

Search this Journal:
Reset
Open Access Articles: Forthcoming
Volume 10: 4 Issues (2019): Forthcoming, Available for Pre-Order
Volume 9: 4 Issues (2018)
Volume 8: 4 Issues (2017)
Volume 7: 4 Issues (2016)
Volume 6: 4 Issues (2015)
Volume 5: 4 Issues (2014)
Volume 4: 4 Issues (2013)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing