or-opt-playground

A silly optimization problems playground where silly things are happening

https://github.com/cyyynthia/or-opt-playground

Science Score: 57.0%

This score indicates how likely this project is to be science-related based on various indicators:

✓
CITATION.cff file
Found CITATION.cff file
✓
codemeta.json file
Found codemeta.json file
✓
.zenodo.json file
Found .zenodo.json file
✓
DOI references
Found 4 DOI reference(s) in README
○
Academic publication links
○
Academic email domains
○
Institutional organization owner
○
JOSS paper metadata
○
Scientific vocabulary similarity
Low similarity (9.8%) to scientific vocabulary

Last synced: 10 months ago · JSON representation ·

Repository

A silly optimization problems playground where silly things are happening

Basic Info

Host: GitHub
Owner: cyyynthia
License: bsd-3-clause
Language: Python
Default Branch: mistress
Homepage:
Size: 57.6 KB

Statistics

Stars: 1
Watchers: 1
Forks: 0
Open Issues: 0
Releases: 0

Created over 2 years ago · Last pushed over 2 years ago

Metadata Files

Readme License Citation

Cynthia's OR optimization playground

My personal playground where I experiment with optimization problems, mostly linear programs.

Got inspired* from flop!EDT as they've been struggling to have a way to compute IIS of their linear programs, so I started toying with PuLP after reading some published paper on the matter.

*by inspired, the author means Pablo Seban from flop!EDT proposed a research question about this as part of a course at the Toulouse III - Paul Sabatier University, which lead to curiosity taking over and... this. hehe.

The code quality is not very good, and is certainly not production grade. They're mostly proof of concepts, and full of misc problems that would need to be addressed in a real solution.

I left a ton of comments in the code along my way, with references, notes, and more. They contain a lot of useful information about why I did things this way and link to resources which helped me, which of course contains a lot of further readings.

Things I've done

pulp/compute_iis.py: Computes an IIS of constraints of an infeasible problem, using PuLP. Uses a combination of elastic filtering, deletion filtering, and sensitivity filtering. Not the most efficient solution, but an efficient implementation must come from something lower level than something like PuLP anyway. This is mostly intended to be a PoC of an implementation.
- John W. Chinneck, Erik W. Dravnieks, (1991) Locating Minimal Infeasible Constraint Sets in Linear Programs. ORSA Journal on Computing 3(2):157-168.
- John W. Chinneck, (1997) Finding a Useful Subset of Constraints for Analysis in an Infeasible Linear Program. INFORMS Journal on Computing 9(2):164-174.
pulp/minimumconstraintsto_remove.py: Computes a possible minimal combinaison of constraints to remove in order to make a problem feasible. Crude implementation without many experiments beyond the original PoC.
- Formulas used from this post on Operations Research StackExchange: https://or.stackexchange.com/a/7309

Useful resources

Collection of instances from MIPLIB: https://git.zib.de/miplib2017/revised-submissions-final
Collection of infeasible instances (netlib): https://github.com/coin-or-tools/Data-Infeas

License

Software licensed under the BSD-3-Clause license, please see LICENSE for more details. Each file includes copyright information and the relevant credits.

F@#k Python, nya~ 🩷

Owner

Name: Cynthia
Login: cyyynthia
Kind: user
Location: Toulouse, France
Company: @Borkenware

Website: https://cynthia.dev
Twitter: cyyynthia_
Repositories: 102
Profile: https://github.com/cyyynthia

23f. French Computer Science student at the University of Toulouse. I have a crippling cookie and coffee addiction.

Citation (CITATION.cff)

cff-version: 1.2.0
type: software
repository-code: https://github.com/cyyynthia/or-opt-playground
license: MPL-2.0
title: Experiments with optimizations problems in operational research
message: >-
  If you use this software, please cite it using the
  metadata from this file.
authors:
  - given-names: Cynthia
    family-names: Rey
    email: cynthia@cynthia.dev
references:
  - type: generic
    title: Locating Minimal Infeasible Constraint Sets in Linear Programs
    doi: 10.1287/ijoc.3.2.157
    url: https://doi.org/10.1287/ijoc.3.2.157
    journal: ORSA Journal on Computing
    volume: 3
    number: 2
    start: 157
    end: 168
    year: 1991
    authors:
      - given-names: John W.
        family-names: Chinneck
      - given-names: Erik W.
        family-names: Dravnieks
  - type: generic
    title: Finding a Useful Subset of Constraints for Analysis in an Infeasible Linear Program
    doi: 10.1287/ijoc.9.2.164
    url: https://doi.org/10.1287/ijoc.9.2.164
    journal: INFORMS Journal on Computing
    volume: 9
    number: 2
    start: 164
    end: 174
    year: 1997
    authors:
      - given-names: John W.
        family-names: Chinneck

GitHub Events

Total

Last Year

Issues and Pull Requests

Last synced: about 1 year ago

All Time

Total issues: 0
Total pull requests: 0
Average time to close issues: N/A
Average time to close pull requests: N/A
Total issue authors: 0
Total pull request authors: 0
Average comments per issue: 0
Average comments per pull request: 0
Merged pull requests: 0
Bot issues: 0
Bot pull requests: 0

Past Year

Issues: 0
Pull requests: 0
Average time to close issues: N/A
Average time to close pull requests: N/A
Issue authors: 0
Pull request authors: 0
Average comments per issue: 0
Average comments per pull request: 0
Merged pull requests: 0
Bot issues: 0
Bot pull requests: 0

ecosyste.ms

Data

Tools

Indexes

Applications

Experiments

Open Source Science