Informatica

This paper studies a set of novel integrated scheduling problems by taking into account the combinatorial features of various groups, parallel-batching, deteriorating jobs, and time-dependent setup time simultaneously under the settings of both single-machine and parallel-machine, and the objective of the studied problems is to minimize the makespan. In order to solve the single-machine scheduling problem, we first investigate the structural properties on jobs sequencing, jobs batching, and batches sequencing for the optimal solution, and then develop a scheduling rule. Moreover, for solving the parallel-machine scheduling problem, we exploit the optimal structural properties and batching rule, and propose a novel hybrid AIS-VNS algorithm incorporating Artificial Immune System algorithm (AIS) and Variable Neighbourhood Search (VNS). Extensive computational experiments are conducted to evaluate the performance of the proposed AIS-VNS algorithm, and comparison results show that the proposed algorithm performs quite well in terms of both efficiency and solution quality.

This paper improves an infra-chromatic bound which is used by the exact branch-and-bound maximum clique solver BBMCX (San Segundo et al., 2015) as an upper bound on the clique number for every subproblem. The infra-chromatic bound looks for triplets of colour subsets which cannot contain a 3-clique. As a result, it is tighter than the bound obtained by widely used approximate-colouring algorithms because it can be lower than the chromatic number. The reported results show that our algorithm with the new bound significantly outperforms the state-of-the-art algorithms in a number of structured and uniform random graphs.

We propose a new hybrid approach to solve the unbounded integer knapsack problem (UKP), where valid inequalities are generated based on intermediate solutions of an equivalent forward dynamic programming formulation. These inequalities help tighten the initial LP relaxation of the UKP, and therefore improve the overall computational efficiency. We also extended this approach to solve the multi-dimensional unbounded knapsack problem (d-UKP). Computational results demonstrate the effectiveness of our approach on both problems.

In this paper, we propose a novel trust inference framework in the web-based scenarios which are assumed to have a Web of Trust pre-established, and take the contexts of the trust relationships into account when inferring the recommendation trust. For alleviating the problem of sparse matrix in the Web of Trust, we also incorporate the users’ profile and relationship information on the associated social networks into the framework. Based on the Web of Trust established in the discussed web-based scenario (i.e. epinions.com in this paper), and the social relationship information in the associated social networks, the users are classified into four classes. Then different information is used to infer the users’ recommendation trust value based on the classifications. The simulation experiments show that our approach has good coverage of inferred trust values, and the accurate rate of the predicted trust relationship is higher than the traditional PCC (Pearson Correlation Co-efficiency). According to the computation results of adjusted parameters, it can be concluded that the threshold which is used to filter the inferred trust values can be removed, i.e. all the inferred trust values should be kept.

In this paper, a novel approach involving the concepts from mathematical programming and number theory is proposed to find the D-optimal designs. In specific, we will propose a mathematical formulation for the D-optimal design. In addition to that, we will present the use of cyclotomic cosets in the mathematical formulation, in order to reduce the total number of binary variables. We will illustrate the validity of our proposed method by solving a difficult known instance (N=126) of the D-optimal design.

It is well known that, in general, exact algorithms for the Quadratic Assignment Problem (QAP) cannot solve problems of size N>15. Therefore, it is necessary to use heuristic approaches for solving large-scale QAPs. In this paper, we consider a class of heuristic approaches based on local search criteria. In particular, we selected four algorithms; CRAFT, Simulated Annealing, TABU search and the Graph Partitioning (GP) approach and studied their relative performance in terms of the quality of solutions and CPU times. All of these algorithms performed roughly the same, based on the results of two sets of test problems executed on an IBM ES/3090-600S computer.

In this paper, we present a new local search algorithm for solving the Quadratic Assignment Problem based on the Kernighan-Lin heuristic for the Graph Partitioning Problem. We also prove that finding a local optimum for the Quadratic Assignment Problem, with the neighborhood structure defined in the algorithm, is PLS-complete. The greatest advantages of the algorithm are its simplicity and speed in generating high quality solutions. The algorithm has been implemented and tested on an IBM 3090 computer with a variety of test problems of dimensions up to 100, including many test problems available in the literature and a new set of test problems with known optimal permutations.

In this paper, we discuss computational aspects of an interior-point algorithm [1] for indefinite quadratic programming problems with box constraints. The algorithm finds a local minimizer by successively solving indefinite quadratic problems with an ellipsoid constraint. In addition, we present a sufficient condition for a local minimizer to be global, and we use this result to generate test problems with a known global solution. The proposed algorithm has been implemented on an IBM 3090 computer and tested on a variety of dense test problems, including problems with a known global optimizer.