scsd1, scsd6, scsd8; truss

The Application

Described in this short postscript file.

The Formulation

Described in this short postscript file.

The Problems

Just one AMPL model file serves for all four problems. In fact, we provide two models:

• struc.pl , corresponding to the natural piecewise linear formulation; and
• struc.mod , corresponding to the equivalent linear formulation which splits the variables into positive and negative parts.

If you use struc.pl and specify a linear programming solver, AMPL automatically converts your piecewise-linear program to a linear program, and converts the results back.

There is one AMPL data file for each problem, which can be used with either of the two models:

• scsd1.dat
• scsd6.dat
• scsd8.dat
• truss.dat

The following MPS files are for the equivalent linear formulation with the split variables:

• scsd1.mps
• scsd6.mps
• scsd8.mps
• truss.mps

In the MPS formulation, the sizes of the problems are:

• scsd1: 78 rows, 760 columns, 3148 nonzeros.
• scsd6: 148 rows, 1350 columns, 5666 nonzeros.
• scsd8: 398 rows, 3750 columns, 11334 nonzeros.
• truss: 1001 rows, 8806 columns, 36642 nonzeros.

For a little more information, see this short postscript file. You can download the shell archive of files that generated truss.mps by clicking here.

Results

The optimal objective function values as determined by CPLEX 3.0 are

• scsd1: .86666666743(+1)
• scsd6: .50500000078(+2)
• scsd8: .90499999993(+3)
• truss: .45881584719(+6)

Click on any entry above to see the complete list of primal and dual values obtained from the NEOS LP solver.

As a result of the way in which the variables are split into positive/negative pairs, the constraint matrix consists of pairs of columns that are the same except for sign. At most one of each pair can be in any simplex basis.

In the original piecewise-linear formulation of this problem, the variables are allowed to take any positive or negative values, and hence any basic solution to the constraints is feasible. It follows that, in the equivalent linear formulation, any basic solution is easily adjusted to be feasible. General-purpose primal simplex codes cannot take advantage of this property, however, and consequently tend to spend a lot of iterations in phase 1. See [1] for further explanation.

There is a considerable degree of primal degeneracy in these problems, corresponding to structures that are not rigid. The primal simplex method is observed to take many degenerate iterations as a result. A knowledge of the piecewise-linear structure can be used to reduce the number of degenerate iterations, as explained in [1].

Interior-point methods tend to do well on problems of this kind.

Further reading

1. Robert Fourer and Roy E. Marsten, Solving Piecewise-Linear Programs: Experiments with a Simplex Approach. ORSA Journal on Computing 4 (1992) 16--31.
2. James K. Ho, Optimal Design of Multi-Stage Structures:\ A Nested Decomposition Approach. Computers and Structures 5 (1975) 249--255.
3. Gilbert Strang, Introduction to Applied Mathematics Wellesley-Cambridge Press, Wellesley, MA (1986).

[ Previous problem | Netlib toplevel index | Next problem]

[ Optimization Software Guide | OTC Home Page | NEOS Server | NEOS Guide ]