Non-convex min-max fractional quadratic problems under quadratic constraints: copositive relaxations

In this paper we address a min-max problem of fractional quadratic (not necessarily convex) over linear functions on a feasible set described by linear and (not necessarily convex) quadratic functions. We propose a conic reformulation on the cone of completely positive matrices. By relaxation, a doubly non negative conic formulation is used to provide lower … Read more

Compromise Ratio with weighting functions in a Tabu Search multi-criteria approach to examination timetabling

University examination scheduling is a difficult and heavily administrative task, particularly when the number of students and courses is high. Changes in educational paradigms, an increase in the number of students, the aggregation of schools, more flexible curricula, among others, are responsible for an increase in the difficulty of the problem. As a consequence, there … Read more

Copositivity-based approximations for mixed-integer fractional quadratic optimization

We propose a copositive reformulation of the mixed-integer fractional quadratic problem (MIFQP) under general linear constraints. This problem class arises naturally in many applications, e.g., for optimizing communication or social networks, or studying game theory problems arising from genetics. It includes several APX-hard subclasses: the maximum cut problem, the $k$-densest subgraph problem and several of … Read more

Copositivity and constrained fractional quadratic problems

We provide Completely Positive and Copositive Programming formulations for the Constrained Fractional Quadratic Problem (CFQP) and Standard Fractional Quadratic Problem (StFQP). Based on these formulations, Semidefinite Programming (SDP) relaxations are derived for finding good lower bounds to these fractional programs, which are used in a global optimization branch-and-bound approach. Applications of the CFQP and StFQP, … Read more