snowberryfield / printemps Goto Github PK

View Code? Open in Web Editor NEW

42.0 2.0 2.0 3.91 MB

C++ metaheuristics modeler/solver for general integer optimization problems.

Home Page: https://snowberryfield.github.io/printemps/

License: MIT License

CMake 0.45% C++ 97.32% C 0.28% Dockerfile 0.01% Python 1.55% JetBrains MPS 0.39%

metaheuristics tabu-search combinatorial-optimization integer-programming optimization

printemps's People

Contributors

Stargazers

Watchers

Forkers

sk-surya datatalkv

printemps's Issues

v1.1 fails in presolving a singleton constraint with a negative coefficient.

v1.1 fails in presolving a singleton constraint with a negative coefficient.
The following error message was generated in solving neos-4360552-sangro.mps.

________________________________________________________________________________
INFO    : The values for each option are specified as follows:
 - iteration_max: 20000
 - time_offset: 0.000000
 - time_max: 14400.000000
 - penalty_coefficient_relaxing_ratio: 0.900000
 - penalty_coefficient_tightening_ratio: 1.000000
 - initial_penalty_coefficient: 100000000000.000000
 - is_enabled_local_search: 1
 - is_enabled_grouping_penalty_coefficient: 0
 - is_enabled_initial_value_correction: 1
 - is_enabled_parallel_evaluation: 1
 - is_enabled_parallel_neighborhood_update: 1
 - selection_mode: 1
 - target_objective_value: -1.000e+100
 - verbose: 4
 - local_search.iteration_max: 10000
 - local_search.time_max: 120.000000
 - local_search.time_offset: 0.000000
 - local_search.log_interval: 10
 - local_search.seed: 1
 - tabu_search.iteration_max: 1000
 - tabu_search.time_max: 20000.000000
 - tabu_search.time_offset: 0.000000
 - tabu_search.log_interval: 10
 - tabu_search.initial_tabu_tenure: 10
 - tabu_search.tabu_mode: 1
 - tabu_search.move_preserve_rate: 1.000000
 - tabu_search.frequency_penalty_coefficient: 0.000010
 - tabu_search.is_enabled_improvability_screening: 1
 - tabu_search.is_enabled_shuffle: 1
 - tabu_search.is_enabled_move_curtail: 0
 - tabu_search.is_enabled_automatic_break: 1
 - tabu_search.is_enabled_automatic_tabu_tenure_adjustment:1
 - tabu_search.ignore_tabu_if_augmented_incumbent: 0
 - tabu_search.ignore_tabu_if_feasible_incumbent: 1
 - tabu_search.number_of_initial_modification: 0
 - tabu_search.seed: 1
________________________________________________________________________________
MESSAGE : Verifying the problem...
MESSAGE : Done.
________________________________________________________________________________
MESSAGE : Presolving...
MESSAGE : The singleton constraint stfix_1_1 is removed instead of fixing the va
          lue of the decision variable s(1,1) by -0.000000.
MESSAGE : The singleton constraint stfix_2_1 is removed instead of fixing the va
          lue of the decision variable s(2,1) by -0.000000.
MESSAGE : The singleton constraint stfix_3_1 is removed instead of fixing the va
          lue of the decision variable s(3,1) by -0.000000.
MESSAGE : The singleton constraint stfix_4_1 is removed instead of fixing the va
          lue of the decision variable s(4,1) by -0.000000.
MESSAGE : The singleton constraint stfix_5_1 is removed instead of fixing the va
          lue of the decision variable s(5,1) by -0.000000.
MESSAGE : The singleton constraint stfix_6_1 is removed instead of fixing the va
          lue of the decision variable s(6,1) by -0.000000.
MESSAGE : The singleton constraint edfix_1_48 is removed instead of fixing the v
          alue of the decision variable e(1,48) by 12.000000.
MESSAGE : The singleton constraint edfix_2_48 is removed instead of fixing the v
          alue of the decision variable e(2,48) by 12.000000.
MESSAGE : The singleton constraint edfix_3_48 is removed instead of fixing the v
          alue of the decision variable e(3,48) by 12.000000.
