Skip to main content

LPFICS aims to enable to find ONE infeasible constraint set if a model is considered infeasible once resolved

Project description

LPFICS Lib to find incompatible constraints set in Linear Problems

LPFICS Idea

Objective: This project aims to enable to find ONE incompatible constraint set if a model is considered infeasible once resolved. Note that it MAY NOT be the ONLY ONE set of constraints making your problem infeasible.

This project is based on PuLP (https://github.com/coin-or/pulp) a LP modeler written in Python. PuLP integrates the solver CBC. This solution works with CBC, and GLPK solvers but does not work with Gurobi (as the output is always NotSolved and not Infeasible if the problem is overconstrainted).

Here is a simplified explaination: If a problem is overconstrainted, the problem will:

  • test to solve the problem with the first half of the constraints
    • if there is no solution it continues taking the first half (of the half) of the constraints
    • if there is a solution, it will test the other half
      • if the second half has no solution it will continue dividing the second half set of constraints to test it
      • if the second half has a solution it will rearrange the constraints and test again

References

The methodology (quickXplain) on which the program is based is described, discussed and modeled on the following references:

Junker, Ulrich. 2004. « QUICKXPLAIN: Preferred Explanations and Relaxations for Over-Constrained Problems », In: AAAI-04. San Jose. https://www.aaai .org/Papers/AAAI/2004/AAAI04-027.pdf

Morriet, Lou, Benoit Delinchant, Gilles Debizet, Frédéric Wurtz. 2020. « Algorithme d identification de contraintes incompatibles pour les problemes d optimisation : application à un projet energetique ». In: soumis à IBPSA 2020.

Rodler, Patrick. 2020. « Understanding the QuickXPlain Algorithm: Simple Explanation and Formal Proof ». ArXiv:2001.01835, janvier. http://arxiv .org/abs/2001.01835.

Verger, Guillaume, 2016. Ruby-Cbc [Logiciel]. Ruby. In : Github. Consulte le 15 novembre 2020, https://github.com/gverger/ruby-cbc.

Installation Help

Please install LPFICS Lib with pip using the command prompt and type:

pip install git+https://gricad-gitlab.univ-grenoble-alpes.fr/omegalpes/lpfics.git

Please ask omegalpes-users@groupes.renater.fr if you are struggling during your installation

Library Installation Requirements

PuLP > 1.6.10

Copyright

This project contains a derivative work based on https://github.com/gverger/ruby-cbc. Project ruby-cbc is released under the MIT license, Copyright 2016 Guillaume Verger. Modifications Copyright 2019 G2Elab / MAGE See the LICENSE file for copyright information.

Main Authors:

Guillaume VERGER

Lou MORRIET

Partners:

Univ. Grenoble Alpes, CNRS, Grenoble INP, G2Elab, CEA, Université Paris-Sud

Acknowledgments:

This work has been partially supported by the CDP Eco-SESA receiving fund from the French National Research Agency in the framework of the "Investissements d’avenir" program (ANR-15-IDEX-02), by the ADEME, the French Agency for Environment and Energy Management, with the RETHINE project and by the Region Auvergne Rhône Alpes with the project OREBE.

Project details


Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Source Distribution

LPFICS-0.0.1.tar.gz (7.0 kB view details)

Uploaded Source

Built Distributions

lpfics-0.0.1-py3-none-any.whl (11.5 kB view details)

Uploaded Python 3

LPFICS-0.0.1-py3-none-any.whl (11.5 kB view details)

Uploaded Python 3

File details

Details for the file LPFICS-0.0.1.tar.gz.

File metadata

  • Download URL: LPFICS-0.0.1.tar.gz
  • Upload date:
  • Size: 7.0 kB
  • Tags: Source
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/3.3.0 pkginfo/1.5.0.1 requests/2.25.1 setuptools/51.1.1 requests-toolbelt/0.9.1 tqdm/4.30.0 CPython/3.6.0

File hashes

Hashes for LPFICS-0.0.1.tar.gz
Algorithm Hash digest
SHA256 bbfaee428fd947a539986e2c312efc8bc2d790f93add04c74b1745da33400cfb
MD5 d3ddcbe6f642889b1b3f3d7ac9b29654
BLAKE2b-256 e8f76c9dbd36cd502518825358b6796bb00fd4aa76cf20820207d85a39109577

See more details on using hashes here.

File details

Details for the file lpfics-0.0.1-py3-none-any.whl.

File metadata

  • Download URL: lpfics-0.0.1-py3-none-any.whl
  • Upload date:
  • Size: 11.5 kB
  • Tags: Python 3
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/3.3.0 pkginfo/1.5.0.1 requests/2.25.1 setuptools/51.1.1 requests-toolbelt/0.9.1 tqdm/4.30.0 CPython/3.6.0

File hashes

Hashes for lpfics-0.0.1-py3-none-any.whl
Algorithm Hash digest
SHA256 88d233aca21054821da56c477043b062ff16fa2afe6a6818ce4a97272eb0baf1
MD5 82f35b4aec377f4345c913b0b9b94f47
BLAKE2b-256 23e4017cfffe213ab81bd15980ec09abae54acc0decec204854f1b5f83b4bfc6

See more details on using hashes here.

File details

Details for the file LPFICS-0.0.1-py3-none-any.whl.

File metadata

  • Download URL: LPFICS-0.0.1-py3-none-any.whl
  • Upload date:
  • Size: 11.5 kB
  • Tags: Python 3
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/3.3.0 pkginfo/1.5.0.1 requests/2.25.1 setuptools/51.1.1 requests-toolbelt/0.9.1 tqdm/4.30.0 CPython/3.6.0

File hashes

Hashes for LPFICS-0.0.1-py3-none-any.whl
Algorithm Hash digest
SHA256 01ae82b51bebe764171e2fd3e27e39ceb18b9e92add3b78e606fd4e18b7c52cb
MD5 6f20a0fb01958ab5e4d84f7391baedf7
BLAKE2b-256 ee865e26a56f445831313fbe0d8102d6e744494f9be97984886be30330df8b75

See more details on using hashes here.

Supported by

AWS AWS Cloud computing and Security Sponsor Datadog Datadog Monitoring Fastly Fastly CDN Google Google Download Analytics Microsoft Microsoft PSF Sponsor Pingdom Pingdom Monitoring Sentry Sentry Error logging StatusPage StatusPage Status page