Skip to content

test_check_binary_solution fails on emulated ARM64 systems #34

Open
Open
test_check_binary_solution fails on emulated ARM64 systems#34
@mirhahn

Description

@mirhahn
mirhahn
opened on Nov 24, 2023

Summary

When the extension module is built and tested on an emulated 64-bit ARM architecture (specificly, an emulated QEMU cortex-a57 machine), the test function test_check_binary_solution in test/combina_test.py appears to consistently fail. This appears to not be due to an actual malfunction. Rather, PyCombina appears to find an equivalent solution or solution with indistinguishable objective.

Similar observations can be made on some configurations of emulated 32-bit x86 Linux machines. They may be caused by the effect of subtle differences in floating point arithmetic between these CPU architectures on tree search decisions.

Steps to Reproduce

Reproducing this problem requires either a hardware ARM64 system (might work on an Apple M1). Here, we will discuss the emulation setup on an up-to-date Ubuntu Linux system. These steps were tested on only one specific host system (as well as a Gitlab Action runner of unknown hardware specifications). The following program outputs describe the test systems CPU, Kernel, and OS distribution version:
cpuid.txt
lscpu.txt
lsb_release.txt
uname.txt

For the emulation setup, we require the following packages:

  • libvirt-clients
  • libvirt-daemon
  • libvirt-daemon-driver-qemu
  • virtinst
  • qemu-system-arm
  • qemu-efi-aarch64

We also require an installation image for a reasonably sized Linux distribution. Alpine Linux' virt installation ISO will work:

wget https://dl-cdn.alpinelinux.org/alpine/v3.18/releases/aarch64/alpine-virt-3.18.4-aarch64.iso

Remember to verify checksums.

We can then set up the virtual machine with the command

virt-install \
    --connect qemu:///session \
    --name pycombina-test-env \
    --arch aarch64 \
    --machine virt \
    --virt-type qemu \
    --boot uefi \
    --boot loader=/usr/share/AAVMF/AAVMF_CODE.fd,loader_ro=yes,loader_type=pflash \
    --cdrom alpine-virt-3.18.4-aarch64.iso \
    --disk size=5 \
    --osinfo detect=on \
    --network user \
    --autoconsole text

The virt-install call should automatically open a text console interface to the virtual machine. You can log in as root without password and run the command

setup-alpine

This will guide you through the installation process. For most options, you can give the default response. The following settings are important:

  • set your appropriate keyboard layout;
  • the network device should use DHCP;
  • the disk vda should be used for the purpose sys (otherwise, you will run out of space on your RAM disk);
  • root should have a known (or empty) password;
  • no additional users are required (or should be used).

Afterwards, you can reboot the VM using the reboot command. Take note that all of this will take a lot longer than you might expect. This is normal on an emulated CPU.

After the reboot, log in as root and run the following commands:

setup-apkrepos -1 -c
apk add git python3 python3-dev py3-pip py3-virtualenv gcc g++
git clone -b main https://github.com/adbuerger/pycombina.git
cd pycombina
virtualenv venv
. venv/bin/activate
pip install .[dev]

Finally, you can execute the test suite with

pytest -vvv .

We can subsequently remove the VM from the host machine by calling

virsh --connect qemu:///session destroy pycombina-test-env
virsh --connect qemu:///session undefine --nvram pycombina-test-env
virsh --connect qemu:///session vol-delete --pool default pycombina-test-env.qcow2

Observed output

============================= test session starts ==============================
platform linux -- Python 3.11.6, pytest-7.4.3, pluggy-1.3.0 -- /root/pycombina/venv/bin/python
cachedir: .pytest_cache
rootdir: /root/pycombina
configfile: pyproject.toml
collecting ... collected 14 items

test/combina_test.py::CombinaTestSingleInputBnB::test_check_binary_solution FAILED [  7%]
test/combina_test.py::CombinaTestSingleInputBnB::test_check_n_max_switches PASSED [ 14%]
test/combina_test.py::CombinaTestSingleInputBnB::test_check_objective PASSED [ 21%]
test/combina_test.py::CombinaTestSingleInputMILP::test_check_binary_solution SKIPPED [ 28%]
test/combina_test.py::CombinaTestSingleInputMILP::test_check_n_max_switches SKIPPED [ 35%]
test/combina_test.py::CombinaTestSingleInputMILP::test_check_objective SKIPPED [ 42%]
test/input_test.py::InputTest::test_manual_extend_sos1_fulfilled PASSED  [ 50%]
test/input_test.py::InputTest::test_manual_scale_sos1_fulfilled PASSED   [ 57%]
test/input_test.py::InputTest::test_multiple_controls_sos1_fulfilled_manual PASSED [ 64%]
test/input_test.py::InputTest::test_multiple_controls_sos1_violated PASSED [ 71%]
test/input_test.py::InputTest::test_single_control_T_not_increasing PASSED [ 78%]
test/input_test.py::InputTest::test_single_control_b_rel_not_relaxed_binary_solution PASSED [ 85%]
test/input_test.py::InputTest::test_single_control_invalid_dimensions PASSED [ 92%]
test/input_test.py::InputTest::test_single_control_sos1_violated PASSED  [100%]

