coin-or / coin-or/pulp

More efficient resolve when change in objective function only

Open
#497 2 comments 0 reactions 0 assignees View on GitHub
enhancement
Dominant language
Python
Stars
2.5k
Forks
432
PR merge metrics
No merged PRs in 30d

Description

Describe the new feature
--------------------------
For decomposition problems where we need to solve the same optimisation problem iteratively with a slight change in the objective function each time, having writeLP in actualSolve makes this very computationally inefficient. For cplex we have the cplex_py version, but this still has a rather costly "buildSolverModel" each time we call "actualSolve", rewriting the model each time even if we are only changing the objective function.

I was wondering whether it would be possible to have an option that separates "buildSolverModel" from "actualSolve" so that we can change the objective function and resolve without rewriting the whole problem? I'd be quite happy starting off with cplex, and maybe going on to other solvers that currently only have the writeLP option?

Thanks in advance :)

Example problem:
I would like to use pulp as the modelling language for a decomposition problem, for example:
The optimisation problem is:

frontalproblem

x_i is a one dimensional vector of any size and X_i is the domain of x_i.

I dualise the equality constraint so that I can decompose the problem, so for each i I have the following smaller problem:

decomposedproblem

Where \lambda is the dual variable associated with the equality constraint in the frontal problem.

I update \lambda iteratively using gradient descent.

Additional info
---------------
Please answer these questions before submitting your feature request.

#### Is your feature request related to an issue? Please include the issue number.
Not as far as I can tell

#### Does this feature exist in another product or project? Please provide a link.
It exists in a modelling language used at my company that is in C++ and currently not open source.

Contributor guide

Open the contributing guide

Research direction

Start by reading the CPLEX implementation around actualSolve, writeLP, and buildSolverModel; no specific files or tests are named in the issue. Define the intended separation so an existing solver model can accept an updated objective and resolve without rebuilding the whole problem, then verify the behavior for the CPLEX path before considering other solvers.

Written by the indexing model from the issue text.

Assessment

Tech stack
python
Domain
backend-api-design
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
30/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.