[AMPL 24799] Nonlinear Complementary problem

Google Group Mirror
1

Hi everyone
I am working on a complementary problem with the following equations and constraints:

minimize obj: 0;

Constraints

s.t. linkflow_eq {i in 1…80}: LinkFlows[i] = sum{j in CumulativeLengthData[i-1]+1…CumulativeLengthData[i]} x[flatData[j]];

Calculating Costs

s.t. cost_eq {i in 1…Total_Num_Var}: cost[i] = sum{j in 1…76: MX[i,j] == 1} (LinkINFO[j,1](1+ LinkINFO[j,3](LinkFlows[j]/(LinkINFO[j,2]))^LinkINFO[j,4])) + sum{j in 77…80: MX[i,j] == 1} ((LinkFlows[j]/700) + ((MX[i,LengthDataSize+2]*Price[MX[i,LengthDataSize+6]]) / (gamma * Ruo)) + ((MX[i,LengthDataSize+2]) / (gamma * rate)))*60 ;

Complementary Constraint

s.t. con2{i in 1…Total_Num_Var}: x[i] >= 0 complements (cost[i] - Cstar[MX[i,LengthDataSize+1]]) >= 0;

Demand Constraint

s.t. ODMatrixL_eq{i in 1…576}: sum{j in 1…Total_Num_Var: MX[j,LengthDataSize+1] == i} x[j] = Demand_L[i];

If you look at the formulation of the cost, there is a Price vector variables. I expect that by changing the value of parameters such as price vector, I get two type of result: infeasible or solution found. But there are some result that the output of AMPL is the following message:

** EXIT - other error.

Major Iterations. . . . 46

Minor Iterations. . . . 41413

Restarts. . . . . . . . 3

Crash Iterations. . . . 17

Gradient Steps. . . . . 24

Function Evaluations. . 715

Gradient Evaluations. . 67

Basis Time. . . . . . . 309.366000

Total Time. . . . . . . 322.828000

Residual. . . . . . . . 1.078515e+04

Postsolved residual: 1.0785e+04

Path 5.0.05: Not enough progress.

63 iterations (17 for crash); 41413 pivots.

715 function, 67 gradient evaluations.

What is the reason for that? I would appreciate it if you could guide me.

2

For the example that you have given, the output from the PATH solver includes the following messages:

Postsolved residual: 1.0785e+04
Path 5.0.05: Not enough progress.

“Not enough progress” means that PATH stalled out at a non-solution point, when the step lengths at successive iterations became very close to zero. As a result, PATH could not solve the problem that you sent to it.

The “residual” is the amount of infeasibility at the point where PATH stopped. When path is successful in finding a solution, the residual value is very close to zero – for example, in a test on a different model that I ran, it was 3.125309e-11. The given residual value of 1.0785e+04 for your problem indicates that PATH’s solution was far from feasible when it stalled out.

The most likely cause of this behavior is that there is no feasible solution. If you know a good guess of the solution, however, you might try assigning it to the variables as a starting point, to see if then PATH converges to a feasible solution. You could also try the Knitro solver, which uses a different method for complementarity problems and might happen to give better results. In general, however, it is very hard to prove that a nonlinear complementarity problem has no feasible solution.

3

Our new solvers Gurobi, Xpress, Highs, Mosek, SCIP understand complementarity formulations and look for globally optimal solutions.

4

Thanks Robert for your reply. I would appreciate it if you let me know how I can assign a good guess to the variables as a starting point.

5

Initial guess:

let {i in 1…n} x[i] := x_val[i];

For MIP solvers (Gurobi, Highs, etc) a primal initial guess can be helpful, but they are “global”, i.e., given enough time, they should find an optimal / feasible solution if exists.

6

Any method for assigning values to AMPL parameters also works for assigning initial values to AMPL variables. That includes specifying values in a var statement, assigning values using a let statement, and reading values from an AMPL .dat file or any other kind of data file.

An example of using let has been given in the previous reply, and there are some examples of other ways in the discussion of Initial values of variables (page 398) in the AMPL book.