search

ERGO-Code / HiGHS

Linear optimization software
MIT License
957 stars 177 forks source link

HiGHS: Create dual ray when solving QPs #1350

Open stumarcus314 opened 1 year ago

stumarcus314 commented 1 year ago

I get an error when I try to solve a feasibility problem in JuMP using HiGHS. I use Julia v1.9.1 with the Julia packages JuMP v1.12.0 and HiGHS v1.5.2.

$ julia JuMP_solve.jl Running HiGHS 1.5.3 [date: 1970-01-01, git hash: 45a127b78] Copyright (c) 2023 HiGHS under MIT licence terms Presolving model 270074 rows, 274684 cols, 1084700 nonzeros 269789 rows, 274399 cols, 1082726 nonzeros Objective function is integral with scale 1

Solving MIP model with: 269789 rows 274399 cols (274398 binary, 1 integer, 0 implied int., 0 continuous) 1082726 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%   0               inf                  inf        0      0      0         0     2.2s

Solving report Status Infeasible Primal bound inf Dual bound inf Gap inf Solution status - Timing 44.02 (total) 1.44 (presolve) 0.00 (postsolve) Nodes 1 LP iterations 11798 (total) 0 (strong br.) 0 (separation) 0 (heuristics) ERROR: No invertible representation for getDualRay 45.992959 seconds (3.86 M allocations: 492.087 MiB, 0.48% gc time, 0.52%

stumarcus314 commented 1 year ago

Attached is the MPS.GZ file that generates the error. p12_fix0_MILP_binary_x_for_HiGHS.mps.gz

jajhall commented 1 year ago

If a MIP is infeasible there's no dual ray

stumarcus314 commented 1 year ago

Is Julia's JuMP requesting a dual ray after HiGHS solves the MIP?

jajhall commented 1 year ago

I don't know. I don't see why it should.

In the case you've highlighted, HiGHS should report something more informative. I'll see that it does

odow commented 1 year ago

We check if there is a dual ray for all infeasible problems:

https://github.com/jump-dev/HiGHS.jl/blob/0160bd354c9587c0aa95944f8bbda8d21a735424/src/MOI_wrapper.jl#L1700C7-L1703

We trap and handle the error, so this is not an actual problem and no error is thrown from Julia. It's just a printing issue.

jajhall commented 1 year ago

Once #1359 is merged into master, HiGHS no longer logs anything or returns an error from getDualRay if the model is a MIP, since there will never be an invertible representation, so the ray is not well defined.