565 research outputs found
Best and Worst Values of the Optimal Cost of the Interval Transportation Problem
No full textWe address the Interval Transportation Problem (ITP), that is, the transportation problem where supply and demand are uncertain and vary over given ranges. We are interested in determining the best and worst values of the optimal cost of the ITP among all the realizations of the uncertain parameters. In this paper, we prove some general properties of the best and worst optimum values from which the existing results derive as a special case. Additionally, we propose an Iterated Local Search algorithm to find a lower bound on the worst optimum value. Our algorithm is competitive compared to the existing approaches in terms of quality of the solution and in terms of computational time
Degenerate Flag Varieties of Type A and C are Schubert Varieties
No full textWe show that any type A or C degenerate flag variety is, in fact, isomorphic to a Schubert
variety in an appropriate partial flag manifold
Epidemiology of primary glaucoma: prevalence, incidence, and blinding effects
No full textCertain general conclusions can be drawn from a series of 56 studies on glaucoma prevalence. Even in the most recently published studies the rate of undiagnosed glaucoma is particularly high. Another fairly constant finding is the discrepancy between the clinical and epidemiologic diagnoses of glaucoma. The prevalence of primary open-angle glaucoma (POAG) has been increasing, and this trend is undoubtedly due at least in part to advances in diagnostic technology. The decreasing prevalence of primary angle-closure glaucoma (PACG) is due to the adoption of more stringent criteria for the diagnosis of this form of glaucoma. Prevalence increases proportionately with age for each racial group. African or African origin populations had the highest POAG prevalence at all ages but the increase in prevalence of POAG is steeper for white populations. PACG is commonest in Asian ethnic groups, with the exception of the Japanese. Low-tension glaucoma (LTG) is quite common in the Japanese population. Over 80% of those with PACG live in Asia, while POAG disproportionately affects those of African derivation. Women are more affected by glaucoma. Very few incidence studies have been completed, because the cost of examining large samples is high. There are only two recent studies conducted on persons of African descent in Barbados (West Indies) and on white inhabitants of Rotterdam (Netherlands). Risk of incident glaucoma was highest among persons classified as having suspect POAG at baseline, followed by those with ocular hypertension. No difference in incidence of POAG between men and women was found. The more recent studies which included routine visual-field testing reveal rates of blinding glaucoma <10% in many countries, including those that are developing
Flying Safely by Bilevel Programming
No full textPreventing aircraft from getting too close to each other is an essential element of safety of the air transportation industry, which becomes ever more important as the air traffic increases. The problem consists in enforcing a minimum distance threshold between flying aircraft, which naturally results in a bilevel formulation with a lower-level subproblem for each pair of aircraft. We propose two single-level reformulations, present a cut generation algorithm which directly solves the bilevel formulation and discuss comparative computational results
An efficient and simple approach to solve a distribution problem
No full textWe consider a distribution problem in a supply chain consisting of multiple plants, multiple regional warehouses, and multiple customers. We focus on the problem of selecting a given number of warehouses among a set of candidate ones, assigning each customer to one or more of the selected warehouses while minimizing costs. We present a mixed integer formulation of the problem of minimizing the sum of the total transportation costs and of the fixed cost associated with the opening of the selected warehouses. We develop a heuristic and a metaheuristic algorithm to solve it. The problem was motivated by the request of a company in the US which was interested both in determining the optimal solution of the problem using available optimization solvers, and in the design and implementation of a simple heuristic able to find good solutions (not farther than 1% from the optimum) in a short time. A series of computational experiments on randomly generated test problems is carried out. Our results show that the proposed solution approaches are a valuable tool to meet the needs of the company
On aircraft deconfliction by bilevel programming
No full textWe present a bilevel programming formulation for the aircraft deconfliction problem with multiple lower-level subproblems. We propose two reformulation based on the KKT conditions and the dual of the lower-level subproblems. Finally, we compare the results obtained implementing these formulations using global optimization solvers
The optimal value range problem for the Interval (immune)Transportation Problem
No full textWe address the problem of finding the range of the optimal cost of a transportation problem when supply and demand vary over an interval. We consider the specific version of a transportation problem with supply inequality constraints and demand equality constraints under the assumption that the transportation costs are immune against the transportation paradox. We investigate some theoretical properties of the problem which constitute the basis of a novel solution algorithm. Our results show that the proposed algorithm hugely outperforms the best existing solution approaches
Locating sensors to observe network arc flows: Exact and heuristic approaches
No full textThe problem of optimally locating sensors on a traffic network to monitor flows has been an object of growing interest in the past few years, due to its relevance in the field of traffic management and control. Sensors are often located in a network in order to observe and record traffic flows on arcs and/or nodes. Given traffic levels on arcs within the range or covered by the sensors, traffic levels on unobserved portions of a network can then be computed. In this paper, the problem of identifying a sensor configuration of minimal size that would permit traffic on any unobserved arcs to be exactly inferred is discussed. The problem being addressed, which is referred to in the literature as the Sensor Location Problem (SLP), is known to be NP-complete, and the existing studies about the problem analyze some polynomial cases and present local search heuristics to solve it. In this paper we further extend the study of the problem by providing a mathematical formulation that up to now has been still missing in the literature and present an exact branch and bound approach, based on a binary branching rule, that embeds the existing heuristics to obtain bounds on the solution value. Moreover, we apply a genetic approach to find good quality solutions. Extended computational results show the effectiveness of the proposed approaches in solving medium-large instances
Mathematical programming formulations for the Collapsed k-Core Problem
No full textIn social network analysis, the size of the k-core, i.e., the maximal induced subgraph of the network with minimum degree at least k, is frequently adopted as a typical metric to evaluate the cohesiveness of a community. We address the Collapsed k-Core Problem, which seeks to find a subset of b users, namely the most critical users of the network, the removal of which results in the smallest possible k-core. For the first time, both the problem of finding the k-core of a network and the Collapsed k-Core Problem are formulated using mathematical programming. On the one hand, we model the Collapsed k-Core Problem as a natural deletion-round-indexed Integer Linear formulation. On the other hand, we provide two bilevel programs for the problem, which differ in the way in which the k-core identification problem is formulated at the lower level. The first bilevel formulation is reformulated as a single-level sparse model, exploiting a Benders-like decomposition approach. To derive the second bilevel model, we provide a linear formulation for finding the k-core and use it to state the lower-level problem. We then dualize the lower level and obtain a compact Mixed-Integer Nonlinear single-level problem reformulation. We additionally derive a combinatorial lower bound on the value of the optimal solution and describe some pre-processing procedures, and valid inequalities for the three formulations. The performance of the proposed formulations is compared on a set of benchmarking instances with the existing state-of-the-art solver for mixed-integer bilevel problems proposed in (Fischetti, Ljubić, Monaci, and Sinnl, 2017)
- …
