1,721,000 research outputs found
Theoretical and computational study of several linearisation techniques for binary quadratic problems
Full text linkWe perform a theoretical and computational study of the classical linearisation techniques (LT) and we propose a new LT for binary quadratic problems (BQPs). We discuss the relations between the linear programming (LP) relaxations of the considered LT for generic BQPs. We prove that for a specific class of BQP all the LTs have the same LP relaxation value. We also compare the LT computational performance for four different BQPs from the literature. We consider the Unconstrained BQP and the maximum cut of edge-weighted graphs and, in order to measure the effects of constraints on the computational performance, we also consider the quadratic extension of two classical combinatorial optimization problems, i.e., the knapsack and stable set problems
Robustness of solutions to the capacitated facility location problem with uncertain demand
Full text linkWe investigate the properties of robust solutions of the Capacitated Facility Location Problem with uncertain demand. We show that the monotonic behavior of the price of robustness is not guaranteed, and therefore that one cannot discriminate among alternative robust solutions by simply relying on the trade-off price-vs-robustness. Furthermore, we report a computational study on benchmark instances from the literature and on instances derived from a real-world application, which demonstrates the validity in practice of our findings
A trust-region framework for derivative-free mixed-integer optimization
No full textThis paper overviews the development of a framework for the optimization of black-box mixed-integer functions subject to bound constraints. Our methodology is based on the use of tailored surrogate approximations of the unknown objective function, in combination with a trust-region method. To construct suitable model approximations, we assume that the unknown objective is locally quadratic, and we prove that this leads to fully-linear models in restricted discrete neighborhoods. We show that the proposed algorithm converges to a first-order mixed-integer stationary point according to several natural definitions of mixed-integer stationarity, depending on the structure of the objective function. We present numerical results to illustrate the computational performance of different implementations of this methodology in comparison with the state-of-the-art derivative-free solver NOMAD
A conjugate direction based simplicial decomposition framework for solving a specific class of dense convex quadratic programs
Full text link
On the Product Knapsack Problem
No full textGiven a set of items, each characterized by a profit and a weight, we study the problem of maximizing the product of the profits of the selected items, while respecting a given capacity. To the best of our knowledge this is the first manuscript that studies this variant of the knapsack problem which we call Product Knapsack Problem (PKP). We show that PKP is weakly NP-hard. We propose and implement a Dynamic Programming algorithm and different Mixed Integer Linear and Nonlinear Programming formulations for the PKP. Finally, we present an extensive computational study on a large set of benchmark instances derived from the literature
A scalable combinatorial benders decomposition for the Stochastic Dial-a-Ride Problem
No full textNowadays, Demand-Responsive Transport companies can help the elderly or disabled citizens in their everyday journeys as well as provide an important link between big cities and their outer suburbs. In practice, many of those trips are scheduled in advance but many others are asked on the fly (online) by the users while the drivers are already on their routes. To answer those online requests, dispatching centers often rely on fast heuristics based on some myopic objectives. However, this deteriorates the flexibility of the dispatch over time. This paper shows the potential of a thorough optimization of the planning of the vehicles at the start of the day under the hypothesis that the transport company is able to forecast the requests that will arrive during the service. Our objective is to design an initial set of routes for the vehicles that maximizes the expected acceptance rate of future requests, since the ones scheduled in-advance are mandatory. In this prospect, we propose a Combinatorial Benders Decomposition framework to solve the so-called Stochastic Dial-a-Ride Problem. A key ingredient for the success of this solver is the use of a clustering-based initialization of the Master Problem. The computational results show the effectiveness of this approach when applied to instances extracted from the literature as well as from actual services provided by Padam Mobility, an international company in Shared Mobility Systems. The proposed method provides a substantial performance gain though traditional heuristics are kept to manage online insertions afterward
Effect of Vincristine on the bone marrow cells of patients with multiple myeloma: a cytomorphologic study.
No full textGoing 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
- …
