**Commenced**in January 2007

**Frequency:**Monthly

**Edition:**International

**Paper Count:**3494

# Search results for: Unbounded Knapsack Problem

##### 3494 Centre Of Mass Selection Operator Based Meta-Heuristic For Unbounded Knapsack Problem

**Authors:**
D.Venkatesan,
K.Kannan,
S. Raja Balachandar

**Abstract:**

In this paper a new Genetic Algorithm based on a heuristic operator and Centre of Mass selection operator (CMGA) is designed for the unbounded knapsack problem(UKP), which is NP-Hard combinatorial optimization problem. The proposed genetic algorithm is based on a heuristic operator, which utilizes problem specific knowledge. This center of mass operator when combined with other Genetic Operators forms a competitive algorithm to the existing ones. Computational results show that the proposed algorithm is capable of obtaining high quality solutions for problems of standard randomly generated knapsack instances. Comparative study of CMGA with simple GA in terms of results for unbounded knapsack instances of size up to 200 show the superiority of CMGA. Thus CMGA is an efficient tool of solving UKP and this algorithm is competitive with other Genetic Algorithms also.

**Keywords:**
Genetic Algorithm,
Unbounded Knapsack Problem,
Combinatorial Optimization,
Meta-Heuristic,
Center of Mass

##### 3493 The Knapsack Sharing Problem: A Tree Search Exact Algorithm

**Authors:**
Mhand Hifi,
Hedi Mhalla

**Abstract:**

In this paper, we study the knapsack sharing problem, a variant of the well-known NP-Hard single knapsack problem. We investigate the use of a tree search for optimally solving the problem. The used method combines two complementary phases: a reduction interval search phase and a branch and bound procedure one. First, the reduction phase applies a polynomial reduction strategy; that is used for decomposing the problem into a series of knapsack problems. Second, the tree search procedure is applied in order to attain a set of optimal capacities characterizing the knapsack problems. Finally, the performance of the proposed optimal algorithm is evaluated on a set of instances of the literature and its runtime is compared to the best exact algorithm of the literature.

**Keywords:**
Branch and bound,
combinatorial optimization,
knap¬sack,
knapsack sharing,
heuristics,
interval reduction.

##### 3492 The Multi-scenario Knapsack Problem: An Adaptive Search Algorithm

**Authors:**
Mhand Hifi,
Hedi Mhalla,
Mustapha Michaphy

**Abstract:**

In this paper, we study the multi-scenario knapsack problem, a variant of the well-known NP-Hard single knapsack problem. We investigate the use of an adaptive algorithm for solving heuristically the problem. The used method combines two complementary phases: a size reduction phase and a dynamic 2- opt procedure one. First, the reduction phase applies a polynomial reduction strategy; that is used for reducing the size problem. Second, the adaptive search procedure is applied in order to attain a feasible solution Finally, the performances of two versions of the proposed algorithm are evaluated on a set of randomly generated instances.

**Keywords:**
combinatorial optimization,
max-min optimization,
knapsack,
heuristics,
problem reduction

##### 3491 A New Knapsack Public-Key Cryptosystem Based on Permutation Combination Algorithm

**Authors:**
Min-Shiang Hwang,
Cheng-Chi Lee,
Shiang-Feng Tzeng

**Abstract:**

**Keywords:**
Public key,
Knapsack problem,
Knapsack cryptosystem,
low-density attack.

##### 3490 A Comparison of Exact and Heuristic Approaches to Capital Budgeting

**Authors:**
Jindřiška Šedová,
Miloš Šeda

**Abstract:**

**Keywords:**
Capital budgeting,
knapsack problem,
GAMS,
heuristic method,
genetic algorithm.

##### 3489 An Enhanced Cryptanalytic Attack on Knapsack Cipher using Genetic Algorithm

**Authors:**
Poonam Garg,
Aditya Shastri,
D.C. Agarwal

**Abstract:**

**Keywords:**
Genetic Algorithm,
Knapsack cipher,
Key search.

##### 3488 A New Heuristic Approach for Large Size Zero-One Multi Knapsack Problem Using Intercept Matrix

**Authors:**
K. Krishna Veni,
S. Raja Balachandar

**Abstract:**

