Publications

Export 15 results:
Sort by: Author Title Type [ Year  (Desc)]
2016
Salmerón, J. M. G., P. Amaral, L. G. Casado, E. M. T. Hendrix, and J. Žilinskas On Regular Simplex Refinement in Copositivity Detection. Global Optimization Workshop. Braga, 2016.
Amaral, Paula Alexandra, and Tiago Cardal Pais. "Compromise Ratio with weighting functions in a Tabu Search multi-criteria approach to examination timetabling." Computers and Operations Research (2016).
2015
Bomze, Immanuel, and Paula Alexandra Amaral. "Copositivity-based approximations for mixed-integer fractional quadratic optimization." Pacific Journal of Optimization. 11.2 (2015): 225-238.
2014
Amaral, P., I. Bomze, and J. Júdice. "Copositivity and constrained fractional quadratic problems." Mathematical Programming. 1.1 (2014): 1-26. Abstract

n/a

2012
Hendrix, Eligius M. T., Leocadio G. Casado, and Paula Amaral. "Global Optimization Simplex Bisection Revisited Based on Considerations by Reiner Horst." Lecture Notes in Computer Science - ICSSA2012 . 7335 (2012): 159-173. AbstractWebsite

In this paper, the use of non-optimality spheres in a simplicial branch and bound (B&B) algorithm is investigated. In this context, some considerations regarding the use of bisection on the longest edge in relation with ideas of Reiner Horst are reminded. Three arguments highlight the merits of bisection of simplicial subsets in B&B schemes.

Pais, Tiago, and Paula Amaral. "Managing the tabu list length using a fuzzy inference system: an application to examination timetabling." Annals of Operations Research. 194 (2012): 341-363. Abstract

In this paper, we present an application of Tabu Search (TS) to the examination timetabling problem. One of the drawbacks of this meta-heuristic is related to the need of tuning some parameter (like tabu tenure) whose value affects the performance of the algorithm. The importance of developing an automatic procedure is clear considering that most of the users of timetabling software, like academic staff, do not have the expertise to conduct such tuning. The goal of this paper is to present a method to automatically manage the memory in the TS using a Decision Expert System. More precisely a Fuzzy Inference Rule Based System (FIRBS) is implemented to handle the tabu tenure based on two concepts, ``Frequency" and ``Inactivity". These concepts are related respectively with the number of times a move is introduced in the tabu list and the last time (in number of iterations) the move was attempted and prevented by the tabu status. Computational results show that the implemented FIRBS handles well the tuning of the tabu status duration improving, as well, the performance of Tabu Search.

2009
Pais, Tiago Cardal, and Paula Amaral A Tabu Based Approach to the Exam Timetabling Problem. Livro de actas do Congresso da APDIO. Caparica -Portugal, 2009.
Amaral, P., L. M. Fernandes, J. Júdice, and H. D. Sherali. "On optimal zero-preserving corrections for inconsistent linear systems." Journal of Global Optimization. 45 (2009): 645-666. Abstract

This paper addresses the problem of finding an optimal correction of an inconsistent linear system, where only the nonzero coefficients of the constraint matrix are allowed to be perturbed for reconstructing a consistent system. Using the Frobenius norm as a measure of the distance to feasibility, a nonconvex minimization problem is formulated, whose objective function is a sum of fractional functions. A branch-and-bound algorithm for solving this nonconvex program is proposed, based on suitably overestimating the denominator function for computing lower bounds. Computational experience is presented to demonstrate the efficacy of this approach.

2008
Amaral, P., J. Júdice, and H. D. Sherali. "A reformulation–linearization–convexification algorithm for optimal correction of an inconsistent system of linear constraints." Computers and Operations Research. 35 (2008): 1494-1509. Abstract

In this paper, an algorithm is introduced to find an optimal solution for an optimization problem that arises in total least squares with inequality constraints, and in the correction of infeasible linear systems of inequalities. The stated problem is a nonconvex program with a special structure that allows the use of a reformulation–linearization–convexification technique for its solution. A branch–and–bound method for finding a global optimum for this problem is introduced based on this technique. Some computational experiments are included to highlight the efficacy of the proposed methodology.

2005
Amaral, P., and P. Barahona. "A Framework for Optimal Correction of Inconsistent Linear Constraints." Constraints. 10:1 (2005): 67-86. Abstract

