Effect of form of equations on IP solving

 3 1 I've been dealing with a family of hard 0/1 IP's all of which are of the form Ax = b (no inequalities except for variable bounds). When I give the problems to CPLEX in their original form it always reports that its been able to perform a number of coefficient reductions (though I don't know which ones. That would be interesting to find out). After looking at the form of the matrix A I noticed that it was possible to do a number of row operations on A (and doing the same operations to b) which would greatly increase the sparsity of A. Now when I give the modified equations to CPLEX it never reports any coefficient reductions, and, in general solves them about 25% to 50% faster. So this brings up the question -- is there are systematic research out there which is able to describe "better" forms of equations? I just went on general idea that sparser was better, but that still seems a bit vague. asked 02 Mar '14, 15:18 VictorSMiller 343●2●15 accept rate: 0%

 5 First of all, there are two ways to change or eliminate coefficients : Row (also column in some cases) operations Coefficient strengthening based on logic on integer variables I am not sure which CPLEX reports here, let me comment on the first type, since I assume that's the technique you used yourself. For LP there are known sparsity methods, which is fairly simple ideas based on gauss elimination. For LP the sparse model is likely to solve faster, but for MIP the picture is a bit more unclear. To give one simple example, assume you have two fixed cliques, a large and a smaller one. The smaller clique is either a full or a partial subset of the larger clique. This gives you an opportunity to eliminate non zeroes in the larger clique in several ways, but you may end up with a weaker clique. Counter examples can be given of course, it just highlight the fact that measuring MIP problem formulation strength in terms of size i.e cons,vars or non zeroes is not a good fit. Another surprising example of relation between size and solve time is that it's possible to reformulate a standard IP (with integer data) into one single row knapsack. Then the million \$ question is which one you prefer to solve :-) answered 02 Mar '14, 15:43 Bo Jensen ♦ 5.0k●2●9●19 accept rate: 14%
 4 While for LP sparse matrices are better, for IP is totally problem dependent. Since you asked for a systematic study, you can check this paper the will be presented to the next IPCO conference: How Good are Sparse Cutting Planes? In the paper there are 3 examples of 0-1 IPs: in a first example sparse matrices are better, in a second example they are really bad, for the third is unclear. The paper presents theoretical proofs, but I saw a presentation about that work with also computational results confirming the proofs. answered 03 Mar '14, 01:22 Stefano Gual... 321●1●3 accept rate: 0%
 3 You can find out which coefficient were reduced by saving the presolved model In cplex interactive, assuming your original model is called mod.lp, you could do read mod.lp write mod.pre read mod.pre write mod.pre.lp  then mod.pre.lp contains the presolved model. Regarding running times, you should look at the log file. Are the problems solved faster after your transformation because there are fewer nodes, or because nodes are processed more rapidly? The latter would probably mean that you win because the LP relaxations are faster to compute on a sparser matrix. If the former, then it is due to more convoluted interactions of CPLEX algorithms. Anyway, it is often the case that two equivalent mathematical models can lead to significant running times. It is our job (as well as other solver developers) to find ways of reformulating models into equivalent models that are faster to solve. You probably found such reformulations. It may be worth publishing these. answered 04 Mar '14, 01:42 jfpuget 2.5k●3●10 accept rate: 8%
 toggle preview community wiki

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "Title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported

Tags:

×191
×71