This paper presents a heuristic to solve large size 0-1 Multi constrained Knapsack problem (01MKP) which is NP-hard. Many researchers are used heuristic operator to identify the redundant constraints of Linear Programming Problem before applying the regular procedure to solve it. We use the intercept matrix to identify the zero valued variables of 01MKP which is known as redundant variables. In this heuristic, first the dominance property of the intercept matrix of constraints is exploited to reduce the search space to find the optimal or near optimal solutions of 01MKP, second, we improve the solution by using the pseudo-utility ratio based on surrogate constraint of 01MKP. This heuristic is tested for benchmark problems of sizes upto 2500, taken from literature and the results are compared with optimum solutions. Space and computational complexity of solving 01MKP using this approach are also presented. The encouraging results especially for relatively large size test problems indicate that this heuristic can successfully be used for finding good solutions for highly constrained NP-hard problems.

**Keywords:**
0-1 Multi constrained Knapsack problem,
heuristic,
computational complexity,
NP-Hard problems.

##### 3487 Exponential Stability of Periodic Solutions in Inertial Neural Networks with Unbounded Delay

**Authors:**
Yunquan Ke,
Chunfang Miao

**Abstract:**

In this paper, the exponential stability of periodic solutions in inertial neural networks with unbounded delay are investigated. First, using variable substitution the system is transformed to first order differential equation. Second, by the fixed-point theorem and constructing suitable Lyapunov function, some sufficient conditions guaranteeing the existence and exponential stability of periodic solutions of the system are obtained. Finally, two examples are given to illustrate the effectiveness of the results.

**Keywords:**
Inertial neural networks,
unbounded delay,
fixed-point theorem,
Lyapunov function,
periodic solutions,
exponential stability.

##### 3486 Decision Support System for Suppliers

**Authors:**
Babak Tashakori Bafghi,
Laleh Tashakori,
Reza Allahyari Soeini,
Mohammad Mokhtari

**Abstract:**

Supplier selection is a multi criteria decision-making process that comprises tangible and intangible factors. The majority of previous supplier selection techniques do not consider strategic perspective. Besides, uncertainty is one of the most important obstacles in supplier selection. For the first, time in this paper, the idea of the algorithm " Knapsack " is used to select suppliers Moreover, an attempt has to be made to take the advantage of a simple numerical method for solving model .This is an innovation to resolve any ambiguity in choosing suppliers. This model has been tried in the suppliers selected in a competitive environment and according to all desired standards of quality and quantity to show the efficiency of the model, an industry sample has been uses.

**Keywords:**
Knapsack,
linear programming,
supplier select,
supply chain management.

##### 3485 Data Collection with Bounded-Sized Messages in Wireless Sensor Networks

**Authors:**
Min Kyung An

**Abstract:**

**Keywords:**
Data collection,
collision-free,
interference-free,
physical interference model,
SINR,
approximation,
bounded-sized
message model,
wireless sensor networks,
WSN.

##### 3484 Exponential Stability of Linear Systems under a Class of Unbounded Perturbations

**Authors:**
Safae El Alaoui,
Mohamed Ouzahra

**Abstract:**

In this work, we investigate the exponential stability of a linear system described by x˙ (t) = Ax(t) − ρBx(t). Here, A generates a semigroup S(t) on a Hilbert space, the operator B is supposed to be of Desch-Schappacher type, which makes the investigation more interesting in many applications. The case of Miyadera-Voigt perturbations is also considered. Sufficient conditions are formulated in terms of admissibility and observability inequalities and the approach is based on some energy estimates. Finally, the obtained results are applied to prove the uniform exponential stabilization of bilinear partial differential equations.

**Keywords:**
Exponential stabilization,
unbounded operator,
Desch-Schappacher,
Miyadera-Voigt operator.

##### 3483 Some Rotational Flows of an Incompressible Fluid of Variable Viscosity

**Authors:**
Rana Khalid Naeem,
Waseem Ahmed Khan,
Muhammad Akhtar,
Asif Mansoor

**Abstract:**

The Navier Stokes Equations (NSE) for an incompressible fluid of variable viscosity in the presence of an unknown external force in Von-Mises system x,\ are transformed, and some new exact solutions for a class of flows characterized by equation y f x a\b for an arbitrary state equation are determined, where f x is a function, \ the stream function, a z 0 and b are the arbitrary constants. In three, out of four cases, the function f x is arbitrary, and the solutions are the solutions of the flow equations for all the flows characterized by the equationy f x a\b. Streamline patterns for some forms of f x in unbounded and bounded regions are given.

**Keywords:**
Bounded and unbounded region,
Exact solution,
Navier Stokes equations,
Streamline pattern,
Variable viscosity,
Von- Mises system

