We present a branch-and-bound framework to solve the following problem: Given a graph G and an integer k, find a subgraph of G formed by removing no more than k edges that contains the most symmetry. We call symmetries on such a subgraph “almost symmetries” of G. We implement our branch-and-bound framework in PEBBL to … Read more
In this paper, we address a new version of the Uncapacitated Single Allocation p-Hub Median Problem (USApHMP) in which transportation costs on each edge are given by piecewise constant cost functions. In the classical USApHMP, transportation costs are modelled as linear functions of the transport volume, where a fixed discount factor on hub-hub connections is … Read more
Recently, there have been many successful applications of optimization algorithms that solve a sequence of quite similar mixed-integer programs (MIPs) as subproblems. Traditionally, each problem in the sequence is solved from scratch. In this paper we consider reoptimization techniques that try to benefit from information obtained by solving previous problems of the sequence. We focus … Read more
We study the Knapsack Problem with Conflict Graph (KPCG), an extension of the 0-1 Knapsack Problem, in which a conflict graph describing incompatibilities between items is given. The goal of the KPCG is to select the maximum profit set of compatible items while satisfying the knapsack capacity constraint. We present a new Branch-and-Bound approach to … Read more
We present a specialized branch-and-bound (b&b) algorithm for the Euclidean Steiner tree problem (ESTP) in R^n and apply it to a convex mixed-integer nonlinear programming (MINLP) formulation of the problem, presented by Fampa and Maculan. The algorithm contains procedures to avoid difficulties observed when applying a b&b algorithm for general MINLP problems to solve the … Read more
The p-facility Huff location problem aims at locating facilities on a competitive environment so as to maximize the market share. While it has been deeply studied in the field of continuous location, in this paper we study the p-facility Huff location problem on networks formulated as a Mixed Integer Nonlinear Programming problem that can be … Read more
Covering problems are well studied in the Operations Research literature under the assumption that both the set of users and the set of potential facilities are finite. In this paper we address the following variant, which leads to a Mixed Integer Nonlinear Program (MINLP): locations of p facilities are sought along the edges of a … Read more
This work deals with a Huff-like Stackelberg problem, where the leader facility wants to decide its location so that its profit is maximal after the competitor (the follower) also built its facility. It is assumed that the follower makes a rational decision, maximizing their profit. The inelastic demand is aggregated into the vertices of a … Read more
We show the importance of selecting good branching variables by exhibiting a family of instances for which an optimal solution is both trivial to find and provably optimal by a fixed-size branch-and-bound tree, but for which state-of-the-art Mixed Integer Programming solvers need an increasing amount of resources. The instances encode the edge-coloring problem on a … Read more
We propose a new method for solving univariate global optimization problems by combining a lower bound function of ®BB method (see [1]) with the lower bound function of the method developed in [4]. The new lower bound function is better than the two lower bound functions. We add the convex/concave test and pruning step which … Read more