coin-or/mibs

A solver for mixed integer bilevel programs

MibS

This file is auto-generated from config.yml using the generate_readme script. To make changes, please edit config.yml or the generation scripts here and here.

MibS is a solver for stochastic mixed integer bilevel linear optimization problems. For an introduction to bilevel optimization, see this slide deck. A somewhat outdated but still useful introduction to MibS is here. A paper that contains a complete technical description of the algorithms in MibS is here. A paper that discusses the cuts employed by MibS is here.

More detailed documentation is available here.

MibS is written in C++ and is released as open source under the Eclipse Public License 2.0.

It is distributed under the auspices of the COIN-OR Foundation

The MibS development site is https://github.com/coin-or/MibS.

CITE

Code:

Paper: https://doi.org/10.1007/s12532-020-00183-6

CURRENT BUILD STATUS

DOWNLOAD

Docker image

There is a Docker image that provides MibS, as well as other projects in the COIN-OR Optimization Suite here

Binaries

For newer releases, binaries will be made available as assets attached to releases in Github here. Older binaries are archived as part of MibS here.

Due to license incompatibilities, pre-compiled binaries may lack some functionality. If binaries are not available for your platform for the latest version and you would like to request them to be built and posted, feel free to let us know in the discussion formum.

Source

Source code can be obtained either by

• Downloading a snapshot of the source code for the latest release version of MibS from the releases page.
• Cloning this repository from Github or
• Using the coinbrew script to get the project and all dependencies (recommended, see below).

Below is a quick start guide for building on common platforms. More detailed build instructions are here.

Dependencies

MibS has a number of dependencies, which are detailed in config.yml. Dependencies on other COIN-OR projects are automatically downloaded when obtaining the source with coinbrew. For some of the remaining third-party dependencies, automatic download scripts and build wrappers are provided (and will also be automatically run for required and recommended dependencies), while other libraries that are aeasy to obtain must be installed using an appropriate package manager (or may come with your OS by default).

BUILDING from source

The quick start assumes you are in a bash shell.

Using coinbrew

To download and build MibS from source, execute the following on the command line.

wget https://raw.githubusercontent.com/coin-or/coinbrew/master/coinbrew
chmod u+x coinbrew
./coinbrew fetch MibS@master
./coinbrew build MibS

For more detailed instructions on coinbrew, see https://coin-or.github.io/coinbrew. The coinbrew script will fetch the additional projects specified in the Dependencies section of config.yml.

Without coinbrew (Expert users)

• Download the source code, e.g., by cloning the git repo https://github.com/coin-or/MibS
• Download and install the source code for the dependencies listed in config.yml
• Build the code as follows (make sure to set PKG_CONFIG_PTH to install directory for dependencies).

./configure -C
make
make test
make install

USING

Modelling Systems

MibS has interfaces to the following modelling systems that allow the user to conveniently build the bilevel model in a high-level modelling language and pass the model to MibS through the interface for solution.

• Pyomo (Python) through the PAO package, see here
• JuMP (Julia) through the BilevelJuMP package, see here for an example.

Command Line

To solve a deterministic mixed integer bilevel linear optimization problem, you must provide both an MPS file and an auxiliary information file that specifies which variables and constraints are associated with the each level (see a description of the file format here). Then call mibs like this:

<build_or_install_dir>/bin/mibs -Alps_instance file.mps -MibS_auxiliaryInfoFile aux_file.txt 

It is also possible to specify additional settings in a parameter file with, e.g.,

<build_or_install_dir>/bin/mibs -param <build_or_install_dir>/MibS/src/mibs.par 

MibS has many parameters. See the example parameter file mibs.par and the header file MibParams.hpp for explanations. You can also find a detailed description of MibS here. Furthermore, to conduct the experiments illustrated in this report, see the README file in the directory scripts.

MibS is also capable of solving two-stage mixed integer stochastic bilevel linear optimization problems. To solve these problems, there are two ways:

• Provide an MPS file, a time file and a stoch file in the same way as the SMPS format. The second-stage objective coefficients should be defined at the end of the time file (see here). Then call mibs like this:

  <build_or_install_dir>/bin/mibs -Alps_instance file.mps -MibS_auxiliaryTimFile file.tim -MibS_auxiliaryStoFile file.sto -MibS_stochasticityType stochasticWithoutSAA -MibS_isSMPSFormat 1 -MibS_isA2Random 1 
  

  The parameter MibS_isA2Random should be set to 0 in case the coefficients of the first-stage variables in the second-stage problem are not random variables.

• Provide an MPS file and an auxiliary information file in the same way as deterministic bilevel problems. The probability distributions of the random variables also should be specified by setting the values of corresponding parameters (MibS currently supports only the discrete uniform distribution). For a sample parameter file, see [src/mibsStochastic.par.in].

Project Links

• Additional documentation
• Code of Conduct
• COIN-OR Web Site
• Discussion forum
• Report a bug

ACKNOWLEDGEMENT

MibS was developed with support from

