@techreport{pedroso1996niche-treport,
author = {Jo{\~a}o P. Pedroso},
title = {{Niche Search:} {A}n {O}bject-{O}riented
implementation in the {C++} programming language},
institution = {CORE, UCL},
year = 1996,
abstract = {A (rather dated) description of the classes that
intervene in Niche Search.}
}
@inproceedings{pedroso1996ppsn,
author = {Jo{\~a}o Pedro Pedroso},
title = {Niche Search: An Evolutionary Algorithm for Global
Optimisation},
booktitle = {PPSN},
year = 1996,
pages = {430-440},
ee = {http://dx.doi.org/10.1007/3-540-61723-X_1007},
crossref = {zzz:DBLP:conf/ppsn/1996},
bibsource = {DBLP, http://dblp.uni-trier.de},
pdf = {PDF/niche-ppsn.pdf},
abstract = {In this paper we describe niche search, a
genetic-based optimisation approach which is
characterised by an evolutionary search on two
layers: the individual layer (which is comparable to
search described in other genetic algorithms), and
the niche layer. Neither of these searches is
directed: both individuals and niches evolve based
on the selection of the fittest. The numerical
results obtained by niche search are quite
promising, as our implementation has successfully
handled all the tests carried out. The
computational performance is considerably better
than that of other algorithms of the same family
analysed in the literature. }
}
@inproceedings{pedroso1996seal,
author = {Jo{\~a}o P. Pedroso},
title = {Numerical solution of {N}ash and {S}tackelberg
equilibria: an evolutionary approach},
booktitle = {Proceedings of the First Asia Conference on
Simulated Evolution and Learning},
xcrossref = {should be in procSEAL96},
year = 1996,
organization = {First Asia Conference on Simulated Evolution and
Learning (SEAL'96)},
address = {Taejon, Korea},
jppnote = {>>> should be Lecture notes in Artificial
Intelligence},
jppbooktitle = {>>> Lecture notes in Artificial Intelligence},
jpppublisher = {>>> Springer-Verlag},
pages = {151-160},
pdf = {PDF/nash-es.pdf},
abstract = { In this paper we describe evolutionary heuristics
for numerically solving systems of several,
interdependent optimisation problems. They can be
used for the solution of some games with
simultaneous moves of the players (Nash equilibria),
asynchronous moves (Stackelberg equilibria), or a
mix of these situations. The application is
possible in cases where the presence of
non-convexities, integral variables, or other
factors restrain the use of traditional methods,
based on derivatives. The solution of instances of
well known economic equilibrium problems with these
algorithms is supplied. The results obtained for
these simple cases show potential applications of
the strategies, and provide limited convergence
evidence.}
}
@techreport{pedroso1997mnpdp,
author = {Jo{\~a}o P. Pedroso},
title = {Niche Search: an Application to the {M}anhattan
Newspaper Problem},
institution = {Center for Operations Research and Econometrics},
year = 1997,
type = {Discussion Paper},
number = 9765,
address = {Universit{\'e} Catholique de Louvain,
Louvain-la-Neuve, Belgium},
abstract = { In this paper we describe a hybrid strategy for
solving combinatorial optimisation problems,
obtained by coupling a local search method to an
evolutionary algorithm, and we provide an
application to the Manhattan newspaper problem. The
local search method has been devised specifically
for this class of problems. It is based on a
composite neighbourhood, which is searched
iteratively up to the point where no further
improvements can be made. The evolutionary
structure is the niche search, an algorithm based on
the evolution of several independent niches. Niches
whose individuals' fitness is good remain, and the
others tend to be replaced. The separation of the
population into niches allows for a good compromise
between intensive search (inside each niche) and
diversification (through the separation between the
niches). },
pdf = {PDF/manhattan-dp.pdf}
}
@inproceedings{pedroso1997noltalib,
author = {Jo{\~a}o P. Pedroso},
title = {Implementation of a library for modelling in
economics: design guidelines},
booktitle = {Proceedings of the 1997 International Symposium on
Nonlinear Theory and its Applications},
crossref = {procNOLTA97},
pages = {297-300},
year = 1997,
abstract = { In this paper we propose some design guidelines for
the implementation of a library for computer aided
modelling and analysis in economics. We base our
approach in object-oriented programming. We also
introduce a prototype implementation, where a set of
algorithms and data structures appropriated for
economic modelling is supplied. },
pdf = {PDF/econ-lib.pdf}
}
@inproceedings{pedroso1997noltapar,
author = {Jo{\~a}o P. Pedroso},
title = {Control of search parameters in evolutionary
algorithms},
booktitle = {Proceedings of the 1997 International Symposium on
Nonlinear Theory and its Applications},
crossref = {procNOLTA97},
pages = {1265-1268},
year = 1997,
abstract = { In this paper we present a strategy for
automatically adapting the control parameters of an
evolutionary algorithm. Its main features consist
on its simplicity, and on providing total
independence of the type of problem being solved. },
pdf = {PDF/control-pars.pdf}
}
@techreport{pedroso1998bsis,
author = {Jo{\~a}o P. Pedroso},
title = {An evolutionary solver for linear integer
programming},
institution = {Riken Brain Science Institute},
year = 1998,
type = {BSIS Technical Report},
number = {98-7},
address = {Wako-shi, Saitama, Japan},
abstract = {In this paper we introduce an evolutionary algorithm
for the solution of linear integer programs. The
strategy is based on the separation of the set of
variables into the integer subset and the continuous
subset; the integer variables are fixed by the
evolutionary system, and the continuous ones are
determined in function of them, by a linear program
solver. If they correspond to a feasible solution,
their evaluation is determined directly by the
objective function. If the variables correspond to
an infeasible solution, the evaluation is measured
by the minimal sum of constraint violations.
Solutions closer to feasibility are preferred,
without regard to the objective function. We report
results obtained for some standard benchmark
instances, and compare them with those obtained by
branch-and-bound. The performance of the
evolutionary algorithm is promising. Good feasible
solutions were generally obtained, and in some of
the difficult benchmark tests the algorithm
outperformed branch-and-bound. },
pdf = {PDF/mip-ga-tr9807.pdf}
}
@inproceedings{pedroso1998icec,
author = {Jo{\~a}o P. Pedroso},
title = {Niche Search: an Application in Vehicle Routing},
booktitle = {IEEE International Conference on Evolutionary
Computation},
crossref = {procICEC98},
year = 1998,
pages = {177-182},
abstract = {In this paper we describe a hybrid strategy for
solving combinatorial optimisation problems,
obtained by coupling a local search method to an
evolutionary algorithm, and we provide an
application to a particular variant of the vehicle
routing problem. The local search method has been
devised specifically for this class of problems. It
is based on a composite neighbourhood, which is
searched iteratively up to the point where no
further improvements can be made. The evolutionary
structure is the niche search, an algorithm based on
the evolution of several independent niches. Niches
whose individuals' fitness is good remain, and the
others tend to be replaced. The separation of the
population into niches allows for a good compromise
between intensive search (inside each niche) and
diversification (through the separation between the
niches). We also describe how we integrate specific
problem knowledge into an evolutionary structure, in
order to achieve a high performance optimisation
algorithm. All the steps that we consider necessary
are described in detail: finding an appropriate
representation, determining what is a relevant
neighbourhood, setting up a local search method and
finally integrating the local search into an
evolutionary algorithm. },
pdf = {PDF/manhattan-icec.pdf}
}
@techreport{pedroso1999bsis,
author = {Jo{\~a}o P. Pedroso and Noboru Murata},
title = {Support vector machines for linear programming:
motivation and formulation},
institution = {Riken Brain Science Institute},
year = 1999,
type = {BSIS Technical Report},
number = {99-2},
address = {Wako-shi, Saitama, Japan},
ps = {lin-svm.ps.gz},
abstract = { We introduce two formulations for training support
vector machines, based on considering the $L_1$ and
$L_\infty$ norms instead of the currently used $L_2$
norm, and maximising the margin between the
separating hyperplane and each data sets using $L_1$
and $L_\infty$ distances. We exploit the
geometrical properties of these different norms, and
propose what kind of results should be expected for
them. Formulations in mathematical programming for
linear problems corresponding to $L_1$ and
$L_\infty$ norms are also provided, for both the
separable and non separable cases. We report
results obtained for some standard benchmark
problems, which confirmed that the performance of
all the formulations is similar. As expected, the
CPU time required for machines solvable with linear
programming is much shorter. }
}
@techreport{pedroso1999cio,
author = {Jo{\~a}o P. Pedroso},
title = {An evolutionary solver for pure integer linear
programming},
institution = {Centro de Investiga{\c{c}}{\~a}o Operacional da
Universidade de Lisboa},
year = 1999,
type = {Working Paper},
number = {5/99},
address = {Centro de Investiga{\c{c}}{\~a}o Operacional,
Faculdade de Ci\^encias da Universidade de Lisboa,
1749-016 Lisboa, Portugal},
ps = {pip-ga.ps.gz},
abstract = {In this paper we introduce an evolutionary algorithm
for the solution of pure integer linear programs.
All the variables of the problem are fixed by the
evolutionary system. If they correspond to a
feasible solution, their evaluation is determined
directly by the objective function. If the
variables correspond to an infeasible solution, the
evaluation is measured by the sum of
infeasibilities, which can be determined by simple
linear algebra manipulations. The algorithm
proposed does not require the solution of continuous
linear programs. We report results obtained for
some standard benchmark problems, and compare them
with those obtained by branch-and-bound. The
performance of the evolutionary algorithm is
promising. Good feasible solutions were generally
obtained, and in some of the difficult benchmark
tests it outperformed branch-and-bound. }
}
@inproceedings{pedroso2000ijcnn,
author = {Jo{\~a}o P. Pedroso and Noboru Murata},
title = {Optimisation on support vector machines},
booktitle = {IEEE-INNS-ENNS International Joint Conference on
Neural Networks},
pages = {399-404},
year = 2000,
editor = {Shun-Ichi Amari and C. Lee Giles and Marco Gori and
Vincenzo Piuri},
volume = {VI},
pdf = {PDF/svm-ijcnn-2000.pdf},
abstract = {In this paper we deal with the optimisation problem
involved in determining the maximal margin
separation hyperplane in support vector machines.
We consider three different formulations, based on
$L_2$ norm distance (the standard case), $L_1$ norm,
and $L_\infty$ norm. We consider separation in the
original space of the data (i.e., there are no
kernel transformations). For any of these cases, we
focus on the following problem: having the optimal
solution for a given training data set, one is given
a new training example. The purpose is to use the
information about the solution of the problem
without the additional example in order to speed up
the new optimisation problem. We also consider the
case of reoptimisation after removing an example
from the data set. We report results obtained for
some standard benchmark problems. }
}
@techreport{pedroso2001cio,
author = {Jo{\~a}o P. Pedroso},
title = {Metaheuristics for combinatorial optimisation},
institution = {Centro de Investiga{\c{c}}{\~a}o Operacional da
Universidade de Lisboa},
year = 2001,
type = {Working Paper},
number = {9/01},
address = {Centro de Investiga{\c{c}}{\~a}o Operacional,
Faculdade de Ci\^encias da Universidade de Lisboa,
1749-016 Lisboa, Portugal},
abstract = {The use of metaheuristics for solving combinatorial
optimisation has now a long history, and there are
virtually no well-known, hard optimisation problems
for which a metaheuristic has not been applied.
Often, metaheuristics obtain the best known
solutions for hard, large-size real problems, for
which exact methods are too time consuming to be
applied in in practice. There are many successful
applications reported in the literature; still, to
the best of our knowledge there are no mathematical
programming languages with an interface to solvers
based on metaheuristics. Mathematical programming
being the traditional, powerful way of modelling
combinatorial problems, we believe that it would be
an important achievement to have a solver based on
metaheuristics callable from mathematical
programming systems. In this paper we will focus on
the different aspects to take into account when
designing a metaheuristic which can be applied to
any combinatorial optimisation problem modelled in
mathematical programming. },
pdf = {PDF/ip-mh.pdf}
}
@inproceedings{pedroso2001dlsp,
author = {Ana S. Pereira and Filipe Carvalho and Jo{\~a}o
P. Pedroso and Miguel Constantino},
title = {Iterated Local Search and Tabu Search for a Discrete
Lot Sizing and Scheduling Problem},
booktitle = {Proceedings of the Fourth Metaheuristics
International Conference},
pages = {697-701},
year = 2001,
editor = {Jorge P. Sousa and Mauricio G. C. Resende},
address = {Porto, Portugal},
pdf = {PDF/dlsp.pdf},
abstract = { In this paper we describe iterated local search and
tabu search for solving a multi-item, multi-machine
discrete lot sizing and scheduling problem with
sequence dependent changeover costs. We present two
construction heuristics with a random component; one
of them is purely random and another is based on the
linear programming relaxation of the mixed integer
programming model. They are used to generate initial
solutions for iterated local search and tabu search.
We also propose two ways of exploring the
neighbourhoods, one based on a random subset of the
whole neighbourhood, and another based on exploring
the whole neighbourhood. Construction and
improvement methods were combined on iterated local
search and tabu search, leading to a total of eight
different methods. We present results of extensive
computer experiments for analysing the performance
of all methods and their comparison with
branch-and-bound, and conclude with some remarks on
the different approaches to the problem. }
}
@inproceedings{pedroso2001neto,
author = {Teresa Neto and Jo{\~a}o P. Pedroso},
title = {GRASP for linear integer programming},
booktitle = {Proceedings of the Fourth Metaheuristics
International Conference},
pages = {377-385},
year = 2001,
editor = {Jorge P. Sousa and Mauricio G. C. Resende},
address = {Porto, Portugal},
ps = {mip-grasp.ps},
abstract = { In this paper we introduce a GRASP for the solution
of general linear integer problems. The strategy is
based on the separation of the set of variables into
the integer subset and the continuous subset. The
integer variables are fixed by GRASP and replaced in
the original linear problem. If the original problem
had continuous variables, we have now a pure
continuous problem, which can be solved by a linear
program solver to determine the objective value
corresponding to the fixed variables. If the
original problem was a pure integer problem, simple
algebraic manipulations can be used to determine the
objective value that corresponds to the fixed
variables. When we assign values to integer
variables that lead to an impossible linear problem,
the evaluation of the corrresponding solution is
given by the sum of infeasibilities, together with
an infeasibility flag. We report results obtained
for some standard benchmark problems, and compare
them to those obtained by branch-and-bound. }
}
@inproceedings{pedroso2001nolta,
author = {Jo{\~a}o P. Pedroso},
title = {Metaheuristics using the Simplex Algorithm for
Nonlinear Programming},
booktitle = {Proceedings of the 2001 International Symposium on
Nonlinear Theory and its Applications},
crossref = {procNOLTA2001},
pages = {315-318},
year = 2001,
abstract = {In this paper we present a metaheuristic for
non-linear programming, based on the Nelder and Mead
simplex algorithm. The algorithm proposed is
suitable for both unconstrained and constrained
optimisation. We explore several possibilities for
escaping local optima.},
pdf = {PDF/nolta-2001.pdf}
}
@article{pedroso2001prl,
author = {Jo{\~a}o P. Pedroso and Noboru Murata},
title = {Support vector machines with different norms:
motivation, formulations, and results},
journal = {Pattern Recognition Letters},
year = 2001,
volume = 22,
pages = {1263-1272},
abstract = { We introduce two formulations for training support
vector machines, based on considering the $L_1$ and
$L_\infty$ norms instead of the currently used $L_2$
norm, and maximising the margin between the
separating hyperplane and each data sets using $L_1$
and $L_\infty$ distances. We exploit the
geometrical properties of these different norms, and
propose what kind of results should be expected for
them. Formulations in mathematical programming for
linear problems corresponding to $L_1$ and
$L_\infty$ norms are also provided, for both the
separable and non separable cases. We report
results obtained for some standard benchmark
problems, which confirmed that the performance of
all the formulations is similar. As expected, the
CPU time required for machines solvable with linear
programming is much shorter. },
jpppdf = {PDF/svm-prl.pdf}
}
@article{pedroso2002itors,
author = {Jo{\~a}o P. Pedroso},
title = {An evolutionary solver for pure integer linear
programming},
journal = {International Transactions in Operational Research},
year = 2002,
volume = 9,
number = 3,
pages = {337-352},
month = {May},
abstract = { In this paper we introduce an evolutionary
algorithm for the solution of pure integer linear
programs. All the variables of the problem are
fixed by the evolutionary system. If they
correspond to a feasible solution, their evaluation
is determined directly by the objective function.
If the variables correspond to an infeasible
solution, the evaluation is measured by the sum of
infeasibilities, which can be determined by simple
linear algebra manipulations. The algorithm
proposed does not require the solution of continuous
linear programs. We report results obtained for
some standard benchmark problems, and compare them
with those obtained by branch-and-bound. The
performance of the evolutionary algorithm is
promising. Good feasible solutions were generally
obtained, and in some of the difficult benchmark
tests it outperformed branch-and-bound. },
jpppdf = {PDF/pip-ga.pdf}
}
@inproceedings{pedroso2003cePROC,
author = {Jo{\~a}o P. Pedroso},
title = {A multi-agent system for automated timetabling with
shared resources},
booktitle = {Proceedings of the 10th ISPE International
Conference on Concurrent Engineering},
year = 2003,
editor = {Jianzhong Cha and Ricardo Jardim-Gon{\c c}alves and
Adolfo Steiger-Gar{\c c}{\~a}o},
volume = {2 - Advanced design, management and production
systems},
address = {Madeira Island - Portugal},
publisher = {A.A. Balkema Publishers},
abstract = { We propose an automated timetabling system for a
typical situation in universities, where agents
(usually departments or faculties) compete for a set
of resources (lecture rooms) on a given number of
time slots. Each agent uses its own algorithm
(which might be unknown to the others). A central
system decides whether some agent is granted a
resource or not, based on a list of requests and on
a certificate, obtained from each agent, asserting
that it does not have requests with priority higher
that a certain amount. Priority is measured
primarily by the number of attendees and some
requirements for particular features on the
resources, but other criteria are proposed for ties.
We describe a prototype implementation, in use at
the Faculty of Sciences, University of Porto. },
pdf = {PDF/ce2003.pdf}
}
@inproceedings{pedroso2003dlsp,
editor = {Jorge P. Sousa and Mauricio G. C. Resende},
author = {Ana S. Pereira and Filipe Carvalho and Miguel
Constantino and Jo{\~a}o P. Pedroso},
booktitle = {METAHEURISTICS: Computer Decision-Making},
title = {Iterated Local Search and Tabu Search for a Discrete
Lot Sizing and Scheduling Problem},
chapter = 27,
publisher = {Kluwer Academic Publishers},
year = 2003,
series = {Combinatorial Optimization Book Series},
pages = {575-600},
doi = {10.1007/978-1-4757-4137-7_27},
pdf = {PDF/dlsp.pdf},
abstract = { In this paper we describe iterated local search and
tabu search for solving a multi-item, multi-machine
discrete lot sizing and scheduling problem with
sequence dependent changeover costs. We present two
construction heuristics with a random component; one
of them is purely random and another is based on the
linear programming relaxation of the mixed integer
programming model. They are used to generate initial
solutions for iterated local search and tabu search.
We also propose two ways of exploring the
neighbourhoods, one based on a random subset of the
whole neighbourhood, and another based on exploring
the whole neighbourhood. Construction and
improvement methods were combined on iterated local
search and tabu search, leading to a total of eight
different methods. We present results of extensive
computer experiments for analysing the performance
of all methods and their comparison with
branch-and-bound, and conclude with some remarks on
the different approaches to the problem. }
}
@inproceedings{pedroso2003neto,
editor = {Jorge P. Sousa and Mauricio G. C. Resende},
author = {Teresa Neto and Jo{\~a}o P. Pedroso},
booktitle = {METAHEURISTICS: Computer Decision-Making},
title = {GRASP for linear integer programming},
chapter = 26,
publisher = {Kluwer Academic Publishers},
year = 2003,
series = {Combinatorial Optimization Book Series},
pages = {545-574},
abstract = { In this paper we introduce a GRASP for the solution
of general linear integer problems. The strategy is
based on the separation of the set of variables into
the integer subset and the continuous subset. The
integer variables are fixed by GRASP and replaced in
the original linear problem. If the original problem
had continuous variables, it becomes a pure
continuous problem, which can be solved by a linear
program solver to determine the objective value
corresponding to the fixed variables. If the
original problem was a pure integer problem, simple
algebraic manipulations can be used to determine the
objective value that corresponds to the fixed
variables. When we assign values to integer
variables that lead to an impossible linear problem,
the evaluation of the corresponding solution is
given by the sum of infeasibilities, together with
an infeasibility flag. We report results obtained
for some standard benchmark problems, and compare
them to those obtained by branch-and-bound and to
those obtained by an evolutionary solver. },
doi = {10.1007/978-1-4757-4137-7_26},
pdf = {PDF/mip-grasp.pdf}
}
@techreport{pedroso2004h4TR,
author = {Rog{\'e}rio Reis and Nelma Moreira and Jo{\~a}o
Pedro Pedroso},
title = {Educated brute-force to get $h(4)$},
institution = {LIACC, Universidade do Porto},
year = 2004,
number = {DCC-2004-04},
abstract = {In one of his numerous conferences, Frank Harary,
talked about one of his many games, that, as usual,
had a very difficult problem associated to it. In
this case, a family of games for two players in
which the selected number of columns in the game has
a vital importance. He has proved that for 2 and 3
columns the longest match has 9 and 24 moves
respectively, that is to say that h_2=9 and
h_3=24. At the same time it was announced that he
knew a solution of length 67 for the problem with 4
columns, but he didn't know if it was the
maximum. We present here a program that proves that
h_4=67. Although it uses but a brute-force approach,
its soundness seems good fun to prove.},
pdf = {PDF/dcc-2004-04.pdf}
}
@inproceedings{pedroso2004ickeds,
author = {Jo{\~a}o P. Pedroso and Nelma Moreira and
Rog{\'e}rio Reis},
title = {A web-based system for multi-agent interactive
timetabling},
booktitle = {{ICKEDS}'04: International Conference on Knowledge
Engineering and Decision Support},
year = 2004,
address = {Porto, Portugal},
month = {July},
abstract = { We propose a web-based timetabling system for a
typical situation in universities, where agents
(usually departments or faculties) compete for a set
of resources (lecture rooms) on a given number of
time slots. Each agent (typically a person, on the
behalf of a department) proposes the placement (room
and time) for events. A dispatching system decides
which event should be scheduled next, based on a
pre-established set of rules, and asks its placement
to the corresponding department. The system also
suggests the placement of an event to each agent,
thus allowing a completely automated timetable
construction. We describe a prototype implemented
at the Faculty of Sciences, University of Porto. },
pdf = {PDF/ickeds2004.pdf}
}
@inproceedings{pedroso2004iss,
author = {Jo{\~a}o P. Pedroso},
title = {Metaheuristics for industrial scheduling},
booktitle = {Proceedings of the International Symposium in
Scheduling},
editor = {Shigeru Masuyama},
year = 2004,
address = {Shizuoka, Japan},
month = {September},
abstract = { We will analyse the problem of scheduling on batch
industries. A production order for an end product
implies the sequential execution of a set of
operations; for each operation, there is a set of
machines, possibly with different characteristics,
able to process it. After processing an operation,
the machines have to be cleaned; the cleaning time
is sequence-dependent. The most usual objective is
minimising the makespan for all the orders in hand.
In this work we present the fundamental notions
concerning the use of metaheuristics for tackling
this problem, focusing on construction strategies
and neighbourhood structures for local search. },
pdf = {PDF/SchedSympShizuoka.pdf},
anote = {Invited seminar}
}
@techreport{pedroso2004mipenumTR,
author = {Jo{\~a}o P. Pedroso},
title = {Hybrid Enumeration Strategies for Mixed Integer
Programming},
institution = {LIACC, Universidade do Porto},
year = 2004,
number = {DCC-2004-08},
pdf = {PDF/mip-enum-WP.pdf},
abstract = { In this paper we present several algorithms which
combine a partial enumeration with metaheuristics
for the solution of general mixed-integer
programming problems. The enumeration is based on
the primal values assignable to the integer
variables of the problem. We develop some algorithms
for this integration, and test them using a set of
well-known benchmark problems. }
}
@inproceedings{pedroso2004miptsKLUWER,
editor = {Cesar Rego},
author = {Jo{\~a}o P. Pedroso},
booktitle = {Metaheuristic Optimization via Memory and Evolution:
Tabu Search and Scatter Search},
title = {Tabu Search for Mixed Integer Programming},
chapter = 11,
series = {Operations Research/Computer Science Interfaces
Series},
publisher = {Springer},
year = 2005,
abstract = { This paper introduces tabu search for the solution
of general linear integer problems. Search is done
on integer variables; if there are continuous
variables, their corresponding value is determined
through the solution of a linear program, which is
also used to evaluate the integer solution. The
complete tabu search procedure includes an
intensification and diversification procedure, whose
effects are analysed on a set of benchmark problems.
},
pdf = {PDF/mip-ts.pdf}
}
@inproceedings{pedroso2005hm,
author = {Jo{\~a}o Pedro Pedroso and Mikio Kubo},
title = {Hybrid Tabu Search for Lot Sizing Problems},
booktitle = {Hybrid Metaheuristics},
year = 2005,
pages = {66-77},
ee = {http://dx.doi.org/10.1007/11546245_7},
crossref = {zzz:DBLP:conf/hm/2005},
bibsource = {DBLP, http://dblp.uni-trier.de},
abstract = { This paper presents a hybrid tabu search strategy
for lot sizing problems. This strategy allows the
exploitation of the quality of the well-known
relax-and-fix heuristic, inside a tabu search
framework which enforces diversity. The
computational results show an advantage of this
strategy when compared to a version of the
relax-and-fix heuristic and to time constrained
branch-and-bound. },
pdf = {PDF/hybrid-ts.pdf}
}
@inproceedings{pedroso2006icdmrodriguesA,
author = {Pedro Rodrigues and Jo{\~a}o Gama and Jo{\~a}o Pedro
Pedroso},
title = {{ODAC}: Hierarchical Clustering of Time Series Data
Streams},
booktitle = {Proceedings of the Sixth SIAM International
Conference on Data Mining},
year = 2006,
editor = {Joydeep Ghosh, Diane Lambert, David Skillicorn and
Jaideep Srivastava},
pages = {499-503},
month = {April},
address = {Bethesda, Maryland, USA},
note = {ISBN 0-89871-611-X},
organization = {SIAM},
abstract = { This paper presents a time series whole clustering
system that incrementally constructs a tree-like
hierarchy of clusters, using a top-down strategy.
The Online Divisive-Agglomerative Clustering
({ODAC}) system uses a correlation-based
dissimilarity measure between time series over a
data stream and possesses an agglomerative phase to
enhance a dynamic behavior capable of concept drift
detection. Main features include splitting and
agglomerative criteria based on the diameters of
existing clusters and supported by a significance
level. At each new example, only the leaves are
updated, reducing computation of unneeded
dissimilarities and speeding up the process every
time the structure grows. Experimental results on
artificial and real data suggest competitive
performance on clustering time series and show that
the system is equivalent to a batch divi- sive
clustering on stationary time series, being also
capable of dealing with concept drift. With this
work, we assure the possibility and importance of
hierarchical incremental time series whole
clustering in the data stream paradigm, presenting a
valuable and usable option. },
doi = {10.1137/1.9781611972764.48},
pdf = {PDF/ODAC.pdf}
}
@techreport{pedroso2007earfmip-DCC,
author = {Jo{\~a}o P. Pedroso},
title = {An evolutionary solver for mixed integer
programming},
institution = {DCC, FC, Universidade do Porto},
year = 2007,
number = {DCC-2007-09},
abstract = { In this paper we introduce an evolutionary
algorithm for the solution of mixed integer
programs. The strategy is based on the separation
of the set of variables into the integer subset and
the continuous subset. The main idea is that if the
integer variables are fixed by the evolutionary
system, the continuous ones can be determined in
function of them by a linear program, which
simultaneously provides an evaluation of those
variables. We extend this idea to the case were
some of the integer variables are fixed by the
evolutionary system and the remaining ones, as well
as the continuous ones, are determined in function
of them. Branch-and-bound and a specialised version
of the relax-and-fixed heuristic are used to solve
the mixed-integer subproblems. When a particular
assignment of the integer variables set by the
evolutionary system leads to a feasible solution,
its evaluation is determined directly by the
objective function. If the variables correspond to
an infeasible solution, the evaluation is measured
by the number of variables that could not be fixed,
due to infeasibility in the subproblem; solutions
with more variables fixed are preferred. We report
results obtained for some standard benchmark
instances, and compare them with those obtained by
time limited branch-and-bound. For a set of
difficult instances, the evolutionary algorithm
could almost always improve the solution obtained by
branch-and-bound on the same amount of CPU time. },
pdf = {PDF/mip-ga-rf-DCC.pdf}
}
@inproceedings{pedroso2007nlpsimplexLNCS,
author = {Jo{\~a}o Pedro Pedroso},
title = {Simple Metaheuristics Using the Simplex Algorithm
for Non-linear Programming},
booktitle = {SLS},
year = 2007,
pages = {217-221},
ee = {http://dx.doi.org/10.1007/978-3-540-74446-7_21},
crossref = {zzz:DBLP:conf/sls/2007},
bibsource = {DBLP, http://dblp.uni-trier.de},
abstract = { In this paper we present an extension of the Nelder
and Mead simplex algorithm for non-linear
programming, which makes it suitable for both
unconstrained and constrained optimisation. We then
explore several extensions of the method for
escaping local optima, and which make it a simple,
yet powerful tool for optimisation of nonlinear
functions with many local optima. A strategy which
proved to be extremely robust was random start local
search, with a correct, though unusual, setup.
Actually, for some of the benchmarks, this simple
metaheuristic remained as the most effective one.
The idea is to use a very large simplex at the
begin; the initial movements of this simplex are
very large, and therefore act as a kind of filter,
which naturally drives the search into good areas.
We propose two more mechanisms for escaping local
optima, which, still being very simple to implement,
provide better results for some difficult problems.
},
pdf = {PDF/nlp-simplex-lncs.pdf}
}
@article{pedroso2008clustering,
author = {Pedro Pereira Rodrigues and Jo{\~a}o Gama and
Jo{\~a}o P. Pedroso},
title = {Hierarchical Clustering of Time Series Data Streams},
journal = {{IEEE} Transactions on Knowledge and Data
Engineering},
year = 2008,
volume = 20,
number = 5,
pages = {615-627},
url = {http://dx.doi.org/10.1109/TKDE.2007.190727},
month = {May},
abstract = {This paper presents and analyzes an incremental
system for clustering streaming time series. The
Online Divisive-Agglomerative Clustering ({ODAC})
system continuously maintains a tree-like hierarchy
of clusters that evolves with data. {ODAC} uses a
top-down strategy. The splitting criterion is a
correlation-based dissimilarity measure among time
series, splitting each node by the farthest pair of
streams, which defines the diameter of the
cluster. In stationary environments expanding the
structure leads to a decrease in the diameters of
the clusters. The system uses a merge operator,
which agglomerates two sibling clusters, in order to
react to changes in the correlation structure
between time series. The split and merge operators
are triggered in response to changes in the
diameters of existing clusters. The system is
designed to process thousands of data streams that
flow at high-rate. The main features of the system
include update time and memory consumption that do
not depend on the number of examples in the
stream. Moreover, the time and memory required to
process an example decreases whenever the cluster
structure expands. Experimental results on
artificial and real data assess the processing
qualities of the system, suggesting competitive
performance on clustering streaming time series,
exploring also its ability to deal with concept
drift. },
jpppdf = {PDF/RGP08.pdf}
}
@incollection{pedroso2008mco,
author = {Rui Jorge Rei and Mikio Kubo and Jo{\~a}o Pedro
Pedroso},
title = {Simulation-Based Optimization for Steel Stacking},
booktitle = {MCO},
year = 2008,
pages = {254-263},
ee = {http://dx.doi.org/10.1007/978-3-540-87477-5_28},
crossref = {zzz:DBLP:conf/mco/2008},
bibsource = {DBLP, http://dblp.uni-trier.de},
abstract = { In many sectors of industry, manufacturers possess
warehouses where finished goods are stored, awaiting
to fulfill a client order. We present a situation
where these items are characterized by release and
due dates, i.e. warehouse arrival for storage and
client delivery, respectively. The warehouse has a
number of positions available, where items can be
placed on top of each other, forming stacks. For
item manipulation, there is a single a stacking
crane, able to carry one item at a time. When in a
given stack an item at the top is due at a date
later than some item below it, it must be relocated
to another stack, so that the item below can be
delivered. In this problem the objective is to
minimize the number of movements made by the crane.
},
pdf = {PDF/stacking_rei-kubo-pedroso.pdf}
}
@inproceedings{pedroso2010cie,
author = {Jo{\~a}o P. Pedroso and Yves Smeers},
title = {Equilibria on a Game with Discrete Variables},
booktitle = {Programs, Proofs, Processes},
year = 2010,
organization = {Computability in Europe 2010},
editor = {Fernando Ferreira and H{\'e}lia Guerra and Elvira
Mayordomo and Jo{\~a}o Rasga},
address = {Azores, Portugal},
pages = {326-335},
pdf = {PDF/nash-co.pdf},
abstract = {Equilibrium in Economics has been seldom addressed
in a situation where some variables are discrete.
This work introduces a problem related to lot-sizing
with several players, and analyses some strategies
which are likely to be found in real world games.
An illustration with a simple example is presented,
with concerns about the difficulty of the problem
and computation possibilities.}
}
@inproceedings{pedroso2010nma,
author = {Jo{\~a}o Pedro Pedroso},
title = {Metaheuristics for the Asymmetric Hamiltonian Path
Problem},
booktitle = {NMA},
year = 2010,
pages = {272-279},
ee = {http://dx.doi.org/10.1007/978-3-642-18466-6_32},
crossref = {zzz:DBLP:conf/nma/2010},
bibsource = {DBLP, http://dblp.uni-trier.de},
pdf = {PDF/nma-atsp.pdf},
abstract = { One of the most important applications of the
Asymmetric Hamiltonian Path Problem is in
scheduling. In this paper we describe a variant of
this problem, and develop both a mathematical
programming formulation and simple metaheuristics
for solving it. The formulation is based on a
transformation of the input data, in such a way that
a standard mathematical programming model for the
Asymmetric Travelling Salesman Problem can be used
on this slightly different problem. Two standard
metaheuristics for the asymmetric travelling
salesman are proposed and analysed on this variant:
repeated random construction followed by local
search with the 3-Exchange neighbourhood, and
iterated local search based on the same
neighbourhood and on a 4-Exchange perturbation. The
computational results obtained show the interest and
the complementary merits of using a mixed-integer
programming solver and an approximative method for
the solution of this problem. }
}
@article{pedroso2010npp,
author = {Jo{\~a}o P. Pedroso and Mikio Kubo},
title = {Heuristics and Exact Methods for Number
Partitioning},
journal = {European Journal of Operational Research},
year = 2010,
volume = 202,
pages = {73-81},
url = {http://dx.doi.org/10.1016/j.ejor.2009.04.027},
doi = {10.1016/j.ejor.2009.04.027},
abstract = { Number partitioning is a classical NP-hard
combinatorial optimization problem, whose solution
is challenging for both exact and approximative
methods. This work presents a new algorithm for
number partitioning, based on ideas drawn from
branch-and-bound, breadth first search, and beam
search. A new set of benchmark instances for this
problem is also proposed. The behavior of the new
method on this and other test beds is analyzed and
compared to other well known heuristics and exact
algorithms. },
pdf = {PDF/EJOR_NPP_PedrosoKubo_2010.pdf}
}
@inproceedings{pedroso2011lncs,
author = {V\'{\i}tor Rodrigues and Jo{\~a}o Pedro Pedroso and
M{\'a}rio Florido and Sim{\~a}o Melo de Sousa},
title = {Certifying Execution Time},
booktitle = {FOPARA},
year = 2011,
pages = {108-125},
ee = {http://dx.doi.org/10.1007/978-3-642-32495-6_7},
crossref = {zzz:DBLP:conf/fopara/2011},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@article{pedroso2012itor,
author = {Rei, Rui Jorge and Pedroso, Jo{\~a}o Pedro},
title = {Heuristic search for the stacking problem},
journal = {International Transactions in Operational Research},
volume = 19,
number = 3,
issn = {1475-3995},
note = {\url{http://dx.doi.org/10.1111/j.1475-3995.2011.00831.x}},
pages = {379--395},
keywords = {Stacking Problem, optimization, simulation,
heuristics},
year = 2012,
abstract = {This paper presents the Stacking Problem, a hard
combinatorial optimization problem concerning
handling and storage of items in a warehouse, where
they are handled by a crane and organized into
stacks. We define the problem, study its complexity
class, and present a mathematical programming model
to solve it. In order to tackle medium- or
large-scale instances, we propose a simulation-based
algorithm using semi-greedy construction
heuristics. This simple approach allows for multiple
constructions, finding solutions within reasonable
time even for large instances. Three semi-greedy
heuristics are proposed and compared in an extensive
computational experiment, where we study the
relation between the number of constructions and the
best solution obtained using each heuristic.},
pdfremoved = {PDF/stacking-itor-preview.pdf}
}
@inproceedings{pedroso2012lncs,
author = {Rui Jorge Rei and Jo{\~a}o Pedro Pedroso and
Hideitsu Hino and Noboru Murata},
title = {A Tree Search Approach to Sparse Coding},
booktitle = {LION},
year = 2012,
pages = {472-477},
ee = {http://dx.doi.org/10.1007/978-3-642-34413-8_47},
crossref = {zzz:DBLP:conf/lion/2012},
bibsource = {DBLP, http://dblp.uni-trier.de},
abstract = {Sparse coding is an important optimization problem
with numerous applications. In this paper, we
describe the problem and the commonly used pursuit
methods, and propose a best-first tree search
algorithm employing multiple queues for unexplored
tree nodes. We assess the effectiveness of our
method in an extensive computational experiment,
showing its superiority over other methods even for
modest computational time.},
pdf = {PDF/sparsecoding_lion6.pdf}
}
@techreport{pedroso2013DCCa,
author = {Filipe Brand{\~a}o and Jo{\~a}o P. Pedroso},
title = {Bin Packing and Related Problems: General Arc-flow
Formulation with Graph Compression},
institution = {DCC, Faculdade de Ci{\^e}ncias, Universidade do
Porto},
year = 2013,
number = {DCC-2013-08},
pdf = {PDF/DCC-2013-08.pdf},
abstract = {We present an exact method, based on an arc-flow
formulation with side constraints, for solving bin
packing and cutting stock problems --- including
multi-constraint variants --- by simply representing
all the patterns in a very compact graph. Our method
includes a graph compression algorithm that usually
reduces the size of the underlying graph
substantially without weakening the model. As
opposed to our method, which provides strong models,
conventional models are usually highly symmetric and
provide very weak lower bounds. Our formulation is
equivalent to Gilmore and Gomory's, thus providing a
very strong linear relaxation. However, instead of
using column-generation in an iterative process, the
method constructs a graph, where paths from the
source to the target node represent every valid
packing pattern. The same method, without any
problem-specific parameterization, was used to solve
a large variety of instances from several different
cutting and packing problems. In this paper, we deal
with vector packing, graph coloring, bin packing,
cutting stock, cardinality constrained bin packing,
cutting stock with cutting knife limitation, cutting
stock with binary patterns, bin packing with
conflicts, and cutting stock with binary patterns
and forbidden pairs. We report computational results
obtained with many benchmark test data sets, all of
them showing a large advantage of this formulation
with respect to the traditional ones.}
}
@techreport{pedroso2013DCCb,
author = {Filipe Brand{\~a}o and Jo{\~a}o P. Pedroso},
title = {Cutting Stock with Binary Patterns: Arc-flow
Formulation with Graph Compression},
institution = {DCC, Faculdade de Ci{\^e}ncias, Universidade do
Porto},
year = 2013,
number = {DCC-2013-09},
pdf = {PDF/DCC-2013-09.pdf},
abstract = {The cutting stock problem with binary patterns (0-1
CSP) is a variant of CSP that usually appears as a
relaxation of 2D and 3D packing problems. We present
an exact method, based on an arc-flow formulation
with side constraints, for solving 0-1 CSP by simply
representing all the patterns in a very compact
graph. Gilmore-Gomory's column generation approach
is usually used to compute strong lower bounds for
0-1 CSP. We report a computational comparison
between the arc-flow approach and the
Gilmore-Gomory's approach.}
}
@techreport{pedroso2013DCCc,
author = {Filipe Brand{\~a}o and Jo{\~a}o P. Pedroso},
title = {Fast Pattern-based Algorithms for Cutting Stock},
institution = {DCC, Faculdade de Ci{\^e}ncias, Universidade do
Porto},
year = 2013,
number = {DCC-2013-10},
pdf = {PDF/DCC-2013-10.pdf},
abstract = {The conventional assignment-based first/best fit
decreasing algorithms (FFD/BFD) are not polynomial
in the cutting stock input size in its most common
format. Therefore, even for small instances with
large demands, it is difficult to compute FFD/BFD
solutions. We present pattern-based methods that
overcome the main problems of conventional
heuristics in cutting stock problems by representing
the solution in a much more compact format. Using
our pattern-based heuristics, FFD/BFD solutions for
extremely large cutting stock instances, with
billions of items, can be found in a very short
amount of time. }
}
@techreport{pedroso2013DCCd,
author = {Filipe Brand{\~a}o and Jo{\~a}o P. Pedroso},
title = {Multiple-choice Vector Bin Packing: Arc-flow
Formulation with Graph Compression},
institution = {DCC, Faculdade de Ci{\^e}ncias, Universidade do
Porto},
year = 2013,
number = {DCC-2013-13},
pdf = {PDF/DCC-2013-13.pdf},
abstract = {The vector bin packing problem (VBP) is a
generalization of bin packing with multiple
constraints. In this problem we are required to pack
items, represented by p-dimensional vectors, into as
few bins as possible. The multiple-choice vector bin
packing (MVBP) is a variant of the VBP in which bins
have several types and items have several
incarnations. We present an exact method, based on
an arc-flow formulation with graph compression, for
solving MVBP by simply representing all the patterns
in a very compact graph. As a proof of concept we
report computational results on a variable-sized bin
packing data set. }
}
@article{pedroso2013aor,
author = {Rui Jorge Rei and Jo{\~a}o Pedro Pedroso},
title = {Tree search for the stacking problem},
journal = {Annals of Operations Research},
volume = 203,
number = 1,
year = 2013,
pages = {371-388},
ee = {http://dx.doi.org/10.1007/s10479-012-1186-2},
abstract = {The stacking problem is a hard combinatorial
optimization problem with high practical interest
in, for example, steel storage or container port
operations. In this problem, a set of items is
stored in a warehouse for a period of time, and a
crane is used to place them in a limited number of
stacks. Since the entrance and exit of items occurs
in an arbitrary order, items may have to be
relocated in order to reach and deliver other items
below them. The objective of the problem is to find
a feasible sequence of movements that delivers all
items, while minimizing the total number of
movements. We propose two heuristic methods to
solve the problem, and study the scalability of an
exact approach. The two heuristic approaches are a
multiple simulation algorithm using semi-greedy
construction heuristics, and a stochastic best-first
tree search algorithm. The two methods are compared
in a set of challenging instances, revealing a
superior performance of the tree search approach in
most cases. },
pdf = {PDF/ANOR_Stacking_ReiPedroso2013.pdf}
}
@article{pedroso2013ejco,
author = {Brand{\~a}o, Filipe and Pedroso, Jo{\~a}o Pedro},
year = 2013,
issn = {2192-4406},
journal = {EURO Journal on Computational Optimization},
doi = {10.1007/s13675-013-0010-3},
title = {A complete search method for the relaxed traveling
tournament problem},
url = {http://dx.doi.org/10.1007/s13675-013-0010-3},
publisher = {Springer-Verlag},
keywords = {Traveling tournament problem; Branch-and-bound;
Metaheuristics; Dynamic programming; 90-08
Computational methods; 90-XX Operations research;
mathematical programming},
pages = {1-10},
language = {English},
abstract = { The Traveling Tournament Problem (TTP) is a sports
scheduling problem that includes two major issues in
creating timetables: home/away pattern feasibility
and travel distance. In this problem the schedule
must be compact: every team plays in every time
slot. However, there are some sports leagues that
have both home/away pattern restrictions and
distance limits, but do not require a compact
schedule. In such schedules, one or more teams can
have a bye in any time slot. This leads us to a
variant of the problem: the Relaxed Traveling
Tournament Problem (RTTP). We present a complete
search method to solve this problem based on
branch-and-bound, metaheuristics and dynamic
programming. },
pdf = {PDF/Brandao_2013_EURO_J_Comput_Optim.pdf}
}
@article{pedroso2013ijepes,
author = {Ana Viana and J. P. Pedroso},
title = {A new {MILP}-based approach for unit commitment in
power production planning},
journal = {International Journal of Electrical Power and Energy
Systems},
year = 2013,
volume = 44,
pages = {997-1005},
note = {\url{http://dx.doi.org/10.1016/j.ijepes.2012.08.046}},
abstract = {This paper presents a complete, quadratic
programming formulation of the standard thermal unit
commitment problem in power generation planning,
together with a novel iterative optimisation
algorithm for its solution. The algorithm, based on
a mixed-integer formulation of the problem,
considers piecewise linear approximations of the
quadratic fuel cost function that are dynamically
updated in an iterative way, converging to the
optimum; this avoids the requirement of resorting to
quadratic programming, making the solution process
much quicker. From extensive computational tests on
a broad set of benchmark instances of this problem,
the algorithm was found to be flexible and capable
of easily incorporating different problem
constraints. Indeed, it is able to tackle ramp
constraints, which although very important in
practice were rarely considered in previous
publications. Most importantly, optimal solutions
were obtained for several well-known benchmark
instances, including instances of practical
relevance, that are not yet known to have been
solved to optimality. Computational experiments and
their results showed that the method proposed is
both simple and extremely effective. },
pdf = {PDF/IJEPES_UCP_VianaPedroso_2013.pdf}
}
@techreport{pedroso2013kepDCC,
author = {Jo{\~a}o P. Pedroso},
title = {Maximizing expectation on vertex-disjoint cycle
packing},
institution = {DCC, Faculdade de Ci{\^e}ncias, Universidade do
Porto},
year = 2013,
number = {DCC-2013-05},
pdf = {PDF/DCC-2013-05_KEP.pdf},
abstract = {This paper proposes a method for computing the
expectation for the length of the maximum set of
vertex-disjoint cycles in a digraph where vertices
and/or arcs are subject to failure with a known
probability. This method has an immediate practical
application: it can be used for the solution of a
kidney exchange program in the common situation
where the underlying graph is unreliable. Results
for realistic benchmark instances are reported and
analyzed.}
}
@article{pedroso2013netoITOR,
author = {Teresa Neto and Miguel Constantino and Jo{\~a}o
P. Pedroso and Isabel Martins},
title = {A branch-and-bound procedure for forest harvest
scheduling problems addressing aspects of habitat
availability},
journal = {International Transactions in Operational Research},
url = {http://dx.doi.org/10.1111/itor.12003},
doi = {10.1111/itor.12003},
volume = 20,
number = 5,
pages = {689--709},
issn = {1475-3995},
year = 2013,
keywords = {forestry, branch and bound, integer programming,
tree algorithms, scheduling},
abstract = { In the literature, the most referenced approaches
for forest harvesting scheduling problems addressing
environmental protection issues have focused mainly
on including constraints on clearcut
area. Nevertheless, these restrictions may not be
sufficient to prevent the loss of habitat
availability that endangers the survival of many
wild species. This work presents a tree search
procedure for finding good feasible solutions, in
reasonable times, to forest harvest scheduling
problems with constraints on clearcut area and
habitat availability. We use two measures for
habitat availability: the area of all habitats and
the connectivity between them. For solving the
problem, we use a tree search procedure: a process
inspired in branch-and-bound, specifically designed
for this problem. In each branch, a partial
solution leads to two children nodes, corresponding
to harvesting or not a given stand in a given
period. Pruning is based on constraint violations
or on unreachable objective values. Preliminary
computational results are reported. },
pdf = {PDF/Neto_et_al-2013-International_Transactions_in_Operational_Research.pdf}
}
@techreport{pedroso2014DCC05,
author = {Jo{\~a}o P. Pedroso and Mikio Kubo and Ana Viana},
title = {Unit commitment with valve-point loading effect},
institution = {DCC, Faculdade de Ci{\^e}ncias, Universidade do
Porto},
year = 2014,
number = {DCC-2014-05},
pdf = {PDF/dcc-2014-05.pdf},
abstract = {Valve-point loading affects the input-output
characteristics of generating units, bringing the
fuel costs nonlinear and nonsmooth. This has been
considered in the solution of load dispatch
problems, but not in the planning phase of unit
commitment. This paper presents a mathematical
optimization model for the thermal unit commitment
problem considering valve-point loading. The
formulation is based on a careful linearization of
the fuel cost function, which is modeled with great
detail on power regions being used in the current
solution, and roughly on other regions. A set of
benchmark instances for this problem is used for
analyzing the method, with recourse to a
general-purpose mixed-integer optimization solver.}
}
@article{pedroso2014aims,
author = {Margarida Carvalho and Jo{\~a}o P. Pedroso and
Jo{\~a}o Saraiva},
title = {Electricity Day-Ahead Markets: Computation of Nash
Equilibria},
journal = {Journal of Industrial and Management Optimization},
volume = 11,
number = 3,
pages = {985--998},
year = 2014,
doi = {10.3934/jimo.2015.11.985},
url = {http://aimsciences.org/journals/displayArticlesnew.jsp?paperID=10449},
issn = {1547-5816},
abstract = {In a restructured electricity sector, day-ahead
markets can be modeled as a game where some players
- the producers - submit their proposals. To analyze
the companies' behavior we have used the concept of
Nash equilibrium as a solution in these multi-agent
interaction problems. In this paper, we present new
and crucial adaptations of two well-known
mechanisms, the adjustment process and the
relaxation algorithm, in order to achieve the goal
of computing Nash equilibria. The advantages of
these approaches are highlighted and compared with
those available in the literature.},
publisher = {American Institute of Mathematical Sciences},
pdf = {PDF/nash_elect_2011.pdf}
}
@article{pedroso2014cor,
title = {Fast pattern-based algorithms for cutting stock},
journal = {Computers \& Operations Research },
volume = 48,
pages = {69--80},
year = 2014,
issn = {0305-0548},
doi = {http://dx.doi.org/10.1016/j.cor.2014.03.003},
url = {http://www.sciencedirect.com/science/article/pii/S0305054814000525},
author = {Filipe Brand{\~a}o and Jo{\~a}o Pedro Pedroso},
abstract = {The conventional assignment-based first/best fit
decreasing algorithms (FFD/BFD) are not polynomial
in the one-dimensional cutting stock input size in
its most common format. Therefore, even for small
instances with large demands, it is difficult to
compute FFD/BFD solutions. We present pattern-based
methods that overcome the main problems of
conventional heuristics in cutting stock problems by
representing the solution in a much more compact
format. Using our pattern-based heuristics, FFD/BFD
solutions for extremely large cutting stock
instances, with billions of items, can be found in a
very short amount of time.},
keywords = {Cutting stock},
keywords = {First fit decreasing},
keywords = {Best fit decreasing },
pdf = {PDF/COR2014.pdf}
}
@article{pedroso2014ijdats,
author = {Nicolau Santos and Rui Rebelo and Jo{\~a}o
P. Pedroso},
title = {A Tabu Search for the Flowshop Scheduling Problem
with Sequence Dependent Setup Times},
year = 2014,
journal = {International Journal of Data Analysis Techniques
and Strategies},
volume = 6,
number = 3,
pages = {275--285},
abstract = {In this work we present a tabu search metaheuristic
method for solving the permutation flow shop
scheduling problem with sequence dependent setup
times and the objective of minimizing total weighted
tardiness. The problem is well known for its
practical applications and for the difficulty in
obtaining good solutions. The tabu search method
proposed is based on the insertion neighborhood, and
is characterized by the selection and evaluation of
a small subset of this neighborhood at each
iteration; this has consequences both on
diversification and intensification of the
search. We also propose a speed-up technique based
on book keeping information of the current solution,
used for the evaluation of its neighbors. },
pdf = {PDF/ts_pfs_ijdats_2012.pdf}
}
@article{pedroso2014ijepes,
title = {Metaheuristic search based methods for unit
commitment },
journal = {International Journal of Electrical Power and Energy
Systems },
volume = 59,
number = 0,
pages = {14 - 22},
year = 2014,
issn = {0142-0615},
doi = {http://dx.doi.org/10.1016/j.ijepes.2014.01.038},
url = {http://www.sciencedirect.com/science/article/pii/S0142061514000519},
author = {Dewan Fayzur Rahman and Ana Viana and Jo{\~a}o Pedro
Pedroso},
keywords = {Unit commitment},
keywords = {Combinatorial optimization},
keywords = {Matheuristics },
abstract = {This paper presents two new solution approaches
capable of finding optimal solutions for the thermal
unit commitment problem in power generation
planning. The approaches explore the concept of
"matheuristics", a term usually used to refer to an
optimization algorithm that hybridizes
(meta)heuristics with mixed integer programming
solvers, in order to speed up convergence to
optimality for large scale instances. Two algorithms
are proposed: "local branching", and an
hybridization of particle swarm optimization with a
mixed integer programming solver. From extensive
computational tests on a broad set of benchmarks,
the algorithms were found to be able to solve large
instances. Optimal solutions were obtained for
several well-known situations with dramatic
reductions in CPU time for the larger cases, when
compared to previously proposed exact methods.},
pdf = {PDF/ucp-ijepes-2014.pdf}
}
@incollection{pedroso2014lncsCOA,
year = 2014,
isbn = {978-3-319-09128-0},
booktitle = {Computational Science and Its Applications -- ICCSA
2014},
volume = 8580,
series = {Lecture Notes in Computer Science},
editor = {Murgante, Beniamino and Misra, Sanjay and Rocha, Ana
Maria A.C. and Torre, Carmelo and Rocha, Jorge
Gustavo and Falc{\~a}o, Maria Irene and Taniar,
David and Apduhan, Bernady O. and Gervasi, Osvaldo},
doi = {10.1007/978-3-319-09129-7_3},
title = {Maximizing Expectation on Vertex-Disjoint Cycle
Packing},
url = {http://dx.doi.org/10.1007/978-3-319-09129-7_3, },
pdf = {PDF/DCC-2013-05_KEP.pdf},
publisher = {Springer International Publishing},
keywords = {Kidney exchange programs; Cycle packing; Expectation
optimization; Combinatorial optimization},
author = {Pedroso, Jo{\~a}o Pedro},
pages = {32-46},
language = {English},
abstract = {This paper proposes a method for computing the
expectation for the length of a maximum set of
vertex-disjoint cycles in a digraph where vertices
and/or arcs are subject to failure with a known
probability. This method has an immediate practical
application: it can be used for the solution of a
kidney exchange program in the common situation
where the underlying graph is unreliable. Results
for realistic benchmark instances are reported and
analyzed.}
}
@inproceedings{pedroso2014tron,
author = {Jo{\~a}o Pedro Pedroso},
title = {Optimization and Artificial Intelligence for Smart
Devices},
booktitle = {T-Engine Forum},
year = 2014,
address = {Tokyo, Japan},
organization = {IEEE Consumer Electronics Society},
pdf = {PDF/ia-smart-devices.pdf}
}
@incollection{pedroso2014ucpFayzur,
year = 2014,
isbn = {978-3-319-00794-6},
booktitle = {Operations Research Proceedings 2012},
series = {Operations Research Proceedings},
editor = {Helber, Stefan and Breitner, Michael and R{\"o}sch,
Daniel and Sch{\"o}n, Cornelia and Graf von der
Schulenburg, Johann-Matthias and Sibbertsen, Philipp
and Steinbach, Marc and Weber, Stefan and Wolter,
Anja},
doi = {10.1007/978-3-319-00795-3_23},
title = {A {MILP}-Based Approach for Hydrothermal Scheduling},
url = {http://dx.doi.org/10.1007/978-3-319-00795-3_23},
publisher = {Springer International Publishing},
author = {Rahman, Dewan Fayzur and Viana, Ana and Pedroso,
Jo{\~a}o Pedro},
abstract = {This paper presents new solution approaches capable
of finding optimal solutions for the Hydrothermal
Scheduling Problem (HSP) in power generation
planning. The problem has been proven to be NP-hard
and no exact methods have been able to tackle it,
for problem sizes of practical relevance. We explore
three approaches. The first method is an iterative
algorithm that has been successfully used previously
to solve the thermal commitment problem. The two
other methods are "Local Branching" and a
hybridization of "Particle Swarm Optimization" with
a general purpose solver. Computational experiments
show that the iterative piecewise linear
approximation method outperforms more elaborated
approaches, indicating that recourse to
matheuristics for solving this problem is not
necessary.},
pages = {157-162},
language = {English},
pdf = {PDF/MILP-HydSched-2012.pdf}
}
@incollection{pedroso2015mctsASO,
isbn = {978-3-319-15032-1},
booktitle = {Applied Simulation and Optimization},
editor = {Mujica Mota, Miguel and De La Mota, Idalia Flores
and Guimarans Serrano, Daniel},
doi = {10.1007/978-3-319-15033-8_4},
title = {Tree Search and Simulation},
url = {http://dx.doi.org/10.1007/978-3-319-15033-8_4},
publisher = {Springer International Publishing},
author = {Jo{\~a}o P. Pedroso and Rui Rei},
pages = {109-131},
year = 2015,
abstract = {This chapter presents a methodology for embodying
simulation as part of a tree search procedure, as a
technique for solving practical problems in
combinatorial optimization. Target problems either
are difficult to express as mixed integer
optimization models, or have models which provide
rather loose bounds; in both cases, traditional,
exact methods typically fail. The idea used is to
have tree search instantiating part of the
variables, in a systematic way, and for that
particular instantiation---a node in the search
tree---resort to a simulation for assigning values
to the remaining variables; then, use the outcome of
the simulation for evaluating that node in the tree.
This method has been used with considerable success
in game playing, but has received very limited
attention as a tool for optimization. Nevertheless,
it has great potential, either as a way for
improving known heuristics or as an alternative to
metaheuristics. We depart from repeated, randomized
simulation based on problem-specific heuristics for
applications in scheduling, logistics, and packing,
and show how the systematic search in a tree
improves the results that can be obtained.},
pdf = {PDF/mcts_chapter.pdf}
}
@article{pedroso2015scp,
title = {Certifying execution time in multicores },
journal = {Science of Computer Programming },
volume = 111,
number = {P3},
pages = {505--534},
month = {November},
year = 2015,
issn = {0167-6423},
doi = {10.1016/j.scico.2015.06.006},
url = {http://dx.doi.org/10.1016/j.scico.2015.06.006},
author = {V{\'\i}tor Rodrigues and Benny Akesson and M{\'a}rio
Florido and Sim{\~a}o Melo de Sousa and Jo{\~a}o
Pedro Pedroso and Pedro Vasconcelos},
keywords = {Abstract interpretation},
keywords = {Verification},
keywords = {\{ACC\}},
keywords = {\{WCET\}},
keywords = {\{LP\}},
keywords = {\{LR\} -servers },
abstract = {Abstract This article presents a semantics-based
program verification framework for critical embedded
real-time systems using the worst-case execution
time (WCET) as the safety parameter. The
verification algorithm is designed to run on devices
with limited computational resources where efficient
resource usage is a requirement. For this purpose,
the framework of abstract-carrying code (ACC) is
extended with an additional verification mechanism
for linear programming (LP) by applying the
certifying properties of duality theory to check the
optimality of \{WCET\} estimates. Further, the
\{WCET\} verification approach preserves feasibility
and scalability when applied to multicore
architectural models. The certifying \{WCET\}
algorithm is targeted to architectural models based
on the \{ARM\} instruction set and is presented as a
particular instantiation of a compositional
data-flow framework supported on the theoretic
foundations of denotational semantics and abstract
interpretation. The data-flow framework has
algebraic properties that provide algorithmic
transformations to increase verification efficiency,
mainly in terms of verification time. The \{WCET\}
analysis/verification on multicore architectures
applies the formalism of latency-rate ( \{LR\} )
servers, and proves its correcteness in the context
of abstract interpretation, in order to ease
\{WCET\} estimation of programs sharing resources. },
pdf = {PDF/certET2015.pdf}
}
@article{pedroso2016EPSR,
title = {A multiple criteria utility-based approach for unit
commitment with wind power and pumped storage hydro
},
journal = {Electric Power Systems Research },
volume = 131,
pages = {244 - 254},
year = 2016,
issn = {0378-7796},
doi = {http://dx.doi.org/10.1016/j.epsr.2015.10.024},
url = {http://www.sciencedirect.com/science/article/pii/S037877961500320X},
author = {Bruno Vieira and Ana Viana and Manuel Matos and
Jo{\~a}o Pedro Pedroso},
keywords = {Multiple criteria analysis},
keywords = {Utility theory},
keywords = {Uncertainty modelling},
keywords = {Unit commitment},
keywords = {Wind power },
abstract = {Abstract The integration of wind power in
electricity generation brings new challenges to the
unit commitment problem, as a result of the random
nature of the wind speed. The scheduling of thermal
generation units at the day-ahead stage is usually
based on wind power forecasts. Due to technical
limitations of thermal units, deviations from those
forecasts during intra-day operations may lead to
unwanted consequences, such as load shedding and
increased operating costs. Wind power forecasting
uncertainty has been handled in practice by means of
conservative stochastic scenario-based optimization
models, or through additional operating reserve
settings. However, generation companies may have
different attitudes towards the risks associated to
wind power variability. In this paper, operating
costs and load shedding are modeled by non-linear
utility functions aggregated into a single additive
utility function of a multi-objective
model. Computational experiments have been done to
validate the approach: firstly we test our model for
the wind–thermal unit commitment problem and, in a
second stage, pumped storage hydro units are added,
leading to a model with wind–hydro-thermal
coordination. Results have shown that the proposed
methodology is able to correctly reflect different
risk profiles of decision makers for both models. },
pdf = {PDF/Vieira_MC-UCP-WindHydro_2016.pdf}
}
@article{pedroso2016corBPP,
title = {Bin packing and related problems: General arc-flow
formulation with graph compression },
journal = {Computers \& Operations Research },
volume = 69,
pages = {56 - 67},
year = 2016,
issn = {0305-0548},
doi = {http://dx.doi.org/10.1016/j.cor.2015.11.009},
url = {http://www.sciencedirect.com/science/article/pii/S0305054815002762},
author = {Filipe Brand{\~a}o and Jo{\~a}o Pedro Pedroso},
keywords = {Bin packing},
keywords = {Cutting stock},
keywords = {Vector packing},
keywords = {Arc-flow formulation },
abstract = {Abstract We present an exact method, based on an
arc-flow formulation with side constraints, for
solving bin packing and cutting stock
problems—including multi-constraint variants—by
simply representing all the patterns in a very
compact graph. Our method includes a graph
compression algorithm that usually reduces the size
of the underlying graph substantially without
weakening the model. Our formulation is equivalent
to Gilmore and Gomory׳s, thus providing a very
strong linear relaxation. However, instead of using
column-generation in an iterative process, the
method constructs a graph, where paths from the
source to the target node represent every valid
packing pattern. The same method, without any
problem-specific parameterization, was used to solve
a large variety of instances from several different
cutting and packing problems. In this paper, we deal
with vector packing, bin packing, cutting stock,
cardinality constrained bin packing, cutting stock
with cutting knife limitation, bin packing with
conflicts, and other problems. We report
computational results obtained with many benchmark
test datasets, some of them showing a large
advantage of this formulation with respect to the
traditional ones. },
pdf = {PDF/BrandaoPedroso_COR_2016.pdf}
}
@article{pedroso2016corKEP,
title = {Maximising expectation of the number of transplants
in kidney exchange programmes },
journal = {Computers \& Operations Research },
volume = 73,
pages = {1 - 11},
year = 2016,
issn = {0305-0548},
doi = {http://dx.doi.org/10.1016/j.cor.2016.03.004},
url = {http://www.sciencedirect.com/science/article/pii/S0305054816300533},
author = {Xenia Klimentova and João Pedro Pedroso and Ana
Viana},
keywords = {Kidney exchange programmes},
keywords = {Cycle packing},
keywords = {Expectation optimisation },
abstract = {This paper addresses the problem of maximising the
expected number of transplants in kidney exchange
programmes. New schemes for matching rearrangement
in case of failure are presented, along with a new
tree search algorithm used for the computation of
optimal expected values. Extensive computational
experiments demonstrate the effectiveness of the
algorithm and reveal a clear superiority of a newly
proposed scheme, subset-recourse, as compared to
previously known approaches. },
pdf = {PDF/kep-kpv-caor-2016.pdf}
}
@article{pedroso2016itorOCC,
author = {Pedroso, Jo{\~a}o Pedro and Cunha, S{\'\i}lvia and
Tavares, Jo{\~a}o Nuno},
title = {Recursive circle packing problems},
journal = {International Transactions in Operational Research},
volume = 23,
number = {1-2},
issn = {1475-3995},
url = {http://dx.doi.org/10.1111/itor.12107},
doi = {10.1111/itor.12107},
pages = {355--368},
keywords = {packing problems, knapsack problems, heuristics,
practice of OR, combinatorial optimization, integer
programming, loading problems, local search},
year = 2016,
pdf = {PDF/ITOR-RCP-2015.pdf}
}
@article{pedroso2016mathprog,
author = {Carvalho, Margarida and Lodi, Andrea and Pedroso,
Jo{\~a}o Pedro and Viana, Ana},
title = {Nash equilibria in the two-player kidney exchange
game},
journal = {Mathematical Programming},
year = {2016},
pages = {1--29},
issn = {1436-4646},
doi = {10.1007/s10107-016-1013-7},
url = {http://dx.doi.org/10.1007/s10107-016-1013-7},
abstract = {Kidney exchange programs have been set in several
countries within national, regional or hospital
frameworks, to increase the possibility of kidney
patients being transplanted. For the case of
hospital programs, it has been claimed that
hospitals would benefit if they collaborated with
each other, sharing their internal pools and
allowing transplants involving patients of different
hospitals. This claim led to the study of
multi-hospital exchange markets. We propose a novel
direction in this setting by modeling the exchange
market as an integer programming game. The analysis
of the strategic behavior of the entities
participating in the kidney exchange game allowed us
to prove that the most rational game outcome
maximizes the social welfare and that it can be
computed in polynomial time.}
}
@article{pedroso2016forest,
author = {Neto, Teresa and Constantino, Miguel and Martins,
Isabel and Pedroso, João Pedro},
year = {2016},
title = {Forest harvest scheduling with clearcut and core
area constraints},
journal = {Annals of Operations Research},
issn = {0254-5330},
doi = {10.1007/s10479-016-2313-2},
url = {https://dx.doi.org/10.1007/s10479-016-2313-2},
month = {9},
abstract = {Many studies regarding environmental concerns in
forest harvest scheduling problems deal with
constraints on the maximum clearcut size. However,
these constraints tend to disperse harvests across
the forest and thus to generate a more fragmented
landscape. When a forest is fragmented, the amount
of edge increases at the expense of the core
area. Highly fragmented forests can neither provide
the food, cover, nor the reproduction needs of
core-dependent species. This study presents a
branch-and-bound procedure designed to find good
feasible solutions, in a reasonable time, for forest
harvest scheduling problems with constraints on
maximum clearcut size and minimum core habitat
area. The core area is measured by applying the
concept of subregions. In each branch of the
branch-and-bound tree, a partial solution leads to
two children nodes, corresponding to the cases of
harvesting or not a given stand in a given
period. Pruning is based on constraint violations or
unreachable objective values. The approach was
tested with forests ranging from some dozens to more
than a thousand stands. In general, branch-and-bound
was able to quickly find optimal or good solutions,
even for medium/large instances.}
}
@proceedings{procICEC98,
title = {Proceedings of the 1998 IEEE International
Conference on Evolutionary Computation - ICEC 98},
year = 1998,
number = 1,
series = {98TH8360},
organization = {IEEE},
address = {Anchorage, Alaska}
}
@proceedings{procNOLTA2001,
title = {Proceedings of the 2001 International Symposium on
Nonlinear Theory and its Applications},
year = 2001,
address = {Miyagi, Japan}
}
@proceedings{procNOLTA97,
key = {procNOLTA97},
title = {Proceedings of the 1997 International Symposium on
Nonlinear Theory and its Applications},
year = 1997,
publisher = {Research Society of Nonlinear Theory and its
Applications},
address = {Honolulu}
}
@proceedings{zzz:DBLP:conf/fopara/2011,
editor = {Ricardo Pe{\~n}a and Marko C. J. D. van Eekelen and
Olha Shkaravska},
title = {Foundational and Practical Aspects of Resource
Analysis - Second International Workshop, FOPARA
2011, Madrid, Spain, May 19, 2011, Revised Selected
Papers},
booktitle = {FOPARA},
publisher = {Springer},
series = {Lecture Notes in Computer Science},
volume = 7177,
year = 2012,
isbn = {978-3-642-32494-9},
ee = {http://dx.doi.org/10.1007/978-3-642-32495-6},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@proceedings{zzz:DBLP:conf/hm/2005,
editor = {Maria J. Blesa and Christian Blum and Andrea Roli
and Michael Sampels},
title = {Hybrid Metaheuristics, Second International
Workshop, HM 2005, Barcelona, Spain, August 29-30,
2005, Proceedings},
booktitle = {Hybrid Metaheuristics},
publisher = {Springer},
series = {Lecture Notes in Computer Science},
volume = 3636,
year = 2005,
isbn = {3-540-28535-0},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@proceedings{zzz:DBLP:conf/lion/2012,
editor = {Youssef Hamadi and Marc Schoenauer},
title = {Learning and Intelligent Optimization - 6th
International Conference, LION 6, Paris, France,
January 16-20, 2012, Revised Selected Papers},
booktitle = {LION},
publisher = {Springer},
series = {Lecture Notes in Computer Science},
volume = 7219,
year = 2012,
isbn = {978-3-642-34412-1},
ee = {http://dx.doi.org/10.1007/978-3-642-34413-8},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@proceedings{zzz:DBLP:conf/mco/2008,
editor = {Le Thi Hoai An and Pascal Bouvry and Pham Dinh Tao},
title = {Modelling, Computation and Optimization in
Information Systems and Management Sciences, Second
International Conference, MCO 2008, Metz, France -
Luxembourg, September 8-10, 2008. Proceedings},
booktitle = {MCO},
publisher = {Springer},
series = {Communications in Computer and Information Science},
volume = 14,
year = 2008,
isbn = {978-3-540-87476-8},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@proceedings{zzz:DBLP:conf/nma/2010,
editor = {Ivan Dimov and Stefka Dimova and Natalia
T. Kolkovska},
title = {Numerical Methods and Applications - 7th
International Conference, NMA 2010, Borovets,
Bulgaria, August 20-24, 2010. Revised Papers},
booktitle = {NMA},
publisher = {Springer},
series = {Lecture Notes in Computer Science},
volume = 6046,
year = 2011,
isbn = {978-3-642-18465-9},
ee = {http://dx.doi.org/10.1007/978-3-642-18466-6},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@proceedings{zzz:DBLP:conf/ppsn/1996,
editor = {Hans-Michael Voigt and Werner Ebeling and Ingo
Rechenberger and Hans-Paul Schwefel},
title = {Parallel Problem Solving from Nature - PPSN IV,
International Conference on Evolutionary
Computation. The 4th International Conference on
Parallel Problem Solving from Nature, Berlin,
Germany, September 22-26, 1996, Proceedings},
booktitle = {PPSN},
publisher = {Springer},
series = {Lecture Notes in Computer Science},
volume = 1141,
year = 1996,
isbn = {3-540-61723-X},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@proceedings{zzz:DBLP:conf/sls/2007,
editor = {Thomas St{\"u}tzle and Mauro Birattari and Holger
H. Hoos},
title = {Engineering Stochastic Local Search
Algorithms. Designing, Implementing and Analyzing
Effective Heuristics, International Workshop, SLS
2007, Brussels, Belgium, September 6-8, 2007,
Proceedings},
booktitle = {SLS},
publisher = {Springer},
series = {Lecture Notes in Computer Science},
volume = 4638,
year = 2007,
isbn = {978-3-540-74445-0},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
This file was generated by bibtex2html 1.96.