search

jump-dev / HiGHS.jl

A Julia interface to the HiGHS solver
https://highs.dev
MIT License
108 stars 15 forks source link

Add support for VariablePrimalStart #128

Closed odow closed 1 year ago

odow commented 2 years ago

Closes #126

This won't work for now, because it requires a new upstream release of HiGHS.

odow commented 1 year ago 
julia> using JuMP

julia> import HiGHS
[ Info: Precompiling HiGHS [87dc4568-4c63-4d18-b0c0-bb2238e4078b]

julia> function main(N)
           w, c = rand(N), rand(N)
           model = Model(HiGHS.Optimizer)
           @variable(model, x[1:N], Bin)
           @constraint(model, w' * x <= 0.1 * N)
           @objective(model, Max, c' * x)
           optimize!(model)
           y = value.(x)

           model = Model(HiGHS.Optimizer)
           @variable(model, x[i = 1:N], Bin, start = y[i])
           @constraint(model, w' * x <= 0.1 * N)
           @objective(model, Max, c' * x)
           optimize!(model)
           return
       end
main (generic function with 1 method)

julia> main(10)
Running HiGHS 1.3.0 [date: 1970-01-01, git hash: e5004072b-dirty]
Copyright (c) 2022 ERGO-Code under MIT licence terms
Presolving model
1 rows, 10 cols, 10 nonzeros
1 rows, 4 cols, 4 nonzeros

Solving MIP model with:
   1 rows
   4 cols (4 binary, 0 integer, 0 implied int., 0 continuous)
   4 nonzeros

        Nodes      |    B&B Tree     |            Objective Bounds              |  Dynamic Constraints |       Work      
     Proc. InQueue |  Leaves   Expl. | BestBound       BestSol              Gap |   Cuts   InLp Confl. | LpIters     Time

         0       0         0   0.00%   2.075119241     -inf                 inf        0      0      0         0     0.0s

Solving report
  Status            Optimal
  Primal bound      1.96795524881
  Dual bound        1.96795524881
  Gap               0% (tolerance: 0.01%)
  Solution status   feasible
                    1.96795524881 (objective)
                    0 (bound viol.)
                    0 (int. viol.)
                    0 (row viol.)
  Timing            0.01 (total)
                    0.00 (presolve)
                    0.00 (postsolve)
  Nodes             1
  LP iterations     1 (total)
                    0 (strong br.)
                    0 (separation)
                    0 (heuristics)
Running HiGHS 1.3.0 [date: 1970-01-01, git hash: e5004072b-dirty]
Copyright (c) 2022 ERGO-Code under MIT licence terms
Presolving model
1 rows, 10 cols, 10 nonzeros
1 rows, 4 cols, 4 nonzeros

MIP start solution is feasible, objective value is 1.96795524881

Solving report
  Status            Optimal
  Primal bound      1.96795524881
  Dual bound        1.96795524881
  Gap               0% (tolerance: 0.01%)
  Solution status   feasible
                    1.96795524881 (objective)
                    0 (bound viol.)
                    0 (int. viol.)
                    0 (row viol.)
  Timing            0.00 (total)
                    0.00 (presolve)
                    0.00 (postsolve)
  Nodes             0
  LP iterations     0 (total)
                    0 (strong br.)
                    0 (separation)
                    0 (heuristics)

but it's possible to segfault it

julia> main(100)
Running HiGHS 1.3.0 [date: 1970-01-01, git hash: e5004072b-dirty]
Copyright (c) 2022 ERGO-Code under MIT licence terms
Presolving model
1 rows, 100 cols, 100 nonzeros
1 rows, 100 cols, 100 nonzeros

Solving MIP model with:
   1 rows
   100 cols (100 binary, 0 integer, 0 implied int., 0 continuous)
   100 nonzeros

        Nodes      |    B&B Tree     |            Objective Bounds              |  Dynamic Constraints |       Work      
     Proc. InQueue |  Leaves   Expl. | BestBound       BestSol              Gap |   Cuts   InLp Confl. | LpIters     Time

         0       0         0   0.00%   52.66944363     -inf                 inf        0      0      0         0     0.0s
 S       0       0         0   0.00%   52.66944363     25.17042529      109.25%        0      0      0         0     0.0s
 R       0       0         0   0.00%   25.90750811     25.38155997        2.07%        0      0      0         2     0.0s

25.0% inactive integer columns, restarting
Model after restart has 1 rows, 75 cols (75 bin., 0 int., 0 impl., 0 cont.), and 75 nonzeros

         0       0         0   0.00%   25.90750811     25.38155997        2.07%        0      0      0         2     0.0s
 R       0       0         0   0.00%   25.90750811     25.48912548        1.64%        0      0      0         2     0.0s

20.0% inactive integer columns, restarting
Model after restart has 1 rows, 60 cols (60 bin., 0 int., 0 impl., 0 cont.), and 60 nonzeros

         0       0         0   0.00%   25.90750811     25.48912548        1.64%        0      0      0         2     0.0s
         0       0         0   0.00%   25.90750811     25.48912548        1.64%        0      0      2         2     0.0s
 L       0       0         0   0.00%   25.81566801     25.78529382        0.12%      345     18      4        49     0.1s

75.0% inactive integer columns, restarting
Model after restart has 1 rows, 15 cols (15 bin., 0 int., 0 impl., 0 cont.), and 15 nonzeros

         0       0         0   0.00%   25.81550426     25.78529382        0.12%        9      0      0       124     0.1s
         0       0         0   0.00%   25.81498701     25.78529382        0.12%        9      8      2       135     0.1s

Solving report
  Status            Optimal
  Primal bound      25.7852938161
  Dual bound        25.7852938161
  Gap               0% (tolerance: 0.01%)
  Solution status   feasible
                    25.7852938161 (objective)
                    0 (bound viol.)
                    0 (int. viol.)
                    0 (row viol.)
  Timing            0.09 (total)
                    0.00 (presolve)
                    0.00 (postsolve)
  Nodes             1
  LP iterations     289 (total)
                    0 (strong br.)
                    134 (separation)
                    142 (heuristics)
Running HiGHS 1.3.0 [date: 1970-01-01, git hash: e5004072b-dirty]
Copyright (c) 2022 ERGO-Code under MIT licence terms
Presolving model
1 rows, 100 cols, 100 nonzeros
1 rows, 100 cols, 100 nonzeros

MIP start solution is feasible, objective value is 25.7852938161

Solving MIP model with:
   1 rows
   100 cols (100 binary, 0 integer, 0 implied int., 0 continuous)
   100 nonzeros

        Nodes      |    B&B Tree     |            Objective Bounds              |  Dynamic Constraints |       Work      
     Proc. InQueue |  Leaves   Expl. | BestBound       BestSol              Gap |   Cuts   InLp Confl. | LpIters     Time

         0       0         0   0.00%   52.66944363     25.78529382      104.26%        0      0      0         0     0.0s

82.0% inactive integer columns, restarting
Model after restart has 1 rows, 18 cols (18 bin., 0 int., 0 impl., 0 cont.), and 18 nonzeros

         0       0         0   0.00%   25.90750811     25.78529382        0.47%        0      0      0         2     0.0s
         0       0         0   0.00%   25.90750811     25.78529382        0.47%        0      0      2         2     0.0s

11.1% inactive integer columns, restarting
Model after restart has 1 rows, 16 cols (16 bin., 0 int., 0 impl., 0 cont.), and 16 nonzeros

         0       0         0   0.00%   25.85686013     25.78529382        0.28%        4      0      0        39     0.0s
         0       0         0   0.00%   25.85686013     25.78529382        0.28%        4      4      2        45     0.0s
julia(33486,0x1117cce00) malloc: Incorrect checksum for freed object 0x7fe20e506708: probably modified after being freed.
Corrupt value: 0x3febdc0fd6e94080
julia(33486,0x1117cce00) malloc: *** set a breakpoint in malloc_error_break to debug

signal (6): Abort trap: 6
in expression starting at REPL[5]:1

signal (4): Illegal instruction: 4
in expression starting at REPL[5]:1
(base) oscar@Oscars-MBP /tmp %
codecov[bot] commented 1 year ago

Codecov Report

Base: 83.07% // Head: 83.07% // No change to project coverage :thumbsup:

Coverage data is based on head (ccd56e2) compared to base (ccd56e2). Patch has no changes to coverable lines.

:exclamation: Current head ccd56e2 differs from pull request most recent head c98099a. Consider uploading reports for the commit c98099a to get more accurate results

Additional details and impacted files ```diff @@ Coverage Diff @@ ## master #128 +/- ## ======================================= Coverage 83.07% 83.07% ======================================= Files 3 3 Lines 1365 1365 ======================================= Hits 1134 1134 Misses 231 231 ``` Help us with your feedback. Take ten seconds to tell us [how you rate us](https://about.codecov.io/nps?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=jump-dev). Have a feature suggestion? [Share it here.](https://app.codecov.io/gh/feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=jump-dev)

:umbrella: View full report at Codecov.
:loudspeaker: Do you have feedback about the report comment? Let us know in this issue.

odow commented 1 year ago

Can reproduce segfault upstream https://github.com/ERGO-Code/HiGHS/issues/983

odow commented 1 year ago

Fixed upstream. Waiting for v1.3.1 release.

odow commented 1 year ago

Confirm the segfault is fixed.