Publications 2021

  1. Home
  2. Publications

Articles


13.  Robust formulations for economic lot-sizing problem with remanufacturing

Attila, Öykü Naz and Agra, Agostinho and Akartunalı, Kerem and Arulselvan, Ashwin

European Journal of Operational Research

Elsevier

In this paper, we consider a lot-sizing problem with the remanufacturing option under parameter uncertainties imposed on demands and returns. Remanufacturing has recently been a fast growing area of interest for many researchers due to increasing awareness on reducing waste in production environments, and in particular studies involving remanufacturing and parameter uncertainties simultaneously are very scarce in the literature. We first present a min-max decomposition approach for this problem, where decision maker’s problem and adversarial problem are treated iteratively. Then, we propose two novel extended reformulations for the decision maker’s problem, addressing some of the computational challenges. An original aspect of the reformulations is that they are applied only to the latest scenario added to the decision maker’s problem. Then, we present an extensive computational analysis, which provides a detailed comparison of the three formulations and evaluates the impact of key problem parameters. We conclude that the proposed extended reformulations outperform the standard formulation for a majority of the instances. We also provide insights on the impact of the problem parameters on the computational performance.

ria.ua.pt | doi | Peer Reviewed

12.  The degrees of toroidal regular proper hypermaps

Fernandes, Maria Elisa and Piedade, Claudio Alexandre

The Art of Discrete and Applied Mathematics

Slovenian Discrete and Applied Mathematics Society; University of Primorska, FAMNI

Recently the classification of all possible faithful transitive permutation representations of the group of symmetries of a regular toroidal map was accomplished. In this paper we complete this investigation on a surface of genus 1 considering the group of a regular toroidal hypermap of type (3,3,3).

ria.ua.pt | doi | Peer Reviewed

11.  The H-join of arbitrary families of graphs

Cardoso, Domingos M. and Gomes, Helena and Pinheiro, Sofia J

arXiv

The H-join of a family of graphs G = {G1, . . . , Gp}, also called the generalized composition, H[G1, . . . , Gp], where all graphs are undirected, simple and finite, is the graph obtained from the graph H replacing each vertex i of H by Gi and adding to the edges of all graphs in G the edges of the join Gi ∨ Gj , for every edge ij of H. Some well known graph operations are particular cases of the H-join of a family of graphs G as it is the case of the lexicographic product (also called composition) of two graphs H and G, H[G], which coincides with the H-join of family of graphs G where all the graphs in G are isomorphic to a fixed graph G. So far, the known expressions for the determination of the entire spectrum of the H-join in terms of the spectra of its components and an associated matrix are limited to families of regular graphs. In this paper, we extend such a determination to families of arbitrary graphs.

ria.ua.pt

10.  On circulant like matrices properties involving Horadam, Fibonacci, Jacobsthal and Pell numbers

Andrade, Enide and Carrasco-Olivera, Dante and Manzaneda, Cristina

Linear Algebra and its Applications

Elsevier

In this work a new type of matrix called circulant-like matrix is introduced. This type of matrix includes the classical k-circulant matrix, introduced in [4], in a natural sense. Its eigenvalues and its inverse and some other properties are studied, namely, it is shown that the inverse of a matrix of this type is also a matrix of this type and that its first row is the unique solution of a certain system of linear equations. Additionally, for some of these matrices whose entries are written as function of Horadam, Fibonacci, Jacobsthal and Pell numbers we study its eigenvalues and write it as function of those numbers. Moreover, the same study is done if the entries are arithmetic sequences.

ria.ua.pt | doi | Peer Reviewed

9.  Two families of locally toroidal regular 4-hypertopes arising from toroids

Fernandes, Maria Elisa and Leemans, Dimitri and Piedade, Claudio Alexandre and Weiss, Asia Ivić

Contemporary Mathematics

American Mathematical Society

In this paper we present two infinite families of locally toroidal hypertopes of rank 4 that are constructed from regular toroids of types {4, 3, 4}_(s,s,0) and {3, 3, 4, 3}_(s,0,0,0). The Coxeter diagram of the first of the two families is star-shaped and the diagram of the other is a square. In both cases the toroidal residues are regular toroidal maps of type {3, 6}.

ria.ua.pt | doi | Peer Reviewed

8.  On strong duality in linear copositive programming