=================================== FAILURES ===================================
_____________ CombinaTestSingleInputBnB.test_check_binary_solution _____________

self = <test.combina_test.CombinaTestSingleInputBnB testMethod=test_check_binary_solution>

    def test_check_binary_solution(self):
    
        b_bin = self.binapprox.b_bin
>       assert_array_equal(np.squeeze(b_bin[0,:]), self.b_bin_check)

test/combina_test.py:141: 
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 

args = (<built-in function eq>, array([0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.,
       0., 0., 0.,...0., 0., 0., 0., 0., 0., 0.,
       0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.,
       0., 0.]))
kwds = {'err_msg': '', 'header': 'Arrays are not equal', 'strict': False, 'verbose': True}

    @wraps(func)
    def inner(*args, **kwds):
        with self._recreate_cm():
>           return func(*args, **kwds)
E           AssertionError: 
E           Arrays are not equal
E           
E           Mismatched elements: 4 / 359 (1.11%)
E           Max absolute difference: 1.
E           Max relative difference: 1.
E            x: array([0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.,
E                  0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.,
E                  0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.,...
E            y: array([0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.,
E                  0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.,
E                  0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.,...

/usr/lib/python3.11/contextlib.py:81: AssertionError
---------------------------- Captured stdout setup -----------------------------
Running Branch and Bound ... 

    Iteration   Upper bound    Branches     Runtime (s)    
 U        359   1.492254e+04          193   2.174400e-02
 U        686   1.492254e+04          113   3.404000e-02
 U       1092   1.491668e+04          113   5.070000e-02
 U       1335   1.490628e+04          217   6.454100e-02
 U       1681   1.466628e+04          217   7.791400e-02
 U       2026   1.442628e+04          215   9.027400e-02
 U       2368   1.418628e+04          213   1.015990e-01
 U       2707   1.394628e+04          211   1.135950e-01
 U       3043   1.370628e+04          209   1.265310e-01
 U       3376   1.346628e+04          207   1.378230e-01
    Iteration   Upper bound    Branches     Runtime (s)    
 U       3706   1.322628e+04          205   1.479860e-01
 U       4033   1.298628e+04          203   1.587170e-01
 U       4357   1.274628e+04          201   1.695000e-01
 U       4678   1.250628e+04          199   1.792410e-01
 U       4996   1.226628e+04          197   1.901060e-01
 U       5311   1.202628e+04          195   2.004120e-01
 U       5623   1.178628e+04          193   2.107990e-01
 U       5932   1.154628e+04          191   2.214780e-01
 U       6238   1.130628e+04          189   2.317100e-01
 U       6541   1.106628e+04          187   2.418450e-01
    Iteration   Upper bound    Branches     Runtime (s)    
 U       6841   1.082628e+04          185   2.521730e-01
 U       7138   1.058628e+04          183   2.613710e-01
 U       7432   1.034628e+04          181   2.720020e-01
 U       7723   1.010628e+04          179   2.816850e-01
 U       8011   9.866278e+03          177   2.906280e-01
 U       8296   9.626278e+03          175   3.002270e-01
 U       8578   9.386278e+03          173   3.086740e-01
 U       8857   9.146278e+03          171   3.184470e-01
 U       9133   8.906278e+03          169   3.287310e-01
 U       9406   8.666278e+03          167   3.371320e-01
    Iteration   Upper bound    Branches     Runtime (s)    
 U       9676   8.426278e+03          165   3.471150e-01
 U       9943   8.186278e+03          163   3.557620e-01
 U      10207   7.946278e+03          161   3.651910e-01
 U      10468   7.706278e+03          159   3.738520e-01
 U      10726   7.466278e+03          157   3.826940e-01
 U      10981   7.226278e+03          155   3.906110e-01
 U      11233   6.986278e+03          153   3.987310e-01
 U      11482   6.746278e+03          151   4.073570e-01
 U      11728   6.506278e+03          149   4.156230e-01
 U      11971   6.266278e+03          147   4.240400e-01
    Iteration   Upper bound    Branches     Runtime (s)    
 U      12211   6.026278e+03          145   4.329160e-01
 U      12448   5.786278e+03          143   4.424950e-01
 U      12682   5.546278e+03          141   4.510750e-01
 U      12913   5.306278e+03          139   4.601110e-01
 U      13141   5.066278e+03          137   4.677880e-01
 U      13366   4.826278e+03          135   4.779070e-01
 U      13588   4.586278e+03          133   4.875270e-01
 U      13807   4.346278e+03          131   4.957500e-01
 U      14023   4.286637e+03          129   5.037530e-01
 U      15852   4.106278e+03          136   5.732390e-01
    Iteration   Upper bound    Branches     Runtime (s)    
 U      17578   3.960137e+03          177   6.420570e-01
 U      19330   3.720137e+03          179   7.137420e-01
 U      20906   3.480137e+03          181   7.721740e-01
 U      22401   3.240137e+03          181   8.301330e-01
 U      23835   3.000137e+03          178   8.876220e-01
 U      25101   2.760137e+03          176   9.337170e-01
 U      26230   2.520137e+03          174   9.740980e-01
 U      27186   2.280137e+03          174   1.005934e+00
 U      27874   2.040137e+03          182   1.028818e+00
 U      45928   2.038044e+03          186   1.673825e+00
    Iteration   Upper bound    Branches     Runtime (s)    
 U      51400   1.988518e+03          187   1.870376e+00
 U      57075   1.938991e+03          186   2.104009e+00
 U      62048   1.889460e+03          184   2.309029e+00
 U      67361   1.850574e+03          175   2.498778e+00
 U      67529   1.831332e+03          175   2.506058e+00
 U      87803   1.805342e+03          181   3.247767e+00
 U      94015   1.725159e+03          181   3.495085e+00
 U      98200   1.644977e+03          180   3.655375e+00
 U     103439   1.643323e+03          169   3.846041e+00
 U     114933   1.643323e+03          166   4.256921e+00
    Iteration   Upper bound    Branches     Runtime (s)    
 U     116162   1.603330e+03          176   4.300309e+00
 U     123397   1.603330e+03          177   4.574120e+00
 U     154495   1.603330e+03          183   5.718500e+00

    Optimal solution found

    Best solution:    1.603330e+03
    Total iterations:       972202
    Total runtime:    4.043268e+01 s


=========================== short test summary info ============================
SKIPPED [3] venv/lib/python3.11/site-packages/_pytest/unittest.py:371: CombinaMILP not available, skipping tests.
FAILED test/combina_test.py::CombinaTestSingleInputBnB::test_check_binary_solution
=================== 1 failed, 10 passed, 3 skipped in 52.06s ===================

Expected output

The following output was collected on the host machine with pytest -s -vvv .:

============================================== test session starts ==============================================
platform linux -- Python 3.11.6, pytest-7.4.3, pluggy-1.3.0 -- [REDACTED]/pycombina/venv/bin/python
cachedir: .pytest_cache
rootdir: [REDACTED]/pycombina
configfile: pyproject.toml
collecting ... - gurobipy version > 8.0.0 not found, CombinaMILP disabled.

collected 14 items                                                                                              

test/combina_test.py::CombinaTestSingleInputBnB::test_check_binary_solution Running Branch and Bound ... 

    Iteration   Upper bound    Branches     Runtime (s)    
 U        359   1.492254e+04          193   8.659000e-03
 U        686   1.492254e+04          113   1.504800e-02
 U       1092   1.491668e+04          113   2.321100e-02
 U       1335   1.490628e+04          217   2.919900e-02
 U       1681   1.466628e+04          217   3.544900e-02
 U       2026   1.442628e+04          215   4.165600e-02
 U       2368   1.418628e+04          213   4.783100e-02
 U       2707   1.394628e+04          211   5.282100e-02
 U       3043   1.370628e+04          209   5.855300e-02
 U       3376   1.346628e+04          207   6.384500e-02
    Iteration   Upper bound    Branches     Runtime (s)    
 U       3706   1.322628e+04          205   6.954500e-02
 U       4033   1.298628e+04          203   7.339800e-02
 U       4357   1.274628e+04          201   7.408000e-02
 U       4678   1.250628e+04          199   7.463300e-02
 U       4996   1.226628e+04          197   7.532400e-02
 U       5311   1.202628e+04          195   7.609100e-02
 U       5623   1.178628e+04          193   7.702400e-02
 U       5932   1.154628e+04          191   7.770700e-02
 U       6238   1.130628e+04          189   7.833100e-02
 U       6541   1.106628e+04          187   7.878200e-02
    Iteration   Upper bound    Branches     Runtime (s)    
 U       6841   1.082628e+04          185   7.916500e-02
 U       7138   1.058628e+04          183   7.950800e-02
 U       7432   1.034628e+04          181   7.981100e-02
 U       7723   1.010628e+04          179   8.025100e-02
 U       8011   9.866278e+03          177   8.061600e-02
 U       8296   9.626278e+03          175   8.092300e-02
 U       8578   9.386278e+03          173   8.123700e-02
 U       8857   9.146278e+03          171   8.153900e-02
 U       9133   8.906278e+03          169   8.184000e-02
 U       9406   8.666278e+03          167   8.214900e-02
    Iteration   Upper bound    Branches     Runtime (s)    
 U       9676   8.426278e+03          165   8.244900e-02
 U       9943   8.186278e+03          163   8.275000e-02
 U      10207   7.946278e+03          161   8.305800e-02
 U      10468   7.706278e+03          159   8.334100e-02
 U      10726   7.466278e+03          157   8.362000e-02
 U      10981   7.226278e+03          155   8.389900e-02
 U      11233   6.986278e+03          153   8.418300e-02
 U      11482   6.746278e+03          151   8.444700e-02
 U      11728   6.506278e+03          149   8.470900e-02
 U      11971   6.266278e+03          147   8.498200e-02
    Iteration   Upper bound    Branches     Runtime (s)    
 U      12211   6.026278e+03          145   8.525300e-02
 U      12448   5.786278e+03          143   8.555400e-02
 U      12682   5.546278e+03          141   8.592300e-02
 U      12913   5.306278e+03          139   8.620100e-02
 U      13141   5.066278e+03          137   8.645400e-02
 U      13366   4.826278e+03          135   8.671500e-02
 U      13588   4.586278e+03          133   8.700200e-02
 U      13807   4.346278e+03          131   8.726500e-02
 U      14023   4.286637e+03          129   8.752100e-02
 U      15852   4.106278e+03          136   8.938200e-02
    Iteration   Upper bound    Branches     Runtime (s)    
 U      17578   3.960137e+03          177   9.116600e-02
 U      19330   3.720137e+03          179   9.328900e-02
 U      20906   3.480137e+03          181   9.540100e-02
 U      22401   3.240137e+03          181   9.703000e-02
 U      23835   3.000137e+03          178   9.850400e-02
 U      25101   2.760137e+03          176   9.978900e-02
 U      26230   2.520137e+03          174   1.009040e-01
 U      27186   2.280137e+03          174   1.018510e-01
 U      27874   2.040137e+03          182   1.025610e-01
 U      45928   2.038044e+03          186   1.233910e-01
    Iteration   Upper bound    Branches     Runtime (s)    
 U      51400   1.988518e+03          187   1.303660e-01
 U      57075   1.938991e+03          186   1.364580e-01
 U      62048   1.889460e+03          184   1.438050e-01
 U      67361   1.850574e+03          175   1.497500e-01
 U      67529   1.831332e+03          175   1.500290e-01
 U      87803   1.805342e+03          181   1.750400e-01
 U      94015   1.725159e+03          181   1.840320e-01
 U      98200   1.644977e+03          180   1.885830e-01
 U     103439   1.643323e+03          169   1.948660e-01
 U     115999   1.603330e+03          176   2.091900e-01
    Iteration   Upper bound    Branches     Runtime (s)    
 U     154293   1.603330e+03          183   2.556200e-01
 U     180267   1.603330e+03          181   2.856690e-01

    Optimal solution found

    Best solution:    1.603330e+03
    Total iterations:       972039
    Total runtime:    1.157639e+00 s


PASSED
test/combina_test.py::CombinaTestSingleInputBnB::test_check_n_max_switches PASSED
test/combina_test.py::CombinaTestSingleInputBnB::test_check_objective PASSED
test/combina_test.py::CombinaTestSingleInputMILP::test_check_binary_solution SKIPPED (CombinaMILP not
available, skipping tests.)
test/combina_test.py::CombinaTestSingleInputMILP::test_check_n_max_switches SKIPPED (CombinaMILP not
available, skipping tests.)
test/combina_test.py::CombinaTestSingleInputMILP::test_check_objective SKIPPED (CombinaMILP not
available, skipping tests.)
test/input_test.py::InputTest::test_manual_extend_sos1_fulfilled PASSED
test/input_test.py::InputTest::test_manual_scale_sos1_fulfilled PASSED
test/input_test.py::InputTest::test_multiple_controls_sos1_fulfilled_manual PASSED
test/input_test.py::InputTest::test_multiple_controls_sos1_violated PASSED
test/input_test.py::InputTest::test_single_control_T_not_increasing PASSED
test/input_test.py::InputTest::test_single_control_b_rel_not_relaxed_binary_solution PASSED
test/input_test.py::InputTest::test_single_control_invalid_dimensions PASSED
test/input_test.py::InputTest::test_single_control_sos1_violated PASSED

============================================ short test summary info ============================================
SKIPPED [3] venv/lib/python3.11/site-packages/_pytest/unittest.py:371: CombinaMILP not available, skipping tests.
========================================= 11 passed, 3 skipped in 1.38s =========================================

As we can see, both solutions have the same objective value up to the sixth decimal.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions