hlefebvr/idol

The Mathematical Optimization Framework

idol's Issues

Getting rid of BlockModel and AbstractModel

The idea is to deal only with Model-s and to get rid of the esoteric concepts of BlockModel, and thus,
of AbstractModel.

Reason for introducing BlockModel (back then): When introducing column generation, a method was needed to describe the decomposable structure of the problem. Since the branch-and-bound algorithm was written in terms of "models", the idea was to embed the structure within the Model. Doing so led to the creation of BlockModel which embedded the sub-problem's models and their generation patterns. The master problem was then implicitly what the B&B algorithm considered.

Issue:

• BlockModel directly implied the necessity of AbstractModel for polymorphism. This introduces complexity.
• Moreover, the polymorphism is not complete (e.g., iterating over variables is done only over the master's variables) and, for advanced applications, which is the aim of the library, a (manual) downcast is needed, which is bad style.
• Finally, when using column generation, this forced the B&B algorithm to save solutions of the relaxed model by requesting values for variables from the non-relaxed model (since the relaxation was only the master problem and "implicitly" the sub-problems).

Proposed solution: The idea would be to deal only with Model-s and to directly embed the structure of the problem inside the backend of the model. We would create two optimizers for doing column generation and dantzig-wolfe decomposition.

• ColumnGenerationOptimizer is an optimizer which is attached to a model. The model is the master problem. Then, sub-problems can be added to the optimizer. When optimized, the master problem is solved and missing columns are identified by solving the sub-problems. Since the optimizer is attached to the master problem, branching is done only on the master variables (allowing for branching on original master problem's variables as well as on dynamically generated variables (e.g., Ryan and Foster)). Sub-problems can potentially be dynamically added.
• DantzigWolfeDecompositionOptimizer inherits from ColumnGenerationOptimizer and is an optimizer which is attached to a model. This model is the original formulation of the problem. The problem is reformulated automatically and branching may be performed on sub-problems' variables, i.e., variables of the attached model.

Advantages:

• Simplifies the overall interface;
• Avoids downcasts;
• Avoids problems related to iteration over objects of model defined as BlockModel;
• Avoids mess with computing decomposition and "opposite axis annotation".

Allow to copy optimizer factories and start optimizer "arithmetic"

We should allow to copy optimizer factory. They are generally lightweight objects and this would allow for optimizer "arithmetic".

Heuristics::IntegerMaster and LazyCut

Describe the bug
If a problem is solved by branch-and-price and lazy cuts are added in the callback, the lazy cut are not generated in the callback and a potentially wrong solution is submitted.

Expected behavior
The callback should you the same optimizer as the original problem but disabling column generation with master problem being integer.

Implement reliability branching

Implement branching with priorities

It would be nice to have branching with priorities implemented.

Skeleton:

BranchAndBound()
    .with_branching_rule(
        BranchingWithPriority()
            .add_branching_rule(MostInfeasible::Strategy<NodeVarInfo>(x.begin(), x.end()))
            .add_branching_rule(MostInfeasible::Strategy<NodeVarInfo>(y.begin(), y.end()))
    )

Implement Rounding heuristic

Implement diving heuristics

Divers have draft in dev branch already.

Implement (Objective) Feasibility Pump

Refactor ColumnGeneration

Current issues

• The current implementation of ColumnGeneration is not 100% clean and there is a confusion with the phases when dealing with infeasible master problem with artificial variables.
• Only one stabilization rule is used which is based on the last iterate.

Do not always solve child nodes to optimality

Is your feature request related to a problem? Please describe.
Currently, all nodes are solved to optimality when they are created. Yet, this is not necessary for correctness. We only need to solve the node optimally if it is selected for branching.

Describe the solution you'd like
Nodes should be solved partially according to some criterion (?) and solved only when needed.

Describe alternatives you've considered
.

Additional context
.

Load columns from pool

Currently, columns are not loaded from the pool.

For each sub problem, check if columns agree with the bounds of parent and if they agree with the SP model constraints.

Automatically adapt smoothing factor in stabilization for CG

Implement "auto-adaptive" scheme from Automation and Combination of Linear-Programming Based Stabilization Techniques in Column Generation, A. Pessoa, R. Sadykov, E. Uchoa, and F. Vanderbeck, INFORMS Journal on Computing (2018), 30:2, 339-360.

Implement RINS

Improvement heuristics