Kostyukova, O. I. and Tchemisova, T. V.

Journal of Global Optimization

Springer

The paper is dedicated to the study of strong duality for a problem of linear copositive programming. Based on the recently introduced concept of the set of normalized immobile indices, an extended dual problem is deduced. The dual problem satisfies the strong dual ity relations and does not require any additional regularity assumptions such as constraint qualifications. The main difference with the previously obtained results consists in the fact that now the extended dual problem uses neither the immobile indices themselves nor the explicit information about the convex hull of these indices. The strong duality formulations presented in the paper for linear copositive problems have similar structure and properties as that proposed in the works by M. Ramana, L. Tuncel, and H. Wolkowicz, for semidefinite programming.

ria.ua.pt | doi | Peer Reviewed

7.  Weighted proximity search

Rodrigues, Filipe and Agra, Agostinho and Hvattum, Lars Magnus and Requejo, Cristina

Journal of Heuristics

Springer

Proximity search is an iterative method to solve complex mathematical programming problems. At each iteration, the objective function of the problem at hand is replaced by the Hamming distance function to a given solution, and a cutoff constraint is added to impose that any new obtained solution improves the objective function value. A mixed integer programming solver is used to find a feasible solution to this modified problem, yielding an improved solution to the original problem. This paper introduces the concept of weighted Hamming distance that allows to design a new method called weighted proximity search. In this new distance function, low weights are associated with the variables whose value in the current solution is promising to change in order to find an improved solution, while high weights are assigned to variables that are expected to remain unchanged. The weights help to distinguish between alternative solutions in the neighborhood of the current solution, and provide guidance to the solver when trying to locate an improved solution. Several strategies to determine weights are presented, including both static and dynamic strategies. The proposed weighted proximity search is compared with the classic proximity search on instances from three optimization problems: the p-median problem, the set covering problem, and the stochastic lot-sizing problem. The obtained results show that a suitable choice of weights allows the weighted proximity search to obtain better solutions, for 75% of the cases, than the ones obtained by using proximity search and for 96% of the cases the solutions are better than the ones obtained by running a commercial solver with a time limit.

ria.ua.pt | doi | Peer Reviewed

6.  Lagrangian duality for robust problems with decomposable functions: the case of a robust inventory problem

Rodrigues, Filipe and Agra, Agostinho and Requejo, Cristina and Delage, Erick

INFORMS Journal on Computing

INFORMS

We consider a class of min-max robust problems in which the functions that need to be “robustified” can be decomposed as the sum of arbitrary functions. This class of problems includes many practical problems, such as the lot-sizing problem under demand uncertainty. By considering a Lagrangian relaxation of the uncertainty set, we derive a tractable approximation, called the dual Lagrangian approach, that we relate with both the classical dualization approximation approach and an exact approach. Moreover, we show that the dual Lagrangian approach coincides with the affine decision rule approximation approach. The dual Lagrangian approach is applied to a lot-sizing problem, in which demands are assumed to be uncertain and to belong to the uncertainty set with a budget constraint for each time period. Using the insights provided by the interpretation of the Lagrangian multipliers as penalties in the proposed approach, two heuristic strategies, a new guided iterated local search heuristic, and a subgradient optimization method are designed to solve more complex lot-sizing problems in which additional practical aspects, such as setup costs, are considered. Computational results show the efficiency of the proposed heuristics that provide a good compromise between the quality of the robust solutions and the running time required in their computation.

ria.ua.pt | doi | Peer Reviewed

5.  Face reduction and the immobile indices approaches to regularization of linear Copositive Programming problems

Kostyukova, O. I. and Tchemisova, T. V.

arXiv

The paper is devoted to the regularization of linear Copositive Programming problems which consists of transforming a problem to an equivalent form, where the Slater condition is satisfied and the strong duality holds. We describe here two regularization algorithms based on the concept of immobile indices and an understanding of the important role these indices play in the feasible sets' characterization. These algorithms are compared to some regularization procedures developed for a more general case of convex problems and based on a facial reduction approach. We show that the immobile-index-based approach combined with the specifics of copositive problems allows us to construct more explicit and detailed regularization algorithms for linear Copositive Programming problems than those already available.

ria.ua.pt

4.  Structural properties of faces of the cone of copositive matrices

