Non delayed relax-and-cut algorithms
A Lucena - Annals of Operations Research, 2005 - Springer
Attempts to allow exponentially many inequalities to be candidates to Lagrangian
dualization date from the early 1980's. In this paper, the term Relax-and-Cut, introduced …
dualization date from the early 1980's. In this paper, the term Relax-and-Cut, introduced …
The salesman and the tree: the importance of search in CP
The traveling salesman problem (TSP) is a challenging optimization problem for CP and OR
that has many industrial applications. Its generalization to the degree constrained minimum …
that has many industrial applications. Its generalization to the degree constrained minimum …
[HTML][HTML] A relax-and-cut algorithm for the prize-collecting Steiner problem in graphs
Given an undirected graph G with penalties associated with its vertices and costs associated
with its edges, a Prize Collecting Steiner (PCS) tree is either an isolated vertex of G or else …
with its edges, a Prize Collecting Steiner (PCS) tree is either an isolated vertex of G or else …
[HTML][HTML] The min-degree constrained minimum spanning tree problem: Formulations and Branch-and-cut algorithm
LC Martinez, AS Da Cunha - Discrete Applied Mathematics, 2014 - Elsevier
Given an edge weighted undirected graph G and a positive integer d, the Min-Degree
Constrained Minimum Spanning Tree Problem (MDMST) consists of finding a minimum cost …
Constrained Minimum Spanning Tree Problem (MDMST) consists of finding a minimum cost …
Branch-and-cut-and-price algorithms for the degree constrained minimum spanning tree problem
LH Bicalho, AS Da Cunha, A Lucena - Computational Optimization and …, 2016 - Springer
Assume that a connected undirected edge weighted graph G is given. The Degree
Constrained Minimum Spanning Tree Problem (DCMSTP) asks for a minimum cost …
Constrained Minimum Spanning Tree Problem (DCMSTP) asks for a minimum cost …
NeuroPrim: An attention-based model for solving NP-hard spanning tree problems
Y Shi, C Han, T Guo - Science China Mathematics, 2024 - Springer
Spanning tree problems with specialized constraints can be difficult to solve in real-world
scenarios, often requiring intricate algorithmic design and exponential time. Recently, there …
scenarios, often requiring intricate algorithmic design and exponential time. Recently, there …
Min-degree constrained minimum spanning tree problem with fixed centrals and terminals: Complexity, properties and formulations
We consider a variant of the Min-Degree Constrained Minimum Spanning Tree Problem
where the central and terminal nodes are fixed a priori. We prove that the optimization …
where the central and terminal nodes are fixed a priori. We prove that the optimization …
Lagrangian heuristics for the quadratic knapsack problem
This paper investigates two Lagrangian heuristics for the Quadratic Knapsack Problem.
They originate from distinct linear reformulations of the problem and follow the traditional …
They originate from distinct linear reformulations of the problem and follow the traditional …
Mathematical models to reconstruct phylogenetic trees under the minimum evolution criterion
A basic problem in molecular biology is to rebuild phylogenetic trees (PT) from a set of DNA
or protein sequences. Among different criteria used for this purpose, the minimum evolution …
or protein sequences. Among different criteria used for this purpose, the minimum evolution …
Exact algorithms for the vertex separator problem in graphs
CC de Souza, VF Cavalcante - Networks, 2011 - Wiley Online Library
In this article, we propose a Lagrangian relaxation framework to solve the vertex separator
problem (VSP). This framework is based on the development of relax‐and‐cut algorithms …
problem (VSP). This framework is based on the development of relax‐and‐cut algorithms …