The problem of inconsistency between constraints often arises in practice as the result, among others, of the complexity of real models or due to unrealistic requirements and preferences. To overcome such inconsistency two major actions may be taken: removal of constraints or changes in the coefficients of the model. This last approach, that can be generically described as ``model corre\-ction" is the problem we address in this paper in the context of linear constraints over the reals. The correction of the right hand side alone, which is very close to a fuzzy constraints approach, was one of the first proposals to deal with inconsistency, as it may be mapped into a linear problem. The correction of both the matrix of coefficients and the right hand side introduces non linearity in the constraints. The degree of difficulty in solving the problem of the optimal correction depends on the objective function, whose purpose is to measure the closeness between the original and corrected model. Contrary to other norms, that provide corrections with quite rigid patterns, the optimization of the important Frobenius norm was still an open problem. We have analyzed the problem using the KKT conditions and derived necessary and sufficient conditions which enabled us to unequivocally characterize local optima, in terms of the solution of the Total Least Squares and the set of active constraints. These conditions justify a set of pruning rules, which proved, in preliminary experimental results, quite successful in a tree search procedure for determining the global minimizer.

Amaral, P., and P. Barahona. "Connections between the total least squares and the correction of an infeasible system of linear inequalities." Linear Algebra and Applications. 395 (2005): 191-210. Abstract

Given an infeasible system of linear inequalities, $Ax łe b$, we \mbox{address} the problem of correcting both the matrix of coefficients $A$ by $A+H$ and vector $b$ by $b+p$ to minimize the Frobenius norm of $[H,p]$. For a system of linear equations this problem can be solved by an algebraic and well-studied method known as the Total Least Squares. For inequalities, Vatolin \cite{Vato86} was the first to approach this problem, presenting a result with necessary and sufficient conditions for local minimizers. Unfortunately the direct application of these results is impracticable for large problems. Since the sufficient conditions are not necessary, in case of their failure one is unable to draw conclusions on a search path for a local minimizer. We have analyzed the problem using the KKT conditions and derived necessary and sufficient conditions which enabled us to unequivocally characterize local optima in terms of the solution of the Total Least Squares and the set of active constraints. Establishing the common features between these two problems is not only important from a theoretical point of view, but it opens the possibility of using theoretical developments related with the Total Least Squares to solve the problem with inequalities.

2002
Amaral, P., and P. Barahona. "On Optimal Correction of Inconsistent Linear Constraints." Principles and Practice of Constraint Programming, CP'2002. Ed. Pascal Van Hentenryck. Vol. 2470. Lecture Notes in Computer Science, 2470. Springer, 2002. 33-46. Abstract

In practice one has often to deal with the problem of inconsistency between constraints, as the result, among others, of the comple\-xi\-ty of real models. To overcome these conflicts we can outline two major \mbox{actions}: removal of constraints or changes in the coefficients of the model. This last approach, that can be generically described as ``model corre\-ction" is the problem we address in this paper. The correction of the right hand side alone was one of the first approaches. The correction of both the matrix of coefficients and the right hand side introduces non linearity in the constraints. The degree of difficulty in solving the problem of the optimal correction depends on the objective function, whose purpose is to measure the closeness between the original and corrected model. Contrary to other norms, the optimization of the important Frobenius was still an open problem. We have analyzed the problem using the KKT conditions and derived necessary and sufficient conditions which enabled us to unequivocally characterize local optima, in terms of the solution of the Total Least Squares and the set of active constraints. These conditions justify a set of pruning rules, which proved, in preliminary experimental results, quite successful in a tree search procedure for determining the global minimizer.

2000
Amaral, P., M. W. Trosset, and P. Barahona Correcting an inconsistent system of linear inequalities by nonlinear programming. Houston, TX 77005: Department of Computational & Applied Mathematics, Rice University, 2000. Abstract
n/a
1999
Amaral, P., and P. Barahona. "About infeasibility in the constraints of a linear model." Ricerca Operativa. 92 (1999): 49-67. Abstract
n/a
Amaral, P., and P. Barahona. "After infeasibility in linear programming." Proceedings of CP-AI-OR99 workshop on integration of AI and OR techniques in Constraint Programming for Combinatorial Optimization problems. Vol. 1. Universit, 1999. Abstract

This work is focused on the correction of Infeasible Linear problems. Its motivation is not difficult to understand if one thinks on the complexity of model building in large real problems. The inconsistency can arise in the definition of the model due, for instance, to structural or data type errors. The identification of conflict sets of constraints is very useful but might not be enough to overcome the problem, since the implementation of a solution may require the definition of a new feasible model. We present a short review on known procedures for the diagnosis of these problems. The approach we propose is based on the correction of (potentially) all the parameters of the model restrictions. We present a pure algebraic methodology based on the Singular Value Decomposition of a matrix. This method is quite rigid in the changes of the matrix coefficients changes, so we give insights on a heuristic based approach in order to attain more flexibility.