MESSAGE : The singleton constraint edfix_4_48 is removed instead of fixing the v
          alue of the decision variable e(4,48) by 12.000000.
MESSAGE : The singleton constraint edfix_5_48 is removed instead of fixing the v
          alue of the decision variable e(5,48) by 12.000000.
MESSAGE : The singleton constraint edfix_6_48 is removed instead of fixing the v
          alue of the decision variable e(6,48) by 12.000000.
MESSAGE : The singleton constraint jx_s_1_1_1 is removed because it is redundant
          .
MESSAGE : The singleton constraint jx_s_1_2_1 is removed because it is redundant
          .
MESSAGE : The singleton constraint jx_s_1_3_1 is removed because it is redundant
          .
MESSAGE : The singleton constraint jx_s_1_4_1 is removed because it is redundant
          .
MESSAGE : The singleton constraint jx_s_1_5_1 is removed because it is redundant
          .
MESSAGE : The singleton constraint jx_s_1_6_1 is removed because it is redundant
          .
MESSAGE : The singleton constraint jx_s_1_7_1 is removed because it is redundant
          .
MESSAGE : The singleton constraint jx_s_1_8_1 is removed because it is redundant
          .
MESSAGE : The singleton constraint jx_s_1_9_1 is removed because it is redundant
          .
MESSAGE : The singleton constraint jx_s_1_10_1 is removed because it is redundan
          t.
MESSAGE : The singleton constraint jx_s_1_11_1 is removed because it is redundan
          t.
MESSAGE : The singleton constraint jx_s_1_12_1 is removed because it is redundan
          t.
MESSAGE : The singleton constraint jx_s_2_1_1 is removed because it is redundant
          .
MESSAGE : The singleton constraint jx_s_2_2_1 is removed because it is redundant
          .
MESSAGE : The singleton constraint jx_s_2_3_1 is removed because it is redundant
          .
MESSAGE : The singleton constraint jx_s_2_4_1 is removed because it is redundant
          .
MESSAGE : The singleton constraint jx_s_2_5_1 is removed because it is redundant
          .
MESSAGE : The singleton constraint jx_s_2_6_1 is removed because it is redundant
          .
MESSAGE : The singleton constraint jx_s_2_7_1 is removed because it is redundant
          .
MESSAGE : The singleton constraint jx_s_2_8_1 is removed because it is redundant
          .
MESSAGE : The singleton constraint jx_s_2_9_1 is removed because it is redundant
          .
MESSAGE : The singleton constraint jx_s_2_10_1 is removed because it is redundan
          t.
MESSAGE : The singleton constraint jx_s_2_11_1 is removed because it is redundan
          t.
MESSAGE : The singleton constraint jx_s_2_12_1 is removed because it is redundan
          t.
MESSAGE : The singleton constraint jx_s_3_1_1 is removed because it is redundant
          .
MESSAGE : The singleton constraint jx_s_3_2_1 is removed because it is redundant
          .
MESSAGE : The singleton constraint jx_s_3_3_1 is removed because it is redundant
          .
MESSAGE : The singleton constraint jx_s_3_4_1 is removed because it is redundant
          .
MESSAGE : The singleton constraint jx_s_3_5_1 is removed because it is redundant
          .
MESSAGE : The singleton constraint jx_s_3_6_1 is removed because it is redundant
          .
MESSAGE : The singleton constraint jx_s_3_7_1 is removed because it is redundant
          .
MESSAGE : The singleton constraint jx_s_3_8_1 is removed because it is redundant
          .
MESSAGE : The singleton constraint jx_s_3_9_1 is removed because it is redundant
          .
MESSAGE : The singleton constraint jx_s_3_10_1 is removed because it is redundan
          t.
MESSAGE : The singleton constraint jx_s_3_11_1 is removed because it is redundan
          t.
MESSAGE : The singleton constraint jx_s_3_12_1 is removed because it is redundan
          t.
MESSAGE : The singleton constraint jx_s_4_1_1 is removed because it is redundant
          .
MESSAGE : The singleton constraint jx_s_4_2_1 is removed because it is redundant
          .
MESSAGE : The singleton constraint jx_s_4_3_1 is removed because it is redundant
          .