##### 3482 Iterative Methods for An Inverse Problem

**Authors:**
Minghui Wang,
Shanrui Hu

**Abstract:**

An inverse problem of doubly center matrices is discussed. By translating the constrained problem into unconstrained problem, two iterative methods are proposed. A numerical example illustrate our algorithms.

**Keywords:**
doubly center matrix,
electric network theory,
iterative methods,
least-square problem.

##### 3481 On Analysis of Boundness Property for ECATNets by Using Rewriting Logic

**Authors:**
Noura Boudiaf,
Allaoua Chaoui

**Abstract:**

**Keywords:**
ECATNets,
Rewriting Logic,
Maude,
Finite-stateSystems,
Infinite-state Systems,
Boundness Property Checking.

##### 3480 Evolutionary Search Techniques to Solve Set Covering Problems

**Authors:**
Darwin Gouwanda,
S. G. Ponnambalam

**Abstract:**

**Keywords:**
Set covering problem,
genetic algorithm,
ant colony
optimization,
LINGO.

##### 3479 Bi-linear Complementarity Problem

**Authors:**
Chao Wang,
Ting-Zhu Huang Chen Jia

**Abstract:**

In this paper, we propose a new linear complementarity problem named as bi-linear complementarity problem (BLCP) and the method for solving BLCP. In addition, the algorithm for error estimation of BLCP is also given. Numerical experiments show that the algorithm is efficient.

**Keywords:**
Bi-linear complementarity problem,
Linear complementarity
problem,
Extended linear complementarity problem,
Error
estimation,
P-matrix,
M-matrix.

##### 3478 A Method for Solving a Bi-Objective Transportation Problem under Fuzzy Environment

**Authors:**
Sukhveer Singh,
Sandeep Singh

**Abstract:**

A bi-objective fuzzy transportation problem with the objectives to minimize the total fuzzy cost and fuzzy time of transportation without according priorities to them is considered. To the best of our knowledge, there is no method in the literature to find efficient solutions of the bi-objective transportation problem under uncertainty. In this paper, a bi-objective transportation problem in an uncertain environment has been formulated. An algorithm has been proposed to find efficient solutions of the bi-objective transportation problem under uncertainty. The proposed algorithm avoids the degeneracy and gives the optimal solution faster than other existing algorithms for the given uncertain transportation problem.

**Keywords:**
Transportation problem,
efficient solution,
ranking function,
fuzzy transportation problem.

##### 3477 Bee Colony Optimization Applied to the Bin Packing Problem

**Authors:**
Kenza Aida Amara,
Bachir Djebbar

**Abstract:**

**Keywords:**
Bee colony optimization,
bin packing,
heuristic algorithm,
pretreatment.

##### 3476 Modeling Language for Machine Learning

**Authors:**
Tsuyoshi Okita,
Tatsuya Niwa

**Abstract:**

**Keywords:**
Formal language,
statistical inference problem,
reduction.

##### 3475 Transformation of Course Timetablinng Problem to RCPSP

**Authors:**
M. Ahmad,
M. Gourgand,
C. Caux

**Abstract:**

**Keywords:**
Course Timetabling,
Integer programming,
Combinatorial optimizations

##### 3474 How to Build and Evaluate a Solution Method: An Illustration for the Vehicle Routing Problem

**Authors:**
Nicolas Zufferey

**Abstract:**

The vehicle routing problem (VRP) is a famous combinatorial optimization problem. Because of its well-known difficulty, metaheuristics are the most appropriate methods to tackle large and realistic instances. The goal of this paper is to highlight the key ideas for designing VRP metaheuristics according to the following criteria: efficiency, speed, robustness, and ability to take advantage of the problem structure. Such elements can obviously be used to build solution methods for other combinatorial optimization problems, at least in the deterministic field.

**Keywords:**
Vehicle routing problem,
Metaheuristics,
Combinatorial optimization.

##### 3473 Seat Assignment Problem Optimization

**Authors:**
Mohammed Salem Alzahrani

**Abstract:**

**Keywords:**
Assignment Problem,
Hungarian Method,
Least Cost
Method,
Northwest Corner Method,
Seat Assignment Method
(SAM),
A Real Word Assignment Problem.

##### 3472 A Deterministic Polynomial-time Algorithm for the Clique Problem and the Equality of P and NP Complexity Classes

**Authors:**
Zohreh O. Akbari

**Abstract:**

**Keywords:**
Clique problem,
Deterministic Polynomial-time
Algorithm,
Equality of P and NP Complexity Classes.

