Problemi di taglio minimo con vincoli di cardinalità
Random matching problems on the complete graph.
Realization of Knapsack Problem Solving Algorithm and some of Its Applications
Rectifiable sets and the Traveling Salesman Problem.
RedInv-SA : a simulated annealing for the quadratic assignment problem
Redinv-SA: la simulated annealing for the quadratic assignment problem
An algebraic and combinatorial approach to the study of the Quadratic Assignment Problem produced theoretical results that can be applied to (meta) heuristics to give them information about the problem structure, allowing the construction of algorithms. In this paper those results were applied to inform a Simulated Annealing-type heuristic (which we called RedInv-SA). Some results from tests with known literature instances are presented.
Reducing Off-Line to On-Line: an Example and Its Applications
Reformulations in Mathematical Programming: Definitions and Systematics
A reformulation of a mathematical program is a formulation which shares some properties with, but is in some sense better than, the original program. Reformulations are important with respect to the choice and efficiency of the solution algorithms; furthermore, it is desirable that reformulations can be carried out automatically. Reformulation techniques are widespread in mathematical programming but interestingly they have never been studied under a unified framework. This paper attempts to move...
Semi-definite positive programming relaxations for graph K-coloring in frequency assignment
In this paper we will describe a new class of coloring problems, arising from military frequency assignment, where we want to minimize the number of distinct -uples of colors used to color a given set of -complete-subgraphs of a graph. We will propose two relaxations based on Semi-Definite Programming models for graph and hypergraph coloring, to approximate those (generally) NP-hard problems, as well as a generalization of the works of Karger et al. for hypergraph coloring, to find good feasible...
Semi-Definite positive Programming Relaxations for Graph Kn-Coloring in Frequency Assignment
In this paper we will describe a new class of coloring problems, arising from military frequency assignment, where we want to minimize the number of distinct n-uples of colors used to color a given set of n-complete-subgraphs of a graph. We will propose two relaxations based on Semi-Definite Programming models for graph and hypergraph coloring, to approximate those (generally) NP-hard problems, as well as a generalization of the works of Karger et al. for hypergraph coloring, to find good feasible...
Semidefinite programming and combinatorial optimization.
Semidefinite Relaxations of The Traveling Salesman Problem
Set-theoretical properties of extreme combinatorial problems.
Simple counter examples for the unsolvability of the Fermat- and Steiner-Weber-problem by compass and ruler.
Simulated annealing algorithm for the minimum weighted perfect euclidean matching problem
Simulated annealing with time-dependent energy function.
Simultaneous solution of linear equations and inequalities in max-algebra
Let and for . Max-algebra is an analogue of linear algebra developed on the pair of operations extended to matrices and vectors. The system of equations and inequalities have each been studied in the literature. We consider a problem consisting of these two systems and present necessary and sufficient conditions for its solvability. We also develop a polynomial algorithm for solving max-linear program whose constraints are max-linear equations and inequalities.
Solution of a fractional combinatorial optimization problem by mixed integer programming
Fractionnal mathematical programs appear in numerous operations research, computer science and economic domains. We consider in this paper the problem of maximizing the sum of 0–1 hyperbolic ratios (SRH). In contrast to the single ratio problem, there has been little work in the literature concerning this problem. We propose two mixed-integer linear programming formulations of SRH and develop two different strategies to solve them. The first one consists in using directly a general-purpose mixed-integer...
Solving a permutation problem by a fully polynomial-time approximation scheme
For a problem of optimal discrete control with a discrete control set composed of vertices of an n-dimensional permutohedron, a fully polynomial-time approximation scheme is proposed.
Solving the Crop Allocation Problem using Hard and Soft Constraints
Application tools for the crop allocation problem (CAP) are required for agricultural advisors to design more efficient farming systems. Despite the extensive treatment of this issue by agronomists in the past, few methods tackle the crop allocation problem considering both the spatial and the temporal aspects of the CAP. In this paper, we precisely propose an original formulation addressing the crop allocation planning problem while taking farmers’ management choices into account. These choices...