skip to main content


Title: Two lower-bounding algorithms for the p-center problem in an area
Abstract

The p-center location problem in an area is an important yet very difficult problem in location science. The objective is to determine the location of p hubs within a service area so that the distance from any point in the area to its nearest hub is as small as possible. While effective heuristic methods exist for finding good feasible solutions, research work that probes the lower bound of the problem’s objective value is still limited. This paper presents an iterative solution framework along with two optimization-based heuristics for computing and improving the lower bound, which is at the core of the problem’s difficulty. One method obtains the lower bound via solving the discrete version of the Euclidean p-center problem, and the other via solving a relatively easier clustering problem. Both methods have been validated in various test cases, and their performances can serve as a benchmark for future methodological improvements.

 
more » « less
Award ID(s):
1944068
NSF-PAR ID:
10362106
Author(s) / Creator(s):
Publisher / Repository:
Springer Science + Business Media
Date Published:
Journal Name:
Computational Urban Science
Volume:
2
Issue:
1
ISSN:
2730-6852
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. null (Ed.)
    In this paper, we study Joint Source-Channel Coding (JSCC) for distributed analog functional compression over both Gaussian Multiple Access Channel (MAC) and AWGN channels. Notably, we propose a deep neural network based solution for learning encoders and decoders. We propose three methods of increasing performance. The first one frames the problem as an autoencoder; the second one incorporates the power constraint in the objective by using a Lagrange multiplier; the third method derives the objective from the information bottleneck principle. We show that all proposed methods are variational approximations to upper bounds on the indirect rate-distortion problem’s minimization objective. Further, we show that the third method is the variational approximation of a tighter upper bound compared to the other two. Finally, we show empirical performance results for image classification. We compare with existing work and showcase the performance improvement yielded by the proposed methods. 
    more » « less
  2. In a chance constrained program (CCP), decision makers seek the best decision whose probability of violating the uncertainty constraints is within the prespecified risk level. As a CCP is often nonconvex and is difficult to solve to optimality, much effort has been devoted to developing convex inner approximations for a CCP, among which the conditional value-at-risk (CVaR) has been known to be the best for more than a decade. This paper studies and generalizes the ALSO-X, originally proposed by Ahmed, Luedtke, SOng, and Xie in 2017 , for solving a CCP. We first show that the ALSO-X resembles a bilevel optimization, where the upper-level problem is to find the best objective function value and enforce the feasibility of a CCP for a given decision from the lower-level problem, and the lower-level problem is to minimize the expectation of constraint violations subject to the upper bound of the objective function value provided by the upper-level problem. This interpretation motivates us to prove that when uncertain constraints are convex in the decision variables, ALSO-X always outperforms the CVaR approximation. We further show (i) sufficient conditions under which ALSO-X can recover an optimal solution to a CCP; (ii) an equivalent bilinear programming formulation of a CCP, inspiring us to enhance ALSO-X with a convergent alternating minimization method (ALSO-X+); and (iii) an extension of ALSO-X and ALSO-X+ to distributionally robust chance constrained programs (DRCCPs) under the ∞−Wasserstein ambiguity set. Our numerical study demonstrates the effectiveness of the proposed methods. 
    more » « less
  3. Site description. This data package consists of data obtained from sampling surface soil (the 0-7.6 cm depth profile) in black mangrove (Avicennia germinans) dominated forest and black needlerush (Juncus roemerianus) saltmarsh along the Gulf of Mexico coastline in peninsular west-central Florida, USA. This location has a subtropical climate with mean daily temperatures ranging from 15.4 °C in January to 27.8 °C in August, and annual precipitation of 1336 mm. Precipitation falls as rain primarily between June and September. Tides are semi-diurnal, with 0.57 m median amplitudes during the year preceding sampling (U.S. NOAA National Ocean Service, Clearwater Beach, Florida, station 8726724). Sea-level rise is 4.0 ± 0.6 mm per year (1973-2020 trend, mean ± 95 % confidence interval, NOAA NOS Clearwater Beach station). The A. germinans mangrove zone is either adjacent to water or fringed on the seaward side by a narrow band of red mangrove (Rhizophora mangle). A near-monoculture of J. roemerianus is often adjacent to and immediately landward of the A. germinans zone. The transition from the mangrove to the J. roemerianus zone is variable in our study area. An abrupt edge between closed-canopy mangrove and J. roemerianus monoculture may extend for up to several hundred meters in some locations, while other stretches of ecotone present a gradual transition where smaller, widely spaced trees are interspersed into the herbaceous marsh. Juncus roemerianus then extends landward to a high marsh patchwork of succulent halophytes (including Salicornia bigellovi, Sesuvium sp., and Batis maritima), scattered dwarf mangrove, and salt pans, followed in turn by upland vegetation that includes Pinus sp. and Serenoa repens. Field design and sample collection. We established three study sites spaced at approximately 5 km intervals along the western coastline of the central Florida peninsula. The sites consisted of the Salt Springs (28.3298°, -82.7274°), Energy Marine Center (28.2903°, -82.7278°), and Green Key (28.2530°, -82.7496°) sites on the Gulf of Mexico coastline in Pasco County, Florida, USA. At each site, we established three plot pairs, each consisting of one saltmarsh plot and one mangrove plot. Plots were 50 m^2 in size. Plots pairs within a site were separated by 230-1070 m, and the mangrove and saltmarsh plots composing a pair were 70-170 m apart. All plot pairs consisted of directly adjacent patches of mangrove forest and J. roemerianus saltmarsh, with the mangrove forests exhibiting a closed canopy and a tree architecture (height 4-6 m, crown width 1.5-3 m). Mangrove plots were located at approximately the midpoint between the seaward edge (water-mangrove interface) and landward edge (mangrove-marsh interface) of the mangrove zone. Saltmarsh plots were located 20-25 m away from any mangrove trees and into the J. roemerianus zone (i.e., landward from the mangrove-marsh interface). Plot pairs were coarsely similar in geomorphic setting, as all were located on the Gulf of Mexico coastline, rather than within major sheltering formations like Tampa Bay, and all plot pairs fit the tide-dominated domain of the Woodroffe classification (Woodroffe, 2002, "Coasts: Form, Process and Evolution", Cambridge University Press), given their conspicuous semi-diurnal tides. There was nevertheless some geomorphic variation, as some plot pairs were directly open to the Gulf of Mexico while others sat behind keys and spits or along small tidal creeks. Our use of a plot-pair approach is intended to control for this geomorphic variation. Plot center elevations (cm above mean sea level, NAVD 88) were estimated by overlaying the plot locations determined with a global positioning system (Garmin GPS 60, Olathe, KS, USA) on a LiDAR-derived bare-earth digital elevation model (Dewberry, Inc., 2019). The digital elevation model had a vertical accuracy of ± 10 cm (95 % CI) and a horizontal accuracy of ± 116 cm (95 % CI). Soil samples were collected via coring at low tide in June 2011. From each plot, we collected a composite soil sample consisting of three discrete 5.1 cm diameter soil cores taken at equidistant points to 7.6 cm depth. Cores were taken by tapping a sleeve into the soil until its top was flush with the soil surface, sliding a hand under the core, and lifting it up. Cores were then capped and transferred on ice to our laboratory at the University of South Florida (Tampa, Florida, USA), where they were combined in plastic zipper bags, and homogenized by hand into plot-level composite samples on the day they were collected. A damp soil subsample was immediately taken from each composite sample to initiate 1 y incubations for determination of active C and N (see below). The remainder of each composite sample was then placed in a drying oven (60 °C) for 1 week with frequent mixing of the soil to prevent aggregation and liberate water. Organic wetland soils are sometimes dried at 70 °C, however high drying temperatures can volatilize non-water liquids and oxidize and decompose organic matter, so 50 °C is also a common drying temperature for organic soils (Gardner 1986, "Methods of Soil Analysis: Part 1", Soil Science Society of America); we accordingly chose 60 °C as a compromise between sufficient water removal and avoidance of non-water mass loss. Bulk density was determined as soil dry mass per core volume (adding back the dry mass equivalent of the damp subsample removed prior to drying). Dried subsamples were obtained for determination of soil organic matter (SOM), mineral texture composition, and extractable and total carbon (C) and nitrogen (N) within the following week. Sample analyses. A dried subsample was apportioned from each composite sample to determine SOM as mass loss on ignition at 550 °C for 4 h. After organic matter was removed from soil via ignition, mineral particle size composition was determined using a combination of wet sieving and density separation in 49 mM (3 %) sodium hexametaphosphate ((NaPO_3)_6) following procedures in Kettler et al. (2001, Soil Science Society of America Journal 65, 849-852). The percentage of dry soil mass composed of silt and clay particles (hereafter, fines) was calculated as the mass lost from dispersed mineral soil after sieving (0.053 mm mesh sieve). Fines could have been slightly underestimated if any clay particles were burned off during the preceding ignition of soil. An additional subsample was taken from each composite sample to determine extractable N and organic C concentrations via 0.5 M potassium sulfate (K_2SO_4) extractions. We combined soil and extractant (ratio of 1 g dry soil:5 mL extractant) in plastic bottles, reciprocally shook the slurry for 1 h at 120 rpm, and then gravity filtered it through Fisher G6 (1.6 μm pore size) glass fiber filters, followed by colorimetric detection of nitrite (NO_2^-) + nitrate (NO_3^-) and ammonium (NH_4^+) in the filtrate (Hood Nowotny et al., 2010,Soil Science Society of America Journal 74, 1018-1027) using a microplate spectrophotometer (Biotek Epoch, Winooski, VT, USA). Filtrate was also analyzed for dissolved organic C (referred to hereafter as extractable organic C) and total dissolved N via combustion and oxidation followed by detection of the evolved CO_2 and N oxide gases on a Formacs HT TOC/TN analyzer (Skalar, Breda, The Netherlands). Extractable organic N was then computed as total dissolved N in filtrate minus extractable mineral N (itself the sum of extractable NH_4-N and NO_2-N + NO_3-N). We determined soil total C and N from dried, milled subsamples subjected to elemental analysis (ECS 4010, Costech, Inc., Valencia, CA, USA) at the University of South Florida Stable Isotope Laboratory. Median concentration of inorganic C in unvegetated surface soil at our sites is 0.5 % of soil mass (Anderson, 2019, Univ. of South Florida M.S. thesis via methods in Wang et al., 2011, Environmental Monitoring and Assessment 174, 241-257). Inorganic C concentrations are likely even lower in our samples from under vegetation, where organic matter would dilute the contribution of inorganic C to soil mass. Nevertheless, the presence of a small inorganic C pool in our soils may be counted in the total C values we report. Extractable organic C is necessarily of organic C origin given the method (sparging with HCl) used in detection. Active C and N represent the fractions of organic C and N that are mineralizable by soil microorganisms under aerobic conditions in long-term soil incubations. To quantify active C and N, 60 g of field-moist soil were apportioned from each composite sample, placed in a filtration apparatus, and incubated in the dark at 25 °C and field capacity moisture for 365 d (as in Lewis et al., 2014, Ecosphere 5, art59). Moisture levels were maintained by frequently weighing incubated soil and wetting them up to target mass. Daily CO_2 flux was quantified on 29 occasions at 0.5-3 week intervals during the incubation period (with shorter intervals earlier in the incubation), and these per day flux rates were integrated over the 365 d period to compute an estimate of active C. Observations of per day flux were made by sealing samples overnight in airtight chambers fitted with septa and quantifying headspace CO_2 accumulation by injecting headspace samples (obtained through the septa via needle and syringe) into an infrared gas analyzer (PP Systems EGM 4, Amesbury, MA, USA). To estimate active N, each incubated sample was leached with a C and N free, 35 psu solution containing micronutrients (Nadelhoffer, 1990, Soil Science Society of America Journal 54, 411-415) on 19 occasions at increasing 1-6 week intervals during the 365 d incubation, and then extracted in 0.5 M K_2SO_4 at the end of the incubation in order to remove any residual mineral N. Active N was then quantified as the total mass of mineral N leached and extracted. Mineral N in leached and extracted solutions was detected as NH_4-N and NO_2-N + NO_3-N via colorimetry as above. This incubation technique precludes new C and N inputs and persistently leaches mineral N, forcing microorganisms to meet demand by mineralizing existing pools, and thereby directly assays the potential activity of soil organic C and N pools present at the time of soil sampling. Because this analysis commences with disrupting soil physical structure, it is biased toward higher estimates of active fractions. Calculations. Non-mobile C and N fractions were computed as total C and N concentrations minus the extractable and active fractions of each element. This data package reports surface-soil constituents (moisture, fines, SOM, and C and N pools and fractions) in both gravimetric units (mass constituent / mass soil) and areal units (mass constituent / soil surface area integrated through 7.6 cm soil depth, the depth of sampling). Areal concentrations were computed as X × D × 7.6, where X is the gravimetric concentration of a soil constituent, D is soil bulk density (g dry soil / cm^3), and 7.6 is the sampling depth in cm. 
    more » « less
  4. Abstract Background

    Perivascular spaces (PVSs) carry cerebrospinal fluid (CSF) around the brain, facilitating healthy waste clearance. Measuring those flows in vivo is difficult, and often impossible, because PVSs are small, so accurate modeling is essential for understanding brain clearance. The most important parameter for modeling flow in a PVS is its hydraulic resistance, defined as the ratio of pressure drop to volume flow rate, which depends on its size and shape. In particular, the local resistance per unit length varies along a PVS and depends on variations in the local cross section.

    Methods

    Using segmented, three-dimensional images of pial PVSs in mice, we performed fluid dynamical simulations to calculate the resistance per unit length. We applied extended lubrication theory to elucidate the difference between the calculated resistance and the expected resistance assuming a uniform flow. We tested four different approximation methods, and a novel correction factor to determine how to accurately estimate resistance per unit length with low computational cost. To assess the impact of assuming unidirectional flow, we also considered a circular duct whose cross-sectional area varied sinusoidally along its length.

    Results

    We found that modeling a PVS as a series of short ducts with uniform flow, and numerically solving for the flow in each, yields good resistance estimates at low cost. If the second derivative of area with respect to axial location is less than 2, error is typically less than 15%, and can be reduced further with our correction factor. To make estimates with even lower cost, we found that instead of solving for the resistance numerically, the well-known resistance of a circular duct could be scaled by a shape factor. As long as the aspect ratio of the cross section was less than 0.7, the additional error was less than 10%.

    Conclusions

    Neglecting off-axis velocity components underestimates the average resistance, but the error can be reduced with a simple correction factor. These results could increase the accuracy of future models of brain-wide and local CSF flow, enabling better prediction of clearance, for example, as it varies with age, brain state, and pathological conditions.

     
    more » « less
  5. An enormous reserve of information about the subglacial bedrock, tectonic and topographic evolution of Marie Byrd Land (MBL) exists within glaciomarine sediments of the Amundsen Sea shelf, slope and deep sea, and MBL marine shelf. Investigators of the NSF ICI-Hot and NSF Linchpin projects partnered with Arizona Laserchron Center to provide course-based undergraduate research experiences (CUREs) for from groups who do not ordinarily find access points to Antarctic science. Our courses enlist BIPOC and gender-expansive undergraduates in studies of ice-rafted debris (IRD) and bedrock samples, in order to impart skills, train in the use of research instrumentation, help students to develop confidence in their scientific abilities, and collaboratively address WAIS research questions at an early academic stage. CUREs afford benefits to graduate researchers and postdoctoral scientists, also, who join in as instructional faculty: CUREs allow GRs and PDs to engage in teaching that closely ties to their active research, yet provides practical experience to strengthen the academic portfolio (Cascella & Jez, 2018). Team members also develop art-science initiatives that engage students and community members who may not ordinarily engage with science, forging connections that make science relatable. Re-casting science topics through art centers personal connections and humanizes science, to promote understanding that goes beyond the purely analytical. Academic research shows that diverse undergraduates gain markedly from the convergence of art and science, and from involvement in collaborative research conducted within a CURE cohort, rather than as an individualized experience (e.g. Shanahan et al. 2022). The CUREs are offered as regular courses for credit, making access equitable via course enrollment. The course designation carries a legitimacy that is sought by students who balance academics with part-time employment. Course information is disseminated via STEM Bridge programs and/or an academic advising hub that reaches students from groups that are insufficiently represented within STEM and cryosphere science. CURE investigation of Amundsen Sea and WAIS problems is worthy objective because: 1) A variety of sample preparation, geochemical methods, and scientific best-practices can be imparted, while educating students about Antarctica’s geological configuration and role in the Earth climate system. 2) Individual projects that are narrowly defined can readily scaffold into collaborative science at the time of data synthesis and interpretation. 3) There is a high likelihood of scientific discovery that contributes to grant objectives. 4) Enrolled students will experience ambiguity and instrumentation setbacks alongside their faculty and instructors, and will likely have an opportunity to withstand/overcome challenges in a manner that trains students in complex problem solving and imparts resilience (St John et al., 2019). Based on our experiences, we consider CUREs as a means to create more inclusive and equitable spaces for learning to do research, and a basis for a broadening future WAIS community. Our groups have yet to assess student learning gains and STEM entry in a robust way, but we can report that two presenters at WAIS 2022 came from our 2021 CURE, and four polar science graduate researchers gained experience via CURE teaching. Data obtained by CURE students is contributing to our NSF projects’ aims to obtain isotope, age, and petrogenetic criteria with bearing on the subglacial bedrock geology, tectonic and landscape evolution, and ice sheet history of MBL. Cited and recommended works: Cascella & Jez, 2018, doi: 10.1021/acs.jchemed.7b00705 Gentile et al., 2017, doi: 10.17226/24622 Shanahan et al. 2022, https://www.cur.org/assets/1/23/01-01_TOC_SPUR_Winter21.pdf Shortlidge & Brownell, 2016, doi: 10.1128/jmbe.v17i3.1103 St. John et al. 2019, EOS, doi: 10.1029/2019EO127285. 
    more » « less