MESSAGE : The singleton constraint jx_s_4_4_1 is removed because it is redundant
          .
MESSAGE : The singleton constraint jx_s_4_5_1 is removed because it is redundant
          .
MESSAGE : The singleton constraint jx_s_4_6_1 is removed because it is redundant
          .
MESSAGE : The singleton constraint jx_s_4_7_1 is removed because it is redundant
          .
MESSAGE : The singleton constraint jx_s_4_8_1 is removed because it is redundant
          .
MESSAGE : The singleton constraint jx_s_4_9_1 is removed because it is redundant
          .
MESSAGE : The singleton constraint jx_s_4_10_1 is removed because it is redundan
          t.
MESSAGE : The singleton constraint jx_s_4_11_1 is removed because it is redundan
          t.
MESSAGE : The singleton constraint jx_s_4_12_1 is removed because it is redundan
          t.
MESSAGE : The singleton constraint jx_s_5_1_1 is removed because it is redundant
          .
MESSAGE : The singleton constraint jx_s_5_2_1 is removed because it is redundant
          .
MESSAGE : The singleton constraint jx_s_5_3_1 is removed because it is redundant
          .
MESSAGE : The singleton constraint jx_s_5_4_1 is removed because it is redundant
          .
MESSAGE : The singleton constraint jx_s_5_5_1 is removed because it is redundant
          .
MESSAGE : The singleton constraint jx_s_5_6_1 is removed because it is redundant
          .
MESSAGE : The singleton constraint jx_s_5_7_1 is removed because it is redundant
          .
MESSAGE : The singleton constraint jx_s_5_8_1 is removed because it is redundant
          .
MESSAGE : The singleton constraint jx_s_5_9_1 is removed because it is redundant
          .
MESSAGE : The singleton constraint jx_s_5_10_1 is removed because it is redundan
          t.
MESSAGE : The singleton constraint jx_s_5_11_1 is removed because it is redundan
          t.
MESSAGE : The singleton constraint jx_s_5_12_1 is removed because it is redundan
          t.
MESSAGE : The singleton constraint jx_s_6_1_1 is removed because it is redundant
          .
MESSAGE : The singleton constraint jx_s_6_2_1 is removed because it is redundant
          .
MESSAGE : The singleton constraint jx_s_6_3_1 is removed because it is redundant
          .
MESSAGE : The singleton constraint jx_s_6_4_1 is removed because it is redundant
          .
MESSAGE : The singleton constraint jx_s_6_5_1 is removed because it is redundant
          .
MESSAGE : The singleton constraint jx_s_6_6_1 is removed because it is redundant
          .
MESSAGE : The singleton constraint jx_s_6_7_1 is removed because it is redundant
          .
MESSAGE : The singleton constraint jx_s_6_8_1 is removed because it is redundant
          .
MESSAGE : The singleton constraint jx_s_6_9_1 is removed because it is redundant
          .
MESSAGE : The singleton constraint jx_s_6_10_1 is removed because it is redundan
          t.
MESSAGE : The singleton constraint jx_s_6_11_1 is removed because it is redundan
          t.
MESSAGE : The singleton constraint jx_s_6_12_1 is removed because it is redundan
          t.
MESSAGE : The singleton constraint jx_e_1_1_48 is removed instead of tightening 
          the lower bound of the decision variable x(1,1,48) by 12.
terminate called after throwing an instance of 'std::logic_error'
  what():  /Users/laevateinn/Documents/Projects/cpp_metaheuristics/cppmh/model/variable.h, line 186, function set_bound: The specified lower bound is bigger than the specified upper bound. lower bound: 12, upper bound: 1
Abort trap: 6

Improvability screening sometime misses incumbent updating solution.

The improvability screening procedure in tabu search sometime misses incumbent updating solution due to the implementation error in checking the screening condition.

The following block in tabu_search.h (L.224-L.234)

            if (option.tabu_search.is_enabled_improvability_screening &&
                has_constraint) {
                if (trial_solution_scores[i_move].is_feasible &&
                    !trial_solution_scores[i_move].is_objective_improvable) {
                    total_scores[i_move] = HUGE_VALF;
                }
                if (!trial_solution_scores[i_move].is_feasible &&
                    !trial_solution_scores[i_move].is_constraint_improvable) {
                    total_scores[i_move] = HUGE_VALF;
                }
            }

