4
$\begingroup$

The problem being solved is finding the truss with the least weight, exactly done as on this website: https://www.layopt.com/truss/. This method is also called the ground structure method. I am aiming to add some functionallity to the method through an MILP optimization. Initially, I started with the cvxpy Linear Programming (LP) solver but since it can't solve MILP I am now using the IBM ILOG CPLEX solver with the python module docplex. Unfortunately I am bumping into an problem, but first in short how the optimization works is:

  • Initialize: Make nodes, place a load (f) and supports (dof)
  • Make the potential members of the truss, with full connectivity all the nodes will be connected with each other. These potential members will form the truss and every member has two variables a (area) and q (internal force) and a length l.
  • Calculate the nodal equilibrium matrix B, which is guaranteed sparce and symmetric.
  • Build the LP-model, which is done via calling the Model() object and start solving it.

The formulation is: \begin{array}{ll} \text{minimize} & V = l^T a \\ \text{subject to}& B q = f \\ & q \le \sigma a \\ & q \ge -\sigma a \\ & a \ge 0 \\ \end{array} In code:

"build the model"
model = Model()
a = model.continuous_var_list(len(members), name='a', lb=0, ub=1)
q = []
Bcons = []
for k, fk in enumerate(f):
    qk = model.continuous_var_list(len(members), name=f'q{k}', lb=-10 ** 10, ub=10 ** 10)
    Bconsk = model.add_constraints(
        sum(B[i, j] * qk[j] for j in range(len(qk))) == fk[i] for i in range(len(dof)) if dof[i] != 0)
    model.add_constraints(qk[i] <= sigma * a[i] for i in range(len(qk)))
    model.add_constraints(qk[i] >= -sigma * a[i] for i in range(len(qk)))
    q.append(qk)
    Bcons.append(Bconsk)
model.set_objective('min', sum(a[i] * l[i] for i in range(len(a))))  
model.print_information()

"solve model and update results"
sol = model.solve()
print(model.solve_details)

For small problem sizes (less than 1000 members) the LP converges in the CPLEX solver and works perfectly. However for larger problem sizes (e.g. more than 10 000 members) the problem is 'optimal with unscaled infeasibilities'. What does this mean and how can I solve this?

What I tried so far:

..

Results:
Nodes: 231 Members: 16290
Model: docplex_model1
 - number of variables: 32580
   - binary=0, integer=0, continuous=32580
 - number of constraints: 33038
   - linear=33038
 - parameters: defaults
 - objective: minimize
 - problem type is: LP
status  = optimal with unscaled infeasibilities
time    = 131.297 s.
problem = LP
Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

When you turn CPLEX loose on a model, it runs a presolver that does assorted magic tricks that end up with a modified model. It then solves the modified model and, assuming it finds a solution to the modified model, transforms that solution back to the original model. I believe that the "unscaled infeasibilities" message means that CPLEX found what it considered an optimal solution to the modified model, converted it to a solution to the original model, and discovered that the solution to the original model violated the constraint tolerance in one or more constraints.

One thing you can do is plug the CPLEX solution into your constraints yourself, evaluate them, and decide if they are satisfied to within an acceptable tolerance. Another possibility is to look at the range of coefficient sizes in the constraints. If you have any really large and/or really small (but nonzero) coefficients, or worse yet a mix of the two, you might have numerical difficulties (ill-conditioning). That's not the only source of ill-conditioning, but it is arguably the most common. A test of ill-conditioning is to look at the kappa value of the final basis matrix. If that's the case, you might ask yourself whether you can shrink some of the big coefficients or enlarge some of the small ones, perhaps by changing units in a consistent manner.

One more thing to try is to turn on CPLEX numerical emphasis parameter, which basically tells CPLEX that there are likely to be numerical adventures and that it should try extra hard to compensate.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks for the comment. In the example results the equilibrium matrix B is of size Nodes x Members = 3.7 milion, however only 65000 entries are nonzero. The range of the entries is between -1 and 1. The smallest absolute nonzero entry is 0.16, thus this matrix is not a basis for ill conditioning. $\endgroup$
    – Bart
    Sep 2, 2021 at 18:58
  • 1
    $\begingroup$ You may be right about the matrix not being ill-conditioned, but it's hard to be sure. A former IBMer told me once about an ill-conditioned matrix he'd encountered whose entries (if I recall correctly) were all 0, 1 and maybe -1. The issue could also have something to do with changes made during presolve (which can alter the constraint coefficients). At the risk of blowing up run time, you could try turning presolve off and see if that gets rid of the "unscaled infeasibilities". $\endgroup$
    – prubin ♦
    Sep 2, 2021 at 20:30
  • 1
    $\begingroup$ Yes, changing the scaling with mdl.parameters.read.scale = 1 lets the model also solve larger problems $\endgroup$
    – Bart
    Sep 8, 2021 at 9:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.