1,720,972 research outputs found
A Lagrangian approach for the minimum spanning tree problem with conflicting edge pairs
No full textThis article addresses the minimum spanning tree problem with conflicting edge pairs, a variant of the classical minimum spanning tree where, given a list of conflicting edges, the goal is to find the cheapest spanning tree with no edges in conflict. We adopt a Lagrangian relaxation approach together with a dual ascent and a subgradient procedure to find tight lower bounds on the optimal solution. The algorithm is also equipped with a heuristics approach which provides an upper bound by removing the conflicts from possible infeasible solutions met during the calculation of the lower bounds. The computational results, carried out on benchmark instances, show that the proposed algorithm finds the optimal solutions on several instances. Moreover, the lower bounds it provides are much more accurate than ones provided by other Lagrangian approaches available in the literature and they are computed is much less time
A two-phase approach for an integrated order batching and picker routing problem
No full textThis article addresses an integrated warehouse order picking problem. The company HappyChic is specialized in men’s ready-to-wear. A central warehouse is dedicated to supplying, every day, the shops of one brand. We focus on the picking area of this warehouse which relies on human picking system. For each picking wave (period of a working day), a set of customer orders has to be prepared. An order is a set of product references, with quantities, i.e., the numbers of items required. The problem consists in jointly deciding: (1) the division of orders into several boxes, respecting weight and size constraints; (2) the batching of boxes into trolleys, that implicitly defines the routing into the picking area. The objective function aims to minimize the total distance. To deal with the large size instances of HappyChic in short computation times, we design a heuristic method based on the split and dynamic programming paradigms. The results are very convincing: the total covered distance decreases by more than 20%. Moreover, we propose an adaptation of the algorithm to prepare homogeneous boxes with respect to classes of products. The logistic department of HappyChic is convinced by results obtained in this research work, and the warehouse management system is currently being updated in order to integrate the proposed algorithm
A new extended formulation with valid inequalities for the Capacitated Concentrator Location Problem
Full text linkWe present a new disaggregated formulation of the Capacitated Concentrator Location Problem (CCLP) using the notion of cardinality of terminals assigned to a concentrator. This formulation consists of O(mnn) variables and constraints, where m denotes the number of concentrators and n the number of terminals, respectively. We prove that this extended formulation is stronger than the traditional one. We also present two classes of inequalities exploiting the cardinality effect of the extended formulation. The first class is a generalization of the well-known Cover and (1, k)-Configuration inequalities, which collectively are stronger than the original Cover and (1, k)-Configuration inequalities. The second class, called the 2-Facility Cardinality Matching Inequality, holds for the uncapacitated version of the Concentrator Location Problem and can be lifted to become a strong inequality for CCLP. We solve the LP relaxation of the extended formulation and use separation heuristics to identify and sequentially add the previous valid inequalities to improve the lower bound. This approach is embedded in a branch-and-bound and results in a branch-and-cut approach. We test our solution approach on a large set of benchmark problems. The experimentation shows that we can identify the optimal solution at the root node in most of the problem instances with up to 50 concentrators and 50 terminals. For larger sized test problems with up to 100 concentrators and 1000 terminals, the branch-and-cut procedure using the disaggregated formulation outperforms the branch-and-cut procedure applied to the traditional formulation both in terms of CPU and the required number of branch-and-bound nodes
Feature selection in SVM via polyhedral k-norm
Full text linkWe treat the feature selection problem in the support vector machine (SVM) framework by adopting an optimization model based on use of the l pseudo-norm. The objective is to control the number of non-zero components of the normal vector to the separating hyperplane, while maintaining satisfactory classification accuracy. In our model the polyhedral norm ‖. ‖ [k], intermediate between ‖. ‖ 1 and ‖. ‖ ∞, plays a significant role, allowing us to come out with a DC (difference of convex) optimization problem that is tackled by means of DCA algorithm. The results of several numerical experiments on benchmark classification datasets are reported
Going Beyond Counting First Authors in Author Co-citation Analysis
Full text linkThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
Variations on the Author
Full text link“Variations on the Author” discusses two of Eduardo Coutinho’s recent films (Um Dia na Vida, from 2010, and Últimas Conversas, posthumously released in 2015) and their contribution to the general question of documentary authorship. The director’s filmography is characterized by a consistent yet self-effacing form of authorial self-inscription: Coutinho often features as an interviewer that rather than express opinions propels discourses; an interviewer that is good at listening. This mode of self-inscription characterizes him as an author who is not expressive but who is nonetheless markedly present on the screen. In Um Dia na Vida, however, Coutinho is completely absent form the image, while Últimas Conversas, on the contrary, includes a confessional prologue that moves the director from the margins to the center of his films. This article examines the ways in which these works stand out in the filmography of a director who offers new insights into the notion of cinematic authorship
A two-point heuristic to calculate the stepsize in subgradient method with application to a network design problem
No full textWe introduce a heuristic rule for calculating the stepsize in the subgradient method for unconstrained convex nonsmooth optimization which, unlike the classic approach, is based on retaining some information from previous iteration. The rule is inspired by the well known two- point stepsize by Barzilai and Borwein (BB) [6] for smooth optimization and it coincides with (BB) in case the function to be minimised is convex quadratic.
Under the use of appropriate safeguards we demonstrate that the method terminates at a point that satisfies an approximate optimality condition.
The proposed approach is tested in the framework of Lagrangian relaxation for integer linear programming where the Lagrangian dual requires maximization of a concave and nonsmooth (piecewise affine) function. In particular we focus on the relaxation of the Minimum Spanning Tree problem with Conflicting Edge Pairs (MSTC). Comparison with classic subgradient method is presented. The results on some widely used academic test problems are provided too
Appropriate Similarity Measures for Author Cocitation Analysis
Full text linkWe provide a number of new insights into the methodological discussion about author cocitation analysis. We first argue that the use of the Pearson correlation for measuring the similarity between authors’ cocitation profiles is not very satisfactory. We then discuss what kind of similarity measures may be used as an alternative to the Pearson correlation. We consider three similarity measures in particular. One is the well-known cosine. The other two similarity measures have not been used before in the bibliometric literature. Finally, we show by means of an example that our findings have a high practical relevance.information science;Pearson correlation;cosine;similarity measure;author cocitation analysis
- …
