Code Monkey home page Code Monkey logo

spopt's Introduction

spopt: Spatial Optimization

Regionalization, facility location, and transportation-oriented modeling

tag Continuous Integration codecov Documentation License Ruff status DOI Discord

Spopt is an open-source Python library for solving optimization problems with spatial data. Originating from the region module in PySAL (Python Spatial Analysis Library), it is under active development for the inclusion of newly proposed models and methods for regionalization, facility location, and transportation-oriented solutions.

Regionalization

import spopt, libpysal, geopandas, numpy
mexico = geopandas.read_file(libpysal.examples.get_path("mexicojoin.shp"))
mexico["count"] = 1
attrs = [f"PCGDP{year}" for year in range(1950, 2010, 10)]
w = libpysal.weights.Queen.from_dataframe(mexico)
mexico["count"], threshold_name, threshold, top_n = 1, "count", 4, 2
numpy.random.seed(123456)
model = spopt.region.MaxPHeuristic(mexico, w, attrs, threshold_name, threshold, top_n)
model.solve()
mexico["maxp_new"] = model.labels_
mexico.plot(column="maxp_new", categorical=True, figsize=(12,8), ec="w");

Locate

from spopt.locate import MCLP
from spopt.locate.util import simulated_geo_points
import numpy, geopandas, pulp, spaghetti

solver = pulp.PULP_CBC_CMD(msg=False, warmStart=True)
lattice = spaghetti.regular_lattice((0, 0, 10, 10), 9, exterior=True)
ntw = spaghetti.Network(in_data=lattice)
street = spaghetti.element_as_gdf(ntw, arcs=True)
street_buffered = geopandas.GeoDataFrame(
    geopandas.GeoSeries(street["geometry"].buffer(0.5).unary_union),
    crs=street.crs,
    columns=["geometry"],
)
client_points = simulated_geo_points(street_buffered, needed=100, seed=5)
ntw.snapobservations(client_points, "clients", attribute=True)
clients_snapped = spaghetti.element_as_gdf(
    ntw, pp_name="clients", snapped=True
)
facility_points = simulated_geo_points(street_buffered, needed=10, seed=6)
ntw.snapobservations(facility_points, "facilities", attribute=True)
facilities_snapped = spaghetti.element_as_gdf(
    ntw, pp_name="facilities", snapped=True
)
cost_matrix = ntw.allneighbordistances(
    sourcepattern=ntw.pointpatterns["clients"],
    destpattern=ntw.pointpatterns["facilities"],
)
numpy.random.seed(0)
ai = numpy.random.randint(1, 12, 100)
mclp_from_cost_matrix = MCLP.from_cost_matrix(cost_matrix, ai, 4, p_facilities=4)
mclp_from_cost_matrix = mclp_from_cost_matrix.solve(solver)

see notebook for plotting code

Examples

More examples can be found in the Tutorials section of the documentation.

All examples can be run interactively by launching this repository as a Binder.

Requirements

Installation

spopt is available on the Python Package Index. Therefore, you can either install directly with pip from the command line:

$ pip install -U spopt

or download the source distribution (.tar.gz) and decompress it to your selected destination. Open a command shell and navigate to the decompressed folder. Type:

$ pip install .

You may also install the latest stable spopt via conda-forge channel by running:

$ conda install --channel conda-forge spopt

Related packages

Contribute

PySAL-spopt is under active development and contributors are welcome.

If you have any suggestions, feature requests, or bug reports, please open new issues on GitHub. To submit patches, please review PySAL's documentation for developers, the PySAL development guidelines, the spopt contributing guidelines before opening a pull request. Once your changes get merged, you’ll automatically be added to the Contributors List.

Support

If you are having trouble, please create an issue, start a discussion, or talk to us in PySAL's Discord channel.

Code of Conduct

As a PySAL-federated project, spopt follows the Code of Conduct under the PySAL governance model.

License

The project is licensed under the BSD 3-Clause license.

Citation

If you use PySAL-spopt in a scientific publication, we would appreciate using the following citations:

