Isitar commented 5 years ago

[ECOS BB] Implemented superior branching rules and new node selection method

Branching rules

In the current ecos version, the branching rule used is "most infeasible". It has been shown in several papers (for example Branching Rules revisited by T. Achterberg, T.Koch and A.Martin) that this rule is basicly as good as selecting a random node.

To check this statement I implemented the random branching strategy. My results are the same as in the paper: Most infeasible branching is only slightly better than random branching, both in solving problems in a time window and with an interation limit.

I implemented 3 new strategies: strong branching, pseudocost branching and reliability branching. All these methods are superior to most-infeasible in some ways.

Strong branching Strong branching the best method to get most out of your iterations. But in regards of time it is very slow and requires a lot of computations since it calculates all costs for up and down branching on every int/bool node.
Pseudocost branching Pseudocost branching relies on previos decisions and branches based on these. It is superior to most infeasible branching both in time and how far you come with an iteration limit.
Reliability branching Reliability branching combines strong and pseudocost branching. A variable is called unreliable if the pseudocost history for this variable is to small. In this case strong branching is used to determine the costs. This method brings an extra tuning parameter, in papers mostly called η. I added it to settings_bb->reliable_eta and set the default value to 6. I tested several η with different datasets. between 4 and 8 seems to be a good value so I choose 6 as a default.

To visualize how much it improves the result I created this graph for the Problem PP08ACUTS (from miplib 2010 download mps) with the different strategies displayed. In the y-axis you see the Lower and upper-bound and in the x-axis the time in seconds: graph over time since strong branching took so long i excluded it and the graph looks like this: graph without strong branching over time As you can see, the current implementation with most infeasible branching is just a little bit better than random branching. All other visible branching strategies are superior.

to show that strong branching is the best in regards of iteration limit, here the graph with iterations as x-axis, I limited the iterations of strong branching to 25'000 and to 50'000 for everything else. As you can see in the previous graphs, strong branching takes a long time.: graph over iterations

The branching strategy is chosen based on the settings_bb->branching_strategy parameter. I added an enum BRANCHING_STRATEGY for it.

enum BRANCHING_STRATEGY
{
    BRANCHING_STRATEGY_MOST_INFEASIBLE = 0,
    BRANCHING_STRATEGY_STRONG_BRANCHING = 1,
    BRANCHING_STRATEGY_PSEUDOCOST_BRANCHING = 2,
    BRANCHING_STRATEGY_RELIABILITY = 3,
    BRANCHING_STRATEGY_RANDOM = 4
};

Since reliability branching is supperior to most infeasible in all cases and aspects, I added it as default branching strategy.

Node selection methods

The current implementation uses a breath first approach, which is by definition the most efficient solution to prove the optimal solution. However most modern solvers use another techique called diving. For simplex based solvers this is a very efficient method for solving an ILP. With ECOS it is not as efficient but it is still a good method to find good integer solutions early on. In practice most of the time a customer is more interested in finding a good solution than improving the lower bound (and perhaps not finding a solution at all). With diving there are two possibiliteis, either dive on the left or on the right node. I implemented both methods. The node selection method can be set with the parameter settings_bb->node_selection_method. As before, I added an enum for easier understanding:

enum NODE_SELECTION_METHOD
{
    BREADTH_FIRST = 0,
    DIVE_LOWER_NODE = 1,
    DIVE_UPPER_NODE = 2,
};

I also set DIVE_LOWER_NODE as default setting for the reasons stated above.

Formatting & .gitignore

I autoformatted every file i touched and it matches now the style of ecos. I used vs-code so I added it to the .gitignore file

This change is

coveralls commented 5 years ago

Coverage remained the same at 89.251% when pulling 1772ffa67a64a8ed51b4e0a0555382ba1fc40990 on Isitar:feature/bb-branching-rules into 53db68793e020774fc14e8b3bee608b338c85fbd on embotech:develop.

sfiruch commented 5 years ago

Any chance this will be merged and released soon?

smerkli commented 5 years ago

@deiruch Yes, I'll look into it in the coming days. @Isitar Please contact ecos@embotech.com about accepting the contributor license agreement (https://github.com/embotech/ecos/blob/develop/CONTRIBUTING.md)

Isitar commented 5 years ago

@smerkli i sent an email that I accept the terms. Since you have this line in the terms: By contributing to the project in any traceable way (pull requests, issues, emails etc.), you agree to these terms. this was already the case.

smerkli commented 5 years ago

:D thanks for the email and for letting me know - I was tasked with making this process a bit more explicit, hence my request. Hopefully there will be a simple "I accept" button on PRs in the future to streamline this.

I'll try to review the PR soon and get back to you with comments!

smerkli commented 5 years ago

Alright, this now looks good, I ran all tests for all branching strategies and they pass, aside from test_basic, which has been failing already before this PR. Thanks again for the contribution!

embotech / ecos