Kostyukova, Olga and Tchemisova, Tatiana

Mathematics

MDPI

In this paper, we study the properties of faces and exposed faces of the cone of copositive matrices (copositive cone), paying special attention to issues related to their geometric structure. Based on the concepts of zero and minimal zero vectors, we obtain several explicit representations of faces of the copositive cone and compare them. Given a face of the cone of copositive matrices, we describe the subspace generated by that face and the minimal exposed face containing it. Summarizing the results obtained in the paper, we systematically show what information can be extracted about the given copositive face in the case of incomplete data. Several examples for illustrating the main findings of the paper and also for justifying the usefulness of the developed approach to the study of the facial structure of the copositive cone are discussed.

ria.ua.pt | doi | Peer Reviewed

3.  An exact robust approach for the integrated berth allocation and quay crane scheduling problem under uncertain arrival times

Rodrigues, Filipe and Agra, Agostinho

European Journal of Operational Research

Elsevier

We consider an integrated berth allocation and quay crane assignment and scheduling problem where the arrival times of the vessels may be affected by uncertainty. The problem is modelled as a two-stage robust mixed integer program where the berth allocation decisions are taken before the exact arrival times are known, and the crane assignment and scheduling operations are adjusted to the arrival times. To solve the robust two-stage model, we follow a decomposition algorithm that decomposes the problem into a master problem and a separation problem. A new scenario reduction procedure for solving the separation problem is proposed as well as a warm start technique for reducing the number of iterations performed by the decomposition algorithm. To scale the proposed decomposition algorithm for large size instances, it is combined with a rolling horizon heuristic.The efficiency and effectiveness of the proposed algorithms are demonstrated through extensive computational experiments carried out on randomly generated instances with both homogeneous and heterogeneous cranes as well as on instances from the literature.

ria.ua.pt | doi | Peer Reviewed

2.  Method of nose stretching in Newton's problem of minimal resistance

Plakhov, Alexander

Nonlinearity

IOP Publishing

We consider the problem $infbig{ int!!int_Omega (1 + |nabla u(x_1,x_2)|^2)^{-1} dx_1 dx_2 : text{ the function } u : Omega to mathbb{R} text{ is concave and } 0 le u(x) le M text{ for all } x = (x_1, x_2) in Omega ={ |x| le 1 } , big}$ (Newton's problem) and its generalizations. In the paper by Brock, Ferone, and Kawohl (1996) it is proved that if a solution $u$ is $C^2$ in an open set $mathcal{U} subset Omega$ then $det D^2u = 0$ in $mathcal{U}$. It follows that graph$(u)rfloor_mathcal{U}$ does not contain extreme points of the subgraph of $u$. In this paper we prove a somewhat stronger result. Namely, there exists a solution $u$ possessing the following property. If $u$ is $C^1$ in an open set $mathcal{U} subset Omega$ then graph$(urfloor_mathcal{U})$ does not contain extreme points of the convex body $C_u = { (x,z) :, x in Omega, 0 le z le u(x) }$. As a consequence, we have $C_u = text{rm Conv} (overline{text{rm Sing$C_u$}})$, where Sing$C_u$ denotes the set of singular points of $partial C_u$. We prove a similar result for a generalization of Newton's problem.

ria.ua.pt | doi | Peer Reviewed

1.  On generalized Newton's aerodynamic problem

Plakhov, Alexander

Transactions of the Moscow Mathematical Society

American Mathematical Society

We consider the generalized Newton's least resistance problem for convex bodies: minimize the functional $int!!int_Omega (1 + |nabla u(x,y)|^2)^{-1} dx, dy$ in the class of concave functions $u: Omega to [0,M]$, where the domain $Omega subset mathbb{R}^2$ is convex and bounded and $M > 0$. It has been known cite{BFK} that if $u$ solves the problem then $|nabla u(x,y)| ge 1$ at all regular points $(x,y)$ such that $u(x,y) < M$. We prove that if the upper level set $L = { (x,y): u(x,y) = M }$ has nonempty interior, then for almost all points of its boundary $(bar x, bar y) in pl L$ one has $lim_{stackrel{(x,y)to(bar x,bar y)}{u(x,y)

ria.ua.pt | Peer Reviewed
(latest changes on 2021-12-02 10:09)

© 2019 CIDMA, all rights reserved