@misc{spopt2021,
    author    = {Feng, Xin, and Gaboardi, James D. and Knaap, Elijah and
                Rey, Sergio J. and Wei, Ran},
    month     = {jan},
    year      = {2021},
    title     = {pysal/spopt},
    url       = {https://github.com/pysal/spopt},
    doi       = {10.5281/zenodo.4444156},
    keywords  = {python,regionalization,spatial-optimization,location-modeling}
}

@article{spopt2022,
    author    = {Feng, Xin and Barcelos, Germano and Gaboardi, James D. and
                Knaap, Elijah and Wei, Ran and Wolf, Levi J. and
                Zhao, Qunshan and Rey, Sergio J.},
    year      = {2022},
    title     = {spopt: a python package for solving spatial optimization problems in PySAL},
    journal   = {Journal of Open Source Software},
    publisher = {The Open Journal},
    volume    = {7},
    number    = {74},
    pages     = {3330},
    url       = {https://doi.org/10.21105/joss.03330},
    doi       = {10.21105/joss.03330},
}

Funding

This project is/was partially funded through:

National Science Foundation Award #1831615: RIDIR: Scalable Geospatial Analytics for Social Science Research

spopt's People

Contributors

dependabot[bot] avatar erinrolson avatar gegen07 avatar github-actions[bot] avatar jgaboardi avatar knaaptime avatar ljwolf avatar martinfleis avatar nickbearman avatar paddyroddy avatar pedrocamargo avatar pre-commit-ci[bot] avatar rongboxu avatar rwei5 avatar sjsrey avatar xf37 avatar

Stargazers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar

Watchers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar

spopt's Issues

migrate spenc code

I cant seem to find a public record, but I've discussed with @ljwolf that spopt would be a preferable home for spenc instead of a standalone package. This issue serves as a reminder to move that code over here (replaces #80)

differentiating spatial clusterers

raising for discussion: is it worth being explicit in the API about clustering algos that strictly regionalize (e.g. maxp, skater) vs those that blend geographic and attribute dissimilarities (e.g. spenc, spatial_ward, etc) to get a spatially-encouraged solution? Might we want to put them in separate submodules or something to make it more explicit to the user?

An issue about "module 'spopt' has no attribute 'version'"

When I ran sphinx-build -b html docsrc docs to build docs website, I got

Running Sphinx v3.1.2
Configuration error:
There is a programmable error in your configuration file:
Traceback (most recent call last):
File "/Users/anaconda3/lib/python3.8/site-packages/sphinx/config.py", line 319, in eval_configfile
execfile(filename, namespace)
File "/Users/anaconda3/lib/python3.8/site-packages/sphinx/util/pycompat.py", line 88, in execfile_
exec(code, _globals)
File "/Users/xinfeng/spopt_rst/docsrc/conf.py", line 60, in <module>
version = spopt.version
AttributeError: module 'spopt' has no attribute 'version'

However, the first line of the init.py under the folder spopt is:
__version__ = "0.1.0"

I have tried to type import spopt and spopt.__version__ in python, and get the right answer. NOT sure why conf.py cannot obtain the version info via import spopt.

replace deleted logos

The PySAL banner (pysal_banner.svg) was deleted from the repo in #86, as well as the .ico image being swapped out for the old PySAL one. Right now we need to add that back. In the the future, it is important to perform code review as often and as thoroughly as possible to prevent this from happening, especially with PRs touching 172 files. I am always available for code review.

Issues caused by GitHub Actions: Deprecating set-env and add-path commands

There is an ongoing issue leading to the following errors.
Error: Unable to process command '::add-path::/usr/share/miniconda3/condabin' successfully.
Error: Unable to process command '::set-env name=CONDA::/usr/share/miniconda3' successfully.
Error: The add-path command is disabled.
Error: The set-env command is disabled.

Funding information in README.md

We should add the information for the current source to the Funding section. I put a template up of entries here that are commented out:

<!-- [<img align="middle" src="docs/_static/image/IMAGE1.png" width="150">](link1) Some text1: [Project title 1](another_link1) -->

Once we have the needed info. (and image, links, etc.), we can simply remove the comment markers (<!-- and -->). As an finished example, see spaghetti's Funding section.

spopt as solver agnostic?

The current implementation of BaseSpOptExactSolver sets the solver to the ortools wrapper for CBC: pywraplp.Solver. In order to make spopt child model classes solver agnostic should we remove the declaration of self.spOptSolver here and have self.solve as an @abstractmethod like in BaseSpOptHeuristicSolver?

Related: #18

rename master branch to main branch

1. Renaming the organization remote master branch.

  1. Create a renamed copy of the master branch.
  •  $ git branch -m master main
    
  1. Push the renamed copy to the organization remote.
  •  $ git push -u upstream main
    
  1. Update the default branch in Settings/Branches.
  2. Delete the organization remote master.
  •  $ git push upstream --delete master
    

2. Renaming your remote master branch.

  1. Create a renamed copy of the master branch.
  •  $ git branch -m master main
    
  1. Push the renamed copy to your remote.
  •  $ git push -u origin main
    
  1. Update the default branch in Settings/Branches.
  2. Delete your remote master.
  •  $ git push origin --delete master
    

Throws an error when silhoutte coefficients for two clusters are the same

https://github.com/pysal/pysal/blob/8612af9f83cef755baa9e040222a7c200073690a/pysal/cg/rtree.py#L461

We are doing a max of a tuple with first element as a float (silhoutte coefft) and second element as a _NodeCursor. Generally, this works fine if the first element is different. However, there are corner cases when silhoutte for two clusters are exactly the same. At this point the second element of the tuple (_NodeCursor) is compared. And, ofcourse, comparison operators (>,<) are not valid for the class _NodeCursor. Hence it throws an error:

...
File "/Library/Frameworks/Python.framework/Versions/3.6/lib/python3.6/site-packages/pysal/cg/rtree.py", line 200, in insert
    self.cursor.insert(o, orect)
  File "/Library/Frameworks/Python.framework/Versions/3.6/lib/python3.6/site-packages/pysal/cg/rtree.py", line 417, in insert
    self._balance()
  File "/Library/Frameworks/Python.framework/Versions/3.6/lib/python3.6/site-packages/pysal/cg/rtree.py", line 462, in _balance
    [(silhouette_coeff(c, memo), c) for c in clusterings])
TypeError: '>' not supported between instances of '_NodeCursor' and '_NodeCursor'

Fix:
Take the argmax of silhoutte score, and choose one cluster based on the index:
Line number: 462: /Library/Frameworks/Python.framework/Versions/3.6/lib/python3.6/site-packages/pysal/cg/rtree.py

Replace below original code:

score, bestcluster = max(
  [(silhouette_coeff(c, memo), c) for c in clusterings])

by the below code

import numpy as np
#print([(silhouette_coeff(c, memo), c) for c in clusterings])
sil_scores = [silhouette_coeff(c, memo) for c in clusterings]
best_sil_index = np.argmax(sil_scores)
bestcluster = clusterings[best_sil_index]
score = sil_scores[best_sil_index]

Clean up / enhance ReadMe

  • Add sections like other PySAL submodules
    • pysal logo
    • quick blurb
    • Examples
    • Installation
    • Requirements
    • Contribute
    • Support
    • CoC
    • License
  • Update subtitle -- Regionalization, facility location, and transport-oriented modeling
  • Redo MaxP notebook screenshot
    • python code chunk in markdown
    • high-res retina image of regions
  • Rename Location Allocation subsection to Facility Location
  • Create new subsection: Transportation and Routing

extra reqs for binder environment + binder badge

  • descartes is currently needed for to run the binders
    • we can't plot polygons without it
    • this will not be needed from geopandas v0.9.0 (I think), but must be there for now
  • we should have a binder badge in the Examples section of README.md

test all binders prior to closing

structural/naming alterations?

Following up with #2, maybe we should reconsider the structure of spopt. The current structure (of non-base classes, etc) is:

  • allocate
  • region
  • route

I propose we change allocate to facility_location (or facloc for shorthand). I intend to add in covering models (LSCP, MCLP, etc.) and those don't generally fall under "location allocation". Also, I would like to add in a Transportation Problem class, so maybe changing route to transport, which would house transportation-oriented models, is a good idea. So the new structure would be:

  • facloc
  • region
  • transport

Installing for Google Collab

Hi! I'm using google's Colab but struggling to install spopt, specifically looking to use MaxPHeuristic.

Any ideas why I'm unable to install spopt in Colab?

Add coverage report?

Creating issue for this comment

we are generating a cov report, but not actually checking/comparing/reporting anything from it. If we would like to set up codecov, I can do that easily, I will just need admin access to spopt.

See example in spaghetti

@sjsrey

various tasks for package admin/cleanup

  • rename LICENSE -> LICENSE.txt 61353f8
  • add a MANIFEST.in file 267753c
  • update supported Python versions (+3.9, -3.6)
    • setup.py (also python_requires=">=3.7") 21f963e
    • installation.rst 75a77b1
  • update binder link creation in conf.py and DRY in general 89631cd
  • remove pin spaces in .ci/*.yml files c958bf4
  • reduce min builds before reporting in codecov.yml 3f6264f
  • adjust environment.yml f788d0b
    • bump Python version to 3.9, -3.8
    • replace coveralls with codecov
  • requirements*.txt files
    • alphabetize 89a1234
    • create requirements_tests.txt with pytest, pytest-cov, & codecov a10dbfc
    • create requirements_dev.txt with black & pre-commit c2da3e4
  • update setup.py 21f963e

Release Polishing

Deadline December 11

  • Documentation
    • docsrc/ and docs/ directories
    • mimic docsrc/ dir of other PySAL submodules
      • conf.py
      • Makefile
      • _static/
      • index.rst/installation.rst/api.rst/tutorials.rst/references.rst
  • Testing
    • locate
    • region
    • transport

Improve testing suite

The failure due to the coverage decrease can be ignored... for now. However, we are desperately in need of a more complete/robust testing suite. At the moment only half our code base is being tested, which paves the way for undetected bugs.

See here for my original comment.

clean up region_k_means.py

region_k_means.py includes several imports that are not used (lines 2,3):

from libpysal.weights.util import get_points_array_from_shapefile
from libpysal.io.fileio import FileIO as psopen

Also, defining neighboring within is_neighbor() (line 66) does not appear to be necessary:

def is_neighbor(area, region, w):
    """Check if area is a neighbor of any member of region"""
    neighboring = False
    for member in region:
        if area in w[member]:
            return True
    return False

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.