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's gravatar image

VictorSMiller
343215
accept rate: 0%


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 :-)

link

answered 02 Mar '14, 15:43

Bo%20Jensen's gravatar image

Bo Jensen ♦
5.0k2919
accept rate: 14%

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.

link

answered 03 Mar '14, 01:22

Stefano%20Gualandi's gravatar image

Stefano Gual...
32113
accept rate: 0%

Dear Victor, you are right, "the sparser the better" is kind of inaccurate, but often not far from reality.

In general, there are plenty of papers on what is referred in general as "reformulation", in which you can include: scaling, change of variables, addition of variables/constraints and so on. It is well know in practice that changing the formulation can greatly affect the performance of a solver.

In your case, I guess you work on the constraints keeping the same variables. I would say that

  1. A sparser formulation might help to speed up the solution of the continuous relaxation of your problem. For instance the complexity of an interior-point methods depends on the "size" of the problem, somehow the number of coefficients needed to describe it. A sparser formulation is often actually smaller.This is something you can easily check by yourself.

  2. You have done part of the CPLEX job!

  3. The impact of rearranging and/or reformulating constraints in IP problems might lead to unpredictable behaviors by the solver: preprocessing and branching rules are often based on heuristics that might be affected by the formulation itself... there are example of problems in which the inclusion of a redundant constraints can substantially change CPLEX behavior. Notwithstanding difference in cut generation...

  4. Assuming you keep the same number of variables, sparser constraints might help in fix some variables implicitly. For instance x1+x2+x3=1 will automatically fix x1=1 if x2,x3=0.

So I would say that as a rule of thumb in LP yes, the sparser the better. In IP things are much blurred...in fact you move from "easy" problems to harder ones.

link

answered 02 Mar '14, 16:56

DeletedUser's gravatar image

DeletedUser
(suspended)
accept rate: 0%

Your third point is interesting in that you mention that adding redundant constraints may really help the problem solution. As you might suspect, the problem is a rendition of a very combinatorial problem, and the system of equations that I generate comes from making some arbitrary choices, but I can prove that any other set of such choices yields a system that is linearly equivalent to the first. I had not thought of including redundant constraints, but that is something I should experiment with.

(03 Mar '14, 12:25) VictorSMiller
1

@VictorSMiller The issue raised with redundant constraints is an example of how the optimizer might take different paths just by "randomness" i.e adding redundant constraints is not an algorithmic technique. If you want to know if the problem at hand has a high "luck" effect, then you should instead try to feed CPLEX different random seeds (some parameter in there).

(03 Mar '14, 13:58) Bo Jensen ♦

@Bo Jensen, At your suggestion I tried the experiment of running the same problem with cplex with all of the same parameters but a different random seeds. The variance is quite large times betwee 25 seconds and 300 seconds. It would be nice if it were a little more predictable.

(03 Mar '14, 17:14) VictorSMiller

@VictorSMiller Yes, but it's not always possible to get, the key is to find what is the triggering factor. Sometimes it's not possible to figure out entirely, so you have to live with the it. I know cplex has a strategy to run the root in separate threads and pick the "best", which should reduce the issue, try to see if that feature can be tuned for your problem.

(03 Mar '14, 17:20) Bo Jensen ♦

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.

link

answered 04 Mar '14, 01:42

jfpuget's gravatar image

jfpuget
2.5k310
accept rate: 8%

Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • 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

Asked: 02 Mar '14, 15:18

Seen: 1,107 times

Last updated: 04 Mar '14, 01:42

OR-Exchange! Your site for questions, answers, and announcements about operations research.