Generating block file for MILPBlock application using Python in DIP

MILPBlock is a prototype for a generic black-box solver for block-diagonal mixed integer linear programming problems that fully automates the branch-and-price-and-cut algorithm without additional user input. The user only needs to provide the mps file of the problem and the block file which indicates how many blocks in the model, which rows in each block etc.

Sometimes it is tedious to write the block file for the large scale problem. So we always expect to create the block file by the script language, which is easy and fast. Python is the right choice.

Here is an example showing the bin packing problem for using Python to create block file.

The objective function and the constraints are described using AMPL language as below :

param numItems;
param Capacity;

set Items = 1 .. numItems;
set Bins  = 1 .. (numItems+1);

param Weight{Items};

var x{i in Items, j in Bins } binary ;

# minimize the number of bins

minimize num_Of_Bins : sum{i in Items} x[i,numItems+1];

subject to condition1 {i in Items}: sum{j in 1 .. numItems}x[i,j] = 1 ;

subject to condition2 {j in Items, i in Items}: x[i,j]<=x[j,numItems+1] ;

subject to condition3 {j in Items}: sum{i in Items}x[i,j]*Weight[i] <=Capacity*\
x[j,numItems+1];


Suppose we have 50 items, and 50 blocks, each block has 51 rows corresponding to j.

The python code to create a block file of the ' list ' format is shown below

*************************************************************************
f = open('test.block','w')
for i in range(50):
    f.write(str(i))
    f.write(' ')
    f.write(str(51))
    f.write('\n')
    for j in range(50):
    f.write(str(50+50*i+j))
    f.write(' ')
    f.write(str(2550+i))
    f.write('\n')

f.close()
*************************************************************************

/usr/bin/ld: cannot find -lusb?

I encountered this sort of problem when I was building bin packing project using DIP.  For example, if it says cannot find -lusb it means that it can not find the libusb.so(shared) or libusb.a(static) libraries.  Normally we need to add the LD_LIBRARY_PATH in the .bashrc file in the build-debug folder, ../configure and make , make install,  Then it should build it (hopefully)

SVN stuff for DIP project

svn co svn+ssh://jiw508@coral.ie.lehigh.edu/srv/svn/DECOMP/trunck/BPP   BPPupdate svn commit svn update  lock permission solve:  chmod -R g+w conf dav db hooks locks  sudo -i

DIP (Decomposition for Integer Programming) Framework

DIP (Decomposition for Integer Programming) is an open-source extensible software framework for implementing decomposition-based bounding algorithms for use in solving large-scale discrete optimization problems. The framework provides a simple API for experimenting with various decomposition-based algorithms, such as Dantzig-Wolfe decomposition, Lagrangian relaxation, and various cutting plane methods. Given a compact formulation and a relaxation, the framework takes care of all algorithmic details associated with implementing any of a wide range of decomposition-based algorithms, such as branch and cut, branch and price, branch and cut and price, subgradient-based Lagrangian relaxation, branch and relax and cut, and decompose and cut. 


https://projects.coin-or.org/Dip

It is quite beneficial to talk with Matt about DIP. I learnt a lot during our discussions. Thanks Matt.

Regarding the design of DIP. We need to treat master-only variables differently, which I did not realize before.