##### 3471 Optimization by Ant Colony Hybryde for the Bin-Packing Problem

**Authors:**
Ben Mohamed Ahemed Mohamed,
Yassine Adnan

**Abstract:**

The problem of bin-packing in two dimensions (2BP) consists in placing a given set of rectangular items in a minimum number of rectangular and identical containers, called bins. This article treats the case of objects with a free orientation of 90Ôùª. We propose an approach of resolution combining optimization by colony of ants (ACO) and the heuristic method IMA to resolve this NP-Hard problem.

**Keywords:**
Ant colony algorithm,
bin-packing problem,
heuristics methods.

##### 3470 Optimal Facility Layout Problem Solution Using Genetic Algorithm

**Authors:**
Maricar G. Misola,
Bryan B. Navarro

**Abstract:**

Facility Layout Problem (FLP) is one of the essential problems of several types of manufacturing and service sector. It is an optimization problem on which the main objective is to obtain the efficient locations, arrangement and order of the facilities. In the literature, there are numerous facility layout problem research presented and have used meta-heuristic approaches to achieve optimal facility layout design. This paper presented genetic algorithm to solve facility layout problem; to minimize total cost function. The performance of the proposed approach was verified and compared using problems in the literature.

**Keywords:**
Facility Layout Problem,
Genetic Algorithm,
Material Handling Cost,
Meta-heuristic Approach.

##### 3469 Solving the Teacher Assignment-Course Scheduling Problem by a Hybrid Algorithm

**Authors:**
Aldy Gunawan,
Kien Ming Ng,
Kim Leng Poh

**Abstract:**

This paper presents a hybrid algorithm for solving a timetabling problem, which is commonly encountered in many universities. The problem combines both teacher assignment and course scheduling problems simultaneously, and is presented as a mathematical programming model. However, this problem becomes intractable and it is unlikely that a proven optimal solution can be obtained by an integer programming approach, especially for large problem instances. A hybrid algorithm that combines an integer programming approach, a greedy heuristic and a modified simulated annealing algorithm collaboratively is proposed to solve the problem. Several randomly generated data sets of sizes comparable to that of an institution in Indonesia are solved using the proposed algorithm. Computational results indicate that the algorithm can overcome difficulties of large problem sizes encountered in previous related works.

**Keywords:**
Timetabling problem,
mathematical programming
model,
hybrid algorithm,
simulated annealing.

##### 3468 Stochastic Programming Model for Power Generation

**Authors:**
Takayuki Shiina

**Abstract:**

**Keywords:**
electric power capacity expansion problem,
integerprogramming,
L-shaped method,
stochastic programming

##### 3467 On Optimum Stratification

**Authors:**
M. G. M. Khan,
V. D. Prasad,
D. K. Rao

**Abstract:**

In this manuscript, we discuss the problem of determining the optimum stratification of a study (or main) variable based on the auxiliary variable that follows a uniform distribution. If the stratification of survey variable is made using the auxiliary variable it may lead to substantial gains in precision of the estimates. This problem is formulated as a Nonlinear Programming Problem (NLPP), which turn out to multistage decision problem and is solved using dynamic programming technique.

**Keywords:**
Auxiliary variable,
Dynamic programming technique,
Nonlinear programming problem,
Optimum stratification,
Uniform distribution.

##### 3466 Enhanced Traveling Salesman Problem Solving by Genetic Algorithm Technique (TSPGA)

**Authors:**
Buthainah Fahran Al-Dulaimi,
Hamza A. Ali

**Abstract:**

The well known NP-complete problem of the Traveling Salesman Problem (TSP) is coded in genetic form. A software system is proposed to determine the optimum route for a Traveling Salesman Problem using Genetic Algorithm technique. The system starts from a matrix of the calculated Euclidean distances between the cities to be visited by the traveling salesman and a randomly chosen city order as the initial population. Then new generations are then created repeatedly until the proper path is reached upon reaching a stopping criterion. This search is guided by a solution evaluation function.

**Keywords:**
Genetic algorithms,
traveling salesman problem solving,
optimization.

##### 3465 Two-Stage Approach for Solving the Multi-Objective Optimization Problem on Combinatorial Configurations

**Authors:**
Liudmyla Koliechkina,
Olena Dvirna

**Abstract:**

**Keywords:**
Discrete set,
linear combinatorial optimization,
multi-objective optimization,
multipermutation,
Pareto solutions,
partial permutation set,
permutation,
structural graph.