Informatica

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.

A new heuristic algorithm for solution of bi-objective discrete competitive facility location problems is developed and experimentally investigated by solving different instances of a facility location problem for firm expansion. The proposed algorithm is based on ranking of candidate locations for the new facilities, where rank values are dynamically adjusted with respect to behaviour of the algorithm. Results of the experimental investigation show that the proposed algorithm is suitable for the latter facility location problems and provides good results in sense of accuracy of the approximation of the true Pareto front.

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.