Multivariable branching: A 0-1 knapsack problem case study

We explore the benefits of multi-variable branching strategies for linear programming based branch and bound algorithms for the 0-1 knapsack problem, i.e., of branching on sets of variables rather than on a single variable (the current default in integer programming solvers). We present examples where multi-variable branching shows advantage over single-variable branching, and partially characterize … Read more

Exact Solution Methods for the hBcitem Quadratic Knapsack Problem

The purpose of this paper is to solve the 0-1 k-item quadratic knapsack problem (kQKP), a problem of maximizing a quadratic function subject to two linear constraints.We propose an exact method based on semide nite optimization. The semide nite relaxation used in our approach includes simple rank one constraints, which can be handled efficiently by interior point … Read more

Optimization Methods for Disease Prevention and Epidemic Control

This paper investigates problems of disease prevention and epidemic control (DPEC), in which we optimize two sets of decisions: (i) vaccinating individuals and (ii) closing locations, given respective budgets with the goal of minimizing the expected number of infected individuals after intervention. The spread of diseases is inherently stochastic due to the uncertainty about disease … Read more

On implementation of local search and genetic algorithm techniques for some combinatorial optimization problems

In this paper we propose the approach to solving several combinatorial optimization problems using local search and genetic algorithm techniques. Initially this approach was developed in purpose to overcome some difficulties inhibiting the application of above-mentioned techniques to the problems of the Questionnaire Theory. But when the algorithms were developed it became clear that them … Read more