• Office of Naval Research (Grant N000141912330)
• National Science Foundation (Grants CMMI-1435453, CMMI-0728011, ACI-0102687)
• Lehigh University
• Zuse Institute Berlin
• Research Campus Modal "Mathematical Optimization and Data Analysis Laboratories" funded by the German Federal Ministry of Education and Research (BMBF Grant 05M14ZAM) and by the DFG SFB/Transregio 154

mibs's Issues

Library not loaded

Hi,
When I executed the MibS, I got the following error message. The platform is MacOS X and paths are already added to .bashrc. When I check the lib, I only find libCgl.0.dylib file. I wonder what can I do to solve this problem?

dyld: Library not loaded: /Users/luyu/Desktop/MibS/lib/libCgl.1.dylib
Referenced from: /Users/luyu/Desktop/MibS/bin/mibs
Reason: image not found
Abort trap: 6

Thank you very much!

Best,
Lu

Compiling error when solving bilevel model with MibS

Dear,

I am using MibS solver to tackle my Mixed Integer Bilevel model. However, when I run the model I got strange compiling error.

mibs: malloc.c:2401: sysmalloc: Assertion `(old_top == initial_top (av) && old_size == 0) || ((unsigned long) (old_size) >= MINSIZE && prev_inuse (old_top) && ((unsigned long) old_end & (pagesize - 1)) == 0)' failed.
Abandon (core dumped)

Please can someone help me to know what is wrong!

I attach output, mps and txt files.

Best regards,
Kaba
output.txt
bilevelModel.txt
bilevelModel.mps.txt

Confusion about example instance

I am trying to understand the data file format for specifying the lower level problem.

When I look at example milp_10_20_50_2310.txt, I see that the first LR entry is row 0. However, row 0 is the objective for the HPR. So how does MibS interpret row 0 as a constraint in the lower level problem?

Installing issue

Hi,
I downloaded the Mibs package, and when trying to install on my computer (mac os X) I have the error message :
BuildTools/get.dependencies.sh: line 656: declare: -A: invalid option
Any ideas please about the issue?
Thanks

Solver Failed

~/Desktop/MibS/build/bin/mibs -Alps_instance 1.mps -MibS_auxiliaryInfoFile aux.txt

== Welcome to the Abstract Library for Parallel Search (ALPS)
== Copyright 2000-2017 Lehigh University and others
== All Rights Reserved.
== Distributed under the Eclipse Public License 1.0
== Version: Trunk (unstable)
== Build Date: Mar 27 2018
== Revision Number: 2133
Alps0030I Data file: 1.mps
Coin0001I At line 1 NAME
Coin0001I At line 3 ROWS
Coin0001I At line 25 COLUMNS
Coin0001I At line 125 RHS
Coin0001I At line 141 BOUNDS
Coin0001I At line 157 ENDATA
Coin0002I Problem no_name has 20 rows, 15 columns and 92 elements
LL Data File: aux.txt
Number of LL Variables: 5

=======================================
Problem Structure

Number of UL Variables: 10
Number of LL Variables: 5
Number of UL Rows: 12
Number of LL Rows: 8
Number of integer UL Variables: 10
Number of integer LL Variables: 5
This instance is a pure integer bilevel optimization problem
Since no branching procedure is selected, it is set to 'MibSBranchingStrategyFractional' automatically.
'Pure integer cut' genertor is on.
Branching procedure is set to 'MibSBranchingStrategyFractional'.
'solveSecondLevelWhenXYVarsInt' is true.
'solveSecondLevelWhenLVarsFixed' is true.
'computeBestUBWhenLVarsFixed' is true.
'seenLinkingSolutions' pool is used.
== Bcps Version: Trunk (unstable)
== Bcps Revision Number: 2133
== Blis Version: Trunk (unstable)

Blis0043I Objective coefficients are multiples of 1
Alps0250I Starting search ...
ERROR:Status is unknown or not allowed
from function exploreSubTree
from class AlpsSubTree

Installation error

When installing on OSX:

./coin.install.sh build --no-prompt --main-proj=MibS CC=gcc-5 CXX=g++-5
./coin.install.sh: line 920: declare: -A: invalid option

Same error appears when running just ./coin.install.sh or ./coin.install.sh fetch build --no-prompt --main-proj=MibS

Write the solution to a file

It would be very handy if there was an option to write the solution to a file (in a structured manner) instead of printing it to stdout.

Infeasibility not found

We are running the latest version of MibS on Windows 10 to model a bilevel optimization problem in the field of auction design.

It would be great if you could help us with a problem which came up. In our model, lower level variables appear in upper level constraints and an optimal solution of the lower level can create infeasibility in the upper level. We are not sure whether this problem conflicts with the definition of bilevel programs or with the models you allow in your algorithm.

Consider the following model as a simple example:
min -x
s.t. y <= 0
y \in argmax {y, s.t. y <= 2, y \in R}
5 >= x >= 0; x \in Z

Here, the only solution which fulfills the second constraint (maximizing y with the single constraint y <= 2) is y = 2, which in turn leads to infeasibility in the upper level in combination with the first constraint (y <= 0). Therefore, as we understand it, the full model is infeasible. Of course, we can make the model more sophisticated, allowing for the lower level variable to not appear alone in an upper level constraint. However, using MibS on this model we get a ‘feasible’ solution with x = 5; y = 0:

We are sorry if we are missing something very fundamental here, like that the upper level constraints need to be respected in the lower level program – however to us the definitions did not force this.
We would be very grateful if you could help us with this problem. Please find attached the input files we use and the complete log.

Best regards,
Richard Littmann

infeasAux.txt

infeasMPS.mps.txt

infeasLog.txt

README and LICENSE do not agree about the license

Make error during installation

An other error occur in the (final?) step of the installation from the script.
Step executed:

 clang++ -DHAVE_CONFIG_H -I. -I/COIN-OR-OptimizationSuite/SYMPHONY/SYMPHONY/include -I../include -I/COIN-OR-OptimizationSuite/SYMPHONY/SYMPHONY/Applications/USER/include -I/COIN-OR-OptimizationSuite/Cgl/Cgl/src -I/COIN-OR-OptimizationSuite/Cgl/Cgl/src/CglAllDifferent -I/COIN-OR-OptimizationSuite/Cgl/Cgl/src/CglClique -I/COIN-OR-OptimizationSuite/Cgl/Cgl/src/CglDuplicateRow -I/COIN-OR-OptimizationSuite/Cgl/Cgl/src/CglFlowCover -I/COIN-OR-OptimizationSuite/Cgl/Cgl/src/CglGMI -I/COIN-OR-OptimizationSuite/Cgl/Cgl/src/CglGomory -I/COIN-OR-OptimizationSuite/Cgl/Cgl/src/CglKnapsackCover -I/COIN-OR-OptimizationSuite/Cgl/Cgl/src/CglLandP -I/COIN-OR-OptimizationSuite/Cgl/Cgl/src/CglLiftAndProject -I/COIN-OR-OptimizationSuite/Cgl/Cgl/src/CglMixedIntegerRounding -I/COIN-OR-OptimizationSuite/Cgl/Cgl/src/CglMixedIntegerRounding2 -I/COIN-OR-OptimizationSuite/Cgl/Cgl/src/CglOddHole -I/COIN-OR-OptimizationSuite/Cgl/Cgl/src/CglPreProcess -I/COIN-OR-OptimizationSuite/Cgl/Cgl/src/CglProbing -I/COIN-OR-OptimizationSuite/Cgl/Cgl/src/CglRedSplit -I/COIN-OR-OptimizationSuite/Cgl/Cgl/src/CglRedSplit2 -I/COIN-OR-OptimizationSuite/Cgl/Cgl/src/CglResidualCapacity -I/COIN-OR-OptimizationSuite/Cgl/Cgl/src/CglSimpleRounding -I/COIN-OR-OptimizationSuite/Cgl/Cgl/src/CglTwomir -I/COIN-OR-OptimizationSuite/Cgl/Cgl/src/CglZeroHalf -I/COIN-OR-OptimizationSuite/3/Cgl/src -I/COIN-OR-OptimizationSuite/Clp/Clp/src/OsiClp -I/COIN-OR-OptimizationSuite/Clp/Clp/src -I/COIN-OR-OptimizationSuite/3/Clp/src -I/COIN-OR-OptimizationSuite/Osi/Osi/src/Osi -I/COIN-OR-OptimizationSuite/3/Osi/src/Osi -I/COIN-OR-OptimizationSuite/CoinUtils/CoinUtils/src -I/COIN-OR-OptimizationSuite/3/CoinUtils/src -I/COIN-OR-OptimizationSuite/Clp/Clp/src/OsiClp -I/COIN-OR-OptimizationSuite/Clp/Clp/src -I/COIN-OR-OptimizationSuite/3/Clp/src -I/COIN-OR-OptimizationSuite/Osi/Osi/src/Osi -I/COIN-OR-OptimizationSuite/3/Osi/src/Osi -I/COIN-OR-OptimizationSuite/CoinUtils/CoinUtils/src -I/COIN-OR-OptimizationSuite/3/CoinUtils/src -I/COIN-OR-OptimizationSuite/Osi/Osi/src/Osi -I/COIN-OR-OptimizationSuite/3/Osi/src/Osi -I/COIN-OR-OptimizationSuite/CoinUtils/CoinUtils/src -I/COIN-OR-OptimizationSuite/3/CoinUtils/src -D__OSI_CLP__ -DSENSITIVITY_ANALYSIS -DUSE_CGL_CUTS -DSIGHANDLER -DHAS_RANDOM -DHAS_SRANDOM -D__NONE__ -D__DARWIN -DCOMPILE_IN_CG -DCOMPILE_IN_CP -DCOMPILE_IN_LP -DCOMPILE_IN_TM -O3 -pipe -DNDEBUG -Wparentheses -Wreturn-type -Wcast-qual -Wall -Wpointer-arith -Wwrite-strings -Wconversion -Wno-unknown-pragmas -Wno-long-long -DSYMPHONY_BUILD -c COIN-OR-OptimizationSuite/SYMPHONY/SYMPHONY/src/LP/lp_genfunc.c  -fno-common -DPIC -o .libs/libSym_la-lp_genfunc.o

Last lines with the error:

COIN-OR-OptimizationSuite/CoinUtils/CoinUtils/src/CoinPackedVector.hpp:252:6: note:
      in instantiation of function template specialization 'CoinSort_3<double,
      int, int, CoinFirstLess_3<double, int, int> >' requested here
   { CoinSort_3(elements_, elements_ + nElements_, origIndices_, indices_,
     ^
87 warnings and 1 error generated.
make[1]: *** [libSym_la-lp_genfunc.lo] Error 1
make: *** [all-recursive] Error 1

I couldn't find any similar error in the logs, could that be a missing dependency?

C++ Hello World - Segmentation Fault

Hello,

I am trying to build a minimal example for using MibS with C++.

Context

I am trying to model the following problem using the C++ API:

 min  -x − 7y
 s.t.   -3x + 2y ≤ 12
             x + 2y ≤ 20
             x ≤ 10
             y ∈ arg min {z : 2x - z ≤ 7,
                              -2x + 4z ≤ 16,
                              z ≤ 5}

Setting

• MibS 1.2 as built using coinbrew and linked with Cplex - though the problem I am facing seems indifferent to CPLEX.
• Ubuntu 22.04 LTS
• CMake as build system
• C++17

My Attempt

So far, I have tried with the following code.

    std::unique_ptr<OsiSolverInterface> solver(new OsiCpxSolverInterface());

    MibSModel model;
    model.setSolver(solver.get());

   // AUXILIARY DATA
    std::vector<int> upper_level_variables_indices = { 0,  };
    std::vector<int> lower_level_variables_indices = { 1,  };
    std::vector<int> upper_level_constraints_indices = { 0, 1,  };
    std::vector<int> lower_level_constraints_indices = { 2, 3,  };
    std::vector<double> lower_level_objective_coefficients = { 1,  };

    model.loadAuxiliaryData(
            (int) lower_level_variables_indices.size(),
            (int) lower_level_constraints_indices.size(),
            lower_level_variables_indices.data(),
            lower_level_constraints_indices.data(),
            1.,
            lower_level_objective_coefficients.data(),
            (int) upper_level_variables_indices.size(),
            (int) upper_level_constraints_indices.size(),
            upper_level_variables_indices.data(),
            upper_level_constraints_indices.data(),
            0,
            nullptr,
            0,
            nullptr,
            nullptr,
            nullptr
    );

   // PROBLEM DATA

    std::vector<double> variable_lower_bounds = { 0, 0,  };
    std::vector<double> variable_upper_bounds = { 10, 5,  };
    std::vector<char> variable_types = { 'I', 'I',  };
    std::vector<double> constraint_lower_bounds = { -1e+20, -1e+20, -1e+20, -1e+20,  };
    std::vector<double> constraint_upper_bounds = { 12, 20, 7, 16,  };
    std::vector<char> constraint_types = { 'L', 'L', 'L', 'L',  };
    std::vector<double> objective = { -1, -7,  };

    CoinPackedMatrix matrix(false, 0, 2);

    CoinPackedVector row1;
    row1.insert(0, -3);
    row1.insert(1, 2);
    matrix.appendRow(row1);

    CoinPackedVector row2;
    row2.insert(0, 1);
    row2.insert(1, 2);
    matrix.appendRow(row2);

    CoinPackedVector row3;
    row3.insert(0, 2);
    row3.insert(1, -1);
    matrix.appendRow(row3);

    CoinPackedVector row4;
    row4.insert(0, -2);
    row4.insert(1, 4);
    matrix.appendRow(row4);

    model.loadProblemData(
            matrix,
            variable_lower_bounds.data(),
            variable_upper_bounds.data(),
            objective.data(),
            constraint_lower_bounds.data(),
            constraint_upper_bounds.data(),
            variable_types.data(),
            1.,
            1e+20,
            constraint_types.data()
    );

Quesitons and Problems

• I get a Segmentation Fault when running this code. This happens in the call of loadProblemData and, in particular, seems to be in setUpperRowData.
• What does the arguments structRowXX relate to ?

Thank you,

Henri.

Is there C/C++ API for MibS

Dears,

When I installed MibS, I realized that to solve a mixed integer bilevel linear optimization problem, we must provide both an MPS file and an auxiliary information file that specifies which variables and constraints are associated with the each level.

I would like to know if there is an API (C, C++, Java, etc.) for MibS. If not, how to generate the two files (mps and txt) when we deal with an instance of a problem with thousands or even millions of variables and constraints ?

Best regards,
Kaba
Innovation and Technology Transfer engineer Inria Lille INOCS

Can’t find MibS/build/bin/mibs

hi, i meet a problem. when i finish installed Mibs in windows, i can't find this path.
only five .exe file in this directory, just like the picture shows.

i don't know how to fix it. please show a bright way to me. thanks a lot.

sincerely
a user : )

Infeasible instance solved as feasible

After having the problem with infeasibilities in our bilevel program and posting it on Github (issue #45) you uploaded a new version which fixed this problem for the instance we supplied. We continued working on our model and unfortunately encountered a similar problem with a new instance.

Again, we had a upper level constraint of the form

d <= 0

with a lower level variable d and a lower level problem of the form

d = {max d , s.t. ...}

We tested an infeasible instance (mpsFile_original, auxFile_original). MibS deemed the instance to be feasibly solvable and put out a solution to the problem with d = 0 and corresponding feasible assignments of other upper level and lower level variables which however would lead to the lower level problem not being maximized (log_original). When we fixed the upper level variables to the MibS output and ran MibS again on this instance (mpsFile_fixed_0), MibS correctly detected the infeasibility of the problem. Also, when we changed the upper level constraint to

d <= 1000,

MibS found a solution to the lower level with a positive value (which now of course is feasible for the whole problem), although this was not detected before (log_fixed_1000). As our model essentially has several lower levels, there are several lower level variables that should make the upper level infeasible:
y1,y2,y4,y5,y8. All of these have positive values and should therefore violate the respective <= 0 constraint (Dr14, DR17, DR4, DR6, DR9) in the upper level.

Unfortunately, we were not able to recreate this problem with a small toy example like the last time, so I am not sure whether it is easy to debug without deeper understanding of our BLP model. We checked our model several times and are quite certain that the results should differ from the solution by MibS. Should you need any info on the model or if you detect anything wrong with it which is problematic for MibS, we are happy to further discuss the issue.

Thank you once again for your great work on MibS. We are grateful for any help you can offer on this issue.

Kind regards,
Richard Littmann

auxFile_fixed_0.txt
auxFile_fixed_1000.txt
auxFile_original.txt
log_fixed_1000.txt
log_original.txt
mpsFile_fixed_0.txt
mpsFile_fixed_1000.txt
mpsFile_original.txt

Mistake in Documentation

Dears,

I think the optimal solution for the general example in the documentation for creating the MPS and Auxiliary file found here is incorrect. The solution C0 = 10 and C1 = 5 does not fulfills the lower level constraint 2*C0 - C1 <= 7. MibS optimal solution here is C0 = 6 and C1 = 5. Much Thanks!

Best Regards,
Gennesaret Tjusila

Typo in example

Hey Guys,

I think the first coefficient of the second lower-constraint in your example is -2. Thanks.

Issue with solving interdiction model

I get the error below when trying to solve my interdiction model. Since my model does not have a binary for each follower variable (all continuous), I am not labeling it as an interdiction model as described here: http://coral.ise.lehigh.edu/wp-content/uploads/2016/02/MibS_inputFile.pdf.

The leader's objective is -y while the follower's objective (to be minimized) is y where y is a continuous follower variable. All follower variables are continuous, but only some have associated leader binary variables. The leader has all binary variables, a knapsack constraint, and additional constraints only involving leader binary variables.

Since y is continuous and appears in the leader's objective, can this problem be solved through MibS?

MibS execution without retrieving solution file

Dear MibS-Team,

thanks for the development and maintaining of MibS!
By using MibS I face the problem, that no solution files can be retrieved, and after displaying

Branching strategy is to branch on all variables with fractional values.
Benders binary cut generator is on.
Generalized no-good cut generator is on.
Fractional cuts will be generated.
solveSecondLevelWhenXYVarsInt is set.
solveSecondLevelWhenLVarsFixed is set.
computeBestUBWhenLVarsFixed is set.
Linking solution pool will be used.
Alps0250I Starting search

in the cmd-line it terminates without printing any further information nor writing a result or log file to the working directory.
I tested it for two compiled versions of MibS MibS-releases.1.2.0-i686-w64-mingw32 and MibS-releases.1.2.0-w64-msvc17-md (with VS + C-plugin installed) on OS:Win11 with an i7 facing the same problem.
The files are initially created by pao, but it does not seem that the problem is located at a corrupted file-format, as I face the same issue for the provided files in #107 that have been executed successfully with MibS 1.2.
The files used for testing are attached below.

problem_mips.txt this is the .mps-file
problem_aux.txt this is the .aux-file

Thanks in advance for your support!

Best,
Kirill

LP/LP gets into infinite loop

Solving any pure LP bilevel program causes MibS to go into an infinite loop with "all linking variables should be discrete."

All linking variables should be discrete

Hey Guys,

I am receiving the following error All linking variables should be discrete for a bi-level problem with this structure:

min x_0 + x_1
x_0, x_1 in Z_+
2 <= x_0, x_1 <= 5
y in argmin cy
s.t. x_0 + A_1y <= b_1
x_1 + A_2y <= b_2
A_3y <= b_3
x, y in Z_+^2 * R_+^n
Presumably, x_0, x_1 are linking and they are discrete. What is missing here? Thanks in advance.

Fails to detect upper level variables and constraints

Hi,

I am currently trying to use MibS and I am not able to get it to work.
It seems like my upper level variables are not detected, this output suggests:

=======================================
Analyzing problem structure            
=======================================

Number of UL Variables: 29430
Number of LL Variables: 0
Number of UL Rows: 93180
Number of LL Rows: 0
Number of integer UL Variables: 10082
Number of integer LL Variables: 0
This instance is a mixed integer problem.
All lower level variables are binary.
Coefficient matrix of lower level variables in upper level problem is non-negative.
Coefficient matrix of upper level variables in lower level problem is non-negative.
Coefficient matrix of lower level variables in upper level problem is non-negative.

later followed by:

Alps0250I Starting search ...
loadProblem():The given matrix is empty!

First, I thought I had maybe misconfigured the .aux file, but then I tried your example from here and it the same happened.

Is this a current bug? Or am I missing something?

Thanks a lot!
Leon

malloc error when running MibS

Hi,

I am testing this solver for my research models. However, I met with the following malloc error:

== Welcome to the Abstract Library for Parallel Search (ALPS)
== Copyright 2000-2019 Lehigh University and others
== All Rights Reserved.
== Distributed under the Eclipse Public License 1.0
== Version: 1.5
== Build Date: Jun 19 2021
Alps0030I Data file: /Users/mac/Downloads/MODEL.mps
Coin0001I At line 1 NAME
Coin0001I At line 2 ROWS
Coin0001I At line 38 COLUMNS
Coin0001I At line 443 RHS
Coin0001I At line 478 BOUNDS
Coin0001I At line 483 ENDATA
Coin0002I Problem no_name has 34 rows, 91 columns and 341 elements
mibs(72078,0x1109cedc0) malloc: Incorrect checksum for freed object 0x7fb22f40ae78: probably modified after being freed.
Corrupt value: 0x2800000027
mibs(72078,0x1109cedc0) malloc: *** set a breakpoint in malloc_error_break to debug
Abort trap: 6

I wonder if it is because the aux or mps file are not matching properly or it is because of other problems?

Thanks very much for your help!

Best,
Evans Cai

How to use CPLEX?

Hi,
I want to use CPLEX instead of SYMPHONY, I changed the config file, but I can't link the solver.
Do you know what needs to be changed to link the solver?

Thank you.

Given any feasible upper level solution the lower level problem is feasible, however MibS found no solution?

Hi,

I wonder if I'm using the solver the wrong way...
My problem has four upper level feasible solutions.
If necessary I can generate and share the bilevel feasible solutions for this problem (I mean leader-feasible and follower optimal response).

My problem uses some input data and an underlying network G(V,E), where V is a set of components and E is a set of undirected edges. The horizon has two time periods, the leader defends at time t=1, and the follower can attack at times t=1 and/or t=2.

I use the following input files for MibS:
model.zip

Here is the output I received:
mibs_output.txt

Here is a bilevel optimal solution for the problem:

upper level: (minimizes the number of damaged components over horizon)
z[i, t] (indicates defend/protection of i at time t)
[(1,1) 0.0; (2,1) 1.0; (3,1) 0.0; (4,1) 0.0]

lower level: (maximizes the number of damaged components over horizon)
y[i,t,0] (indicates attack of i at time t)
[(1,1,0) 0.0; (2,1,0) 0.0; (3,1,0) 0.0; (4,1,0) 0.0; (1,2,0) 0.0; (2,2,0) 0.0; (3,2,0) 0.0; (4,2,0) 1.0]

w[i,t,0] (indicates spread damage in i at time t)
[(3, 2, 0) 1.0; (1, 2, 0) 0.0; (3, 1, 0) 0.0; (1, 1, 0) 0.0; (4, 2, 0) 1.0; (4, 1, 0) 0.0; (2, 2, 0) 0.0; (2, 1, 0) 0.0]

x[i,t,0] (measures the vulnerability of the component at time t) (z[i,t-1]=1 or w[i,t-1,0]=1 makes this measure decrease)
[(3, 2, 0) 14.267529141593812; (1, 2, 0) 6.551886343581829; (3, 1, 0) 13.872371946231844; (1, 1, 0) 4.726983106693199; (4, 2, 0) 16.33995846253321; (4, 1, 0) 16.32883247435988; (2, 2, 0) 8.165345055858875; (2, 1, 0) 16.010449108646597]

θ[i,t,0] (indicates the component i is vulnerable at time t, i.e. x[i,t,0] is over a threshold = 13.4)
[(3, 2, 0) 1.0; (1, 2, 0) 0.0; (3, 1, 0) 1.0; (1, 1, 0) 0.0; (4, 2, 0) 1.0; (4, 1, 0) 1.0; (2, 2, 0) 0.0; (2, 1, 0) 0.0]

ε[(i,j),t,0] (indicates the (i, j) ∈ E connection can spread the attack because both end-points are vulnerable at time t)
[((1, 2), 1, 0) 0.0; ((1, 3), 1, 0) 0.0; ((1, 2), 2, 0) 0.0; ((2, 4), 2, 0) 0.0; ((3, 4), 1, 0) 1.0; ((1, 3), 2, 0) 0.0; ((3, 4), 2, 0) 1.0; ((2, 4), 1, 0) 0.0]

ϕ[i,j,t,0] (indicates that (i,j) ∈ V×V are connected through active edges in E at time t, i.e., those having ε[(i,j),t,0]=1)
[(1, 1, 1, 0) 0.0; (2, 2, 2, 0) 0.0; (1, 2, 1, 0) 0.0; (2, 3, 2, 0) 0.0; (4, 4, 2, 0) 1.0; (1, 3, 1, 0) 0.0; (2, 4, 2, 0) 0.0; (1, 1, 2, 0) 0.0; (1, 4, 1, 0) 0.0; (3, 3, 1, 0) 1.0; (1, 2, 2, 0) 0.0; (3, 4, 1, 0) 1.0; (1, 3, 2, 0) 0.0; (1, 4, 2, 0) 0.0; (2, 2, 1, 0) 0.0; (3, 3, 2, 0) 1.0; (2, 3, 1, 0) 0.0; (4, 4, 1, 0) 1.0; (3, 4, 2, 0) 1.0; (2, 4, 1, 0) 0.0]

μ[(k,k'), i, j, t, 0] (flow through arc (k,k') where (k,k') ∈ E or (k',k) ∈ E of a commodity sourced at component i directed towards component j at time t)
[((2, 1), 1, 4, 2, 0) 0.0; ((3, 4), 1, 4, 2, 0) 0.0; ((4, 3), 2, 3, 2, 0) 0.0; ((2, 4), 2, 3, 1, 0) 0.0; ((4, 2), 1, 4, 1, 0) 0.0; ((2, 4), 2, 3, 2, 0) 0.0; ((4, 3), 1, 4, 1, 0) 0.0; ((4, 2), 1, 4, 2, 0) 0.0; ((4, 3), 1, 4, 2, 0) 0.0; ((2, 4), 1, 4, 1, 0) 0.0; ((1, 2), 2, 3, 1, 0) 0.0; ((3, 1), 2, 3, 1, 0) 0.0; ((2, 4), 1, 4, 2, 0) 0.0; ((1, 3), 2, 3, 1, 0) 0.0; ((1, 2), 2, 3, 2, 0) 0.0; ((3, 1), 2, 3, 2, 0) 0.0; ((1, 3), 2, 3, 2, 0) 0.0; ((1, 2), 1, 4, 1, 0) 0.0; ((3, 1), 1, 4, 1, 0) 0.0; ((1, 3), 1, 4, 1, 0) 0.0; ((1, 2), 1, 4, 2, 0) 0.0; ((3, 1), 1, 4, 2, 0) 0.0; ((2, 1), 2, 3, 1, 0) 0.0; ((1, 3), 1, 4, 2, 0) 0.0; ((3, 4), 2, 3, 1, 0) 0.0; ((2, 1), 2, 3, 2, 0) 0.0; ((3, 4), 2, 3, 2, 0) 0.0; ((4, 2), 2, 3, 1, 0) 0.0; ((2, 1), 1, 4, 1, 0) 0.0; ((3, 4), 1, 4, 1, 0) 0.0; ((4, 3), 2, 3, 1, 0) 0.0; ((4, 2), 2, 3, 2, 0) 0.0]

ϕy[i,j,t,0] (product between variables ϕ[i,j,t,0] and y[j,t,0])
[(1, 1, 1, 0) 0.0; (2, 2, 2, 0) 0.0; (1, 2, 1, 0) 0.0; (2, 3, 2, 0) 0.0; (4, 4, 2, 0) 1.0; (1, 3, 1, 0) 0.0; (2, 4, 2, 0) 0.0; (1, 1, 2, 0) 0.0; (1, 4, 1, 0) 0.0; (3, 3, 1, 0) 0.0; (1, 2, 2, 0) 0.0; (3, 4, 1, 0) 0.0; (1, 3, 2, 0) 0.0; (1, 4, 2, 0) 0.0; (2, 2, 1, 0) 0.0; (3, 3, 2, 0) 0.0; (2, 3, 1, 0) 0.0; (4, 4, 1, 0) 0.0; (3, 4, 2, 0) 1.0; (2, 4, 1, 0) 0.0]

Thanks!

follower as maximization problem

I found this very weird behavior on one instance that I wanted to share with you.

When I solve the problem with the auxiliary file presenting the follower as maximization (problem.mps paired with followerasMax.aux), I get an output which I am pretty sure is not bilevel feasible.

Now if I solve the same problem but with the auxiliary file presenting the follower as minimization (testProblem.mps paired with followerasMin.aux), then I get an optimal solution to the problem. Now the only difference between the auxiliary files is OS=1 vs OS=-1 and the same exact coefficients but multiplied by (-1).

Thanks in advance,

Leo

problem.txt
followerasMin.txt
followerasMax.txt

Question about MibS Solver (potential Bug)

Julia_Model_MibS.txt

Hello, I am a student at the University of Siegen. I am using the MibS solver for my Master's thesis. However, I trouble with the Julia model in the appendix. In particular, the output of the lower level variables does not reflect what the lower constraints should do. Actually, each node should be visited once and no circles to itself should be created. Is this a bug?

Best regards,

Nick Kontorzik

Installation issue in last step

Hi

The steps to Configure, Build, Run and Install for Blas 1.4, Lapack 1.5 are completed.
There is an error in Running CoinUtils as follows. Any idea to solve this issue and move further? Thanks in advance.

##################################################

Running CoinUtils unit test

##################################################

Testing CoinFinite ... finite value: ok; infinite value: ok.
Testing CoinIsnan ... finite value: ok; NaN value: ok.
Testing CoinModel
Assertion failed: numErr== 0, file C:/MSYS64/home/DELL/coinbrew/CoinUtils/CoinUtils/test/CoinModelTest.cpp, line 447
make[1]: *** [Makefile:600: test] Error 3
make: *** [Makefile:819: test] Error 2

Build failed, see error output above

Variables Correspondence and Lower Level Objective

Hi,

For the display of the solution,

1 since I have defined 192 variables, but the solution only gave part of the variable values, and its order is not like they appeared in the .mps file(they all show as x[...] and y[...]), and I don't know how to match these x[...] and y[...] with the variables that I defined

2 also, what about the lower level objective value, I assume I did not see it in the solution.

Thanks a lot and have a nice day!

Best,
Yaheng

Instances crash with "sym_get_col_solution(): No solution has been stored!" message

I'm running the latest version of MibS on Ubuntu 15.10 to check some properties of small graphs that I express as pure bilevel integer programs. In default settings my instances crash with the aforementioned message.
GraphPebblingInstances.zip

Installation issue in the building step

Hi, I'm using macOS Catalina, and when I build the 1.1.3 version with "--test non", I receive the following error massages in the step of building MibS:

/Users/mac/coinbrew/MibS/src/MibSCutGenerator.cpp:2239:52: error: no member named 'deletePrunedNodes' in 'AlpsParams'; did you mean 'deleteDeadNode'? ...boundModel->AlpsPar()->setEntry(AlpsParams::deletePrunedNodes, true);

/Users/mac/coinbrew/MibS/src/MibSCutGenerator.cpp:2318:40: error: no member named 'getWorkingSubTree' in 'AlpsKnowledgeBrokerSerial' AlpsSubTree *boundProbTree = broker.getWorkingSubTree();

Then the build just failed.

Thank you very much!

Best,
Evans Cai

Suggestion : Handle unbounded high-point relaxation

Hello,

I am suggesting an enhancement to MibS and will try to motivate this with an example.

Enhancement Handle MILP-MILP Bilevel problems with unbounded high-point relaxation.

Motivation The main motivation comes from the two-stage robust optimization literature and, in particular, the adversarial problem therein, which is a bilevel problem.

Two-stage robust optimization is concerned with general problems of the form

$$ \begin{align} \min_x \ & c^\top x \\ \text{s.t.} \ & x\in X, \\ & \forall \xi\in\Xi, \exists y\in Y(x,\xi). \end{align} $$

Here, $X$ is called the first-stage feasible space, $\Xi$ is the uncertainty set and $Y(x,\xi)$ is the second-stage feasible space.

One traditional method to solve such problems is through column-and-constraint generation. This method considers a finite subset $\lbrace \xi^1, \dotsc, \xi^K \rbrace \subset \Xi$ and solves the relaxation

$$ \begin{align} \min_x \ & c^\top x \\ \text{s.t.} \ & x\in X, \\ & y^k\in Y(x,\xi^k) \qquad k=1,\dotsc,K. \end{align} $$

Then, one needs to check if a (projected) solution to this relaxation, say $\hat x$, is feasible for the original problem. Hence, one needs to search for a $\xi\in \Xi$ such that $Y(x,\xi) = \emptyset$. This can be done by solving a bilevel problem which maximizes newly introduced "artificial" variables in the second stage, i.e., one solves

$$ \begin{align} \max_{\xi\in\Xi} \ & s \\ \text{s.t.} \ & \xi\in\Xi, \\ & y\in\text{arg min}_y { s : y\in Y(x,\xi) + s }. \end{align} $$

Unfortunately, this problem has an unbounded high-point relaxation which makes it unsolvable by MibS.

Hence, in order to be able to use MibS in, e.g., column-and-constraint algorithms as a sub-routine for two-stage robust problem, it would be very nice if MibS could solve such problems.

I am open to discussion on how this can be achieved (included, if needed, contribution to the MibS code).

Thank you,

Henri.