Alps Error: Status is unknown or not allowed.

[hlefebvr]

Hi,

I am coming here to report an error I am getting while solving mixed-integer linear bilevel problems.
I attach the .aux and .mps file below.

The Error

Here are the logs.

./mibs -MibS_auxiliaryInfoFile a3c82d6d-6a70-4c8d-b1f2-cdd8c6c39513-bilevel.aux -instance a3c82d6d-6a70-4c8d-b1f2-cdd8c6c39513-bilevel.mps

========================================================
========================================================
Welcome to MibS (Mixed Integer Bilevel Solver)
Copyright (C) 2007-2023 Lehigh University, Scott DeNegre, Ted Ralphs
and Sahar Tahernejad.
All Rights Reserved.
This software is licensed under the Eclipse Public License. Please see
accompanying file for terms.
Version: 1.2.2
Build Date: Feb  5 2025
==  Alps Version: 1.5.12
==  Bcps Version: 0.94.9
==  Blis Version: 0.94.13
========================================================
========================================================

Alps0030I Data file: /home/henri/Research/idol/cmake-build-debug/examples/robust/a3c82d6d-6a70-4c8d-b1f2-cdd8c6c39513-bilevel.mps
Coin0001I At line 1 NAME a3c82d6d-6a70-4c8d-b1f2-cdd8c6c39513-bilevel
Coin0001I At line 2 ROWS
Coin0001I At line 175 COLUMNS
Coin0001I At line 1118 RHS
Coin0001I At line 1290 BOUNDS
Coin0001I At line 1931 ENDATA
Coin0002I Problem a3c82d6d-6a70-4c8d-b1f2-cdd8c6c39513-bilevel has 171 rows, 320 columns and 620 elements
Auxiliary file: /home/henri/Research/idol/cmake-build-debug/examples/robust/a3c82d6d-6a70-4c8d-b1f2-cdd8c6c39513-bilevel.aux
Number of LL Variables:   245

Generic MILP cuts will be generated.
=======================================
Problem structure            
=======================================

Number of UL Variables (total): 75
Number of UL Variables (integer): 75
Number of LL Variables (total): 245
Number of LL Variables (integer): 75
Number of UL Rows: 1
Number of LL Rows: 170
This instance is a mixed integer problem.
All upper level variables are binary.
Coefficient matrix of lower level variables in upper level problem is non-negative.
Coefficient matrix of upper level variables in upper level problem is non-negative.
Coefficient matrix of lower level variables in upper level problem is non-positive.
Coefficient matrix of upper level variables in lower level problem is non-positive.
All rows at the upper level have non-positive coefficients
Degree of objective alignment: -1

=======================================
Parameter Settings                     
=======================================

Branching strategy is to branch only on variable with fractional values.
Generic MILP cuts will be generated.
Benders binary cut generator is on.
Generalized no-good cut generator is on.
Hypercube intersection cut generator is on.
Second level problem will be solved when linking variables are fixed
  or first and second level variables are integer.
Upper bounding problem will be solved when linking variables are fixed.
Linking solution pool will be used.

Alps0250I Starting search ...

Nodes Done   Upper Bound   Lower Bound      Gap   Time Nodes Left
         0             0         -1043   99.90%      0          1
0
ERROR:Status is unknown or not allowed
 from function exploreSubTree
 from class AlpsSubTree

Note that the same error occurs with CPLEX used as feasibility checked.

Moreover, the HPR is bounded, as solved by Gurobi here:

gurobi_cl a3c82d6d-6a70-4c8d-b1f2-cdd8c6c39513-bilevel.mps
Set parameter Username
Set parameter LogFile to value "gurobi.log"
Using license file /home/henri/gurobi.lic
Academic license - for non-commercial use only - expires 2025-12-22

Gurobi Optimizer version 11.0.0 build v11.0.0rc2 (linux64 - "Ubuntu 22.04.4 LTS")
Copyright (c) 2023, Gurobi Optimization, LLC

Read MPS format model from file /home/henri/Research/idol/cmake-build-debug/examples/robust/a3c82d6d-6a70-4c8d-b1f2-cdd8c6c39513-bilevel.mps
Reading time = 0.00 seconds
a3c82d6d-6a70-4c8d-b1f2-cdd8c6c39513-bilevel: 171 rows, 320 columns, 620 nonzeros

CPU model: 12th Gen Intel(R) Core(TM) i5-1235U, instruction set [SSE2|AVX|AVX2]
Thread count: 12 physical cores, 12 logical processors, using up to 12 threads

Optimize a model with 171 rows, 320 columns and 620 nonzeros
Model fingerprint: 0x37f3e0e2
Variable types: 170 continuous, 150 integer (0 binary)
Coefficient statistics:
  Matrix range     [1e+00, 4e+01]
  Objective range  [1e+00, 1e+00]
  Bounds range     [1e+00, 2e+02]
  RHS range        [1e+00, 2e+02]
Found heuristic solution: objective -1043.000000

Explored 0 nodes (0 simplex iterations) in 0.00 seconds (0.00 work units)
Thread count was 1 (of 12 available processors)

Solution count 1: -1043 
No other solutions better than -1043

Optimal solution found (tolerance 1.00e-04)
Best objective -1.043000000000e+03, best bound -1.043000000000e+03, gap 0.0000%

More Details

It looks like Alps encounters a node with status AlpsNodeStatusCandidate, the comment there says Status cannot be left as or changed back to candidate. Then, the exception is thrown; see file AlpsSubTree.cpp, line 1380.

Attached Files

a3c82d6d-6a70-4c8d-b1f2-cdd8c6c39513-bilevel.aux.txt
a3c82d6d-6a70-4c8d-b1f2-cdd8c6c39513-bilevel.mps.txt

[tkralphs]

Sorry for the delay on this, I only saw this issue now. When I build with debugging enabled, the code fails on an assert on line 636 in MibSTreeNode.cpp. This indicates that the LP solver bailed out for some reason, perhaps numerical issues. I would suggest trying to solve the LP relaxation with Clp directly and see what happens. Hopefully, this is something you can just report as an issue in the Clp project. I don't think we currently support the option to use an LP solver other then Clp, but I guess that is something we could think about adding for better handling of numerics.

[hlefebvr]

So, turns out that running MibS with -MibS_turnOffDefaultCuts 1, i.e., turning off all cuts not explicitly turned on by parameters, makes it work; no error. But this is doing pure branch-and-bound then, right?

Also, the root node can be solved without problem by Clp.

[tkralphs]

Yes, if you don't turn on any cuts by parameters then you are doing pure branch and bound. If the issue is numerical, then it would make sense that turning off cuts fixes it. There are other things you could play with if your goal is just to solve some particular fixed instances and you don't mind tweaking parameters a little. You could try playing with -scaleConFactor to be more aggressive with discarding potentially problematic cuts, but if you do this too aggressively and you are branching on fractional variables, you may get failures arising because there is an integer point that cannot be cut off. Switching to branching on linking variables (-branchStrategy 1) would fix that, but tends to result in slower solve times.