should be corrected as:

            if (option.tabu_search.is_enabled_improvability_screening &&
                has_constraint) {
                if (solution_score.is_feasible &&
                    !trial_solution_scores[i_move].is_objective_improvable) {
                    total_scores[i_move] = HUGE_VALF;
                }
                if (!solution_score.is_feasible &&
                    !trial_solution_scores[i_move].is_constraint_improvable) {
                    total_scores[i_move] = HUGE_VALF;
                }
            }

Documentation

In the "Solver Option Guide", there are two sections labeled "Preprocess Options". The second such section should probably be relabeled to "Move Options".
https://snowberryfield.github.io/printemps/contents/solver_option_guide.html

Question about Parallelization

Why did you parallelize PRINTEMPS with OpenMP rather than C++ threads (https://cplusplus.com/reference/thread/thread/) or pthreads (https://www.tutorialspoint.com/cplusplus/cpp_multithreading.htm)?

Objective.evaluate() fails if the objective function is not defined.

The Objective.evaluate() method fails if the objective function is not defined because the FixedSizedHashMap object would not be built for that case. The step m_expression.setup_fixed_sensitivities(); in the following code in objective.h should be moved into Model.setup_fixed_sensitivities() method.

    /*************************************************************************/
    inline constexpr void setup(
        const Expression<T_Variable, T_Expression> &a_EXPRESSION) {
        this->initialize();
        m_is_linear  = true;
        m_expression = a_EXPRESSION;
        m_expression.setup_fixed_sensitivities();
    }

Questions about PDLP and the Lagrange dual method

Does the Lagrange dual method work for nonlinear integer programming problems?

Is there a difference between PRINTEMPS PDLP and OR-Tools PDLP?

Does PRINTEMPS PDLP compute a corrected dual objective, as does OR-Tools PDLP? The
corrected dual objective is a feasible lower bound. https://developers.google.com/optimization/lp/pdlp_math#dual

The new PDLP options do not appear in the Solver Option Guide. https://snowberryfield.github.io/printemps/contents/solver_option_guide.html

Is PDLP used as an alternative method to the Lagrange dual search to find a lower bound?

Switch the neighborhood structure according to search status

The swap neighborhood for selection constraints which are automatically detected seems to interfere to find a feasible solution in the early stage of the optimization.
A strategy to switch neighborhood according to search status is preferred.
A concrete idea is to enable the swap neighborhood if and only if the current solution is feasible.

Improve the computational efficiency of Model.evaluate()

The method Model.evaluate() is the most time-consuming method in the optimization.
The method checks the sensitivities of all combinations between variables to be moved and all constraints.
However, such check can be skipped by let a move have the information about constraints that it contributes.

time_max units

What are the units (minutes, hours, days, etc...) of the various time_max options?
https://snowberryfield.github.io/printemps/contents/solver_option_guide.html

Questions about Presolve

Do you know how PRINTEMPS presolve differs from PaPILO presolve and OR-Tools GLOP presolve?

PaPILO:
https://github.com/scipopt/papilo
https://arxiv.org/abs/2206.10709

GLOP Presolve for OR-Tools PDLP:
https://github.com/google/or-tools/blob/5425dedcfbb22cb74c636c1374a9b5ad684b1eb5/ortools/pdlp/solvers.proto#L348

If PRINTEMPS uses presolve, does it need to transform the primal and dual solutions and the upper and lower bounds from the presolved space back to the original space?

Does PRINTEMPS presolve only work for integer linear programming problems?

Recommend Projects

React

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

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

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

An Open Source Machine Learning Framework for Everyone
Django

The Web framework for perfectionists with deadlines.
Laravel

A PHP framework for web artisans
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.
Visualization

Some thing interesting about visualization, use data art
Game

Some thing interesting about game, make everyone happy.

Recommend Org

Facebook

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

Open source projects and samples from Microsoft.
Google

Google ❤️ Open Source for everyone.
Alibaba

Alibaba Open Source for everyone
D3

Data-Driven Documents codes.
Tencent

China tencent open source team.