drkwang / cutgeneratingfunctions_new

This is project for developping high-dimensional cut generating functions.

Description

This project mainly focuses on developing effecient data structures and algorithms, and implementing them in C++ and Python, for exploring new cut-generating functions in high-dimensional space. try

Introduction

The cut-generating function is a family of piecewise linear functions for increasing the speed of solving integer optimization. The information of integer optimization can be found in this book, and the details of cut-generating function can be found in this website.

In general, we are looking for the piecewise linear functions π(x) in high dimension, with satisfying the 4 following conditions:

1. π(0) = 0
2. π(x) + π(y) ≥ π(x + y) (Subadditivity)
3. π(x) + π(f − x) = 1 (Symmetry)
4. π(x) = π(x + k), for k in Z^d (periodicity)

Those functions in one dimension have been well developped, with using computer-based method. However, for high dimension, the main difficulty of exploring and verifying cut-generating functions comes from the verification of the subadditivity, which is a entire verification with heavy computation and hard to find out which subregions in the domain intersects with the minkowski sum for each pair of subregions. Notice that the minkowski sum of two specific subregions only has a local intersection with few subregions, instead of a total retriving. We may arrange rtree data structure as a cheapo index library to organize all subregions of the domain for [easily computing their minkowski sum] and [quickly retriving the intersected subregions]. After using rtree data structure, it could filter most non-intersected subregions and improve the computation significantly.

Apart from the above project in the piecewise linear functions, rtree data structure also has been used as a cheapo index library for preliminary filtering the non-containing element of a