MINLP problem

[Henry Chan]

Hi, all,

I note that there is a mixed integer nonlinear programming (MINLP)
problem in the AMPL google groups.

The source program is as follows:

_________________________________________
var x0 integer >= 1 <= 10 ;
var y0 integer >= 1 <= 10 ;
var x1 >= 1 <= 10 ;
var y1 >= 1 <= 10 ;
var x2 >= 1 <= 10 ;
var y2 >= 1 <= 10 ;
maximize dist: (x0-x1)**2 + (y0-y1)**2 + (x0-x2)**2 +
(y0-y2)**2 + (x1-x2)**2 + (y1-y2)**2 ;
subject to
e01: (x0-x1)**2 + (y0-y1)**2 >= 12.5 ;
e10: (x0-x1)**2 + (y0-y1)**2 <= 64 ;
e02: (x0-x2)**2 + (y0-y2)**2 >= 12.5 ;
e20: (x0-x2)**2 + (y0-y2)**2 <= 64 ;
e12: (x1-x2)**2 + (y1-y2)**2 >= 12.5 ;
e21: (x1-x2)**2 + (y1-y2)**2 <= 64 ;
solve ;
display x0,y0,x1, y1 ,x2, y2 ;
_________________________________________

When I try to use the Active Set method, I obtain the following
result:

x0 = 1
y0 = 10
x1 = 1
y1 = 2
x2 = 7.9282
y2 = 6

For special testing, if I try to amend the source AMPL program by
specifying the x1 and x2 as integer variables, then I can not obtain
the good result as before because one of the integer variables is not
an integer solution.

Can anyone answer my question why this happens? Thanks in advance.

Regards,
Henry Kar Ming Chan

[Henry Chan]

Hi, all,

For another simple testing, if I try to amend the source AMPL program
by
specifying the x1 and y1 (but not x2 at this time) as integer
variables, then I still can not obtain the good result as before
because one of the integer variables is not an integer solution. As
you can note that x1 and y1 are the integer solutions from the
original AMPL program.

Can anyone answer why the solutions are so different? Thanks a lot.

Regards,
Henry Kar Ming Chan

[Henry Chan]

Hi, all,

I hope that I can find the actual MINLP problems of the AMPL programs
solved by KNITRO using Active Set method.

These may due to the searching directions and/or decomposition
strategies during the infeasibility/feasibility analysis stages.

The solution is wrong when I place the variables x0 and y0 in the
middle of variables description. (please note that I only declare x0
as an integer variable in this testing because I want to simplify the
case)
________________________________________________________

var x1 >= 1 <= 10 ;
var y1 >= 1 <= 10;

var x0 integer >= 1 <= 10;

var y0 >= 1 <= 10;

var x2 >= 1 <= 10 ;
var y2 >= 1 <= 10 ;

......
KNITRO 5.2.0: Locally optimal solution.
objective 192.0000042; feasibility error 1.85e-06
6 major iterations; 10 function evaluations
x0 = 8.40332

y0 = 10
x1 = 1

y1 = 6.96836
x2 = 7.32713
y2 = 2.07272
________________________________________________________

The solution is correct when I place the variables x0 and y0 on the
top of variables description.
________________________________________________________

var x0 integer >= 1 <= 10;

var y0 >= 1 <= 10;

var x1 >= 1 <= 10 ;
var y1 >= 1 <= 10;
var x2 >= 1 <= 10 ;
var y2 >= 1 <= 10 ;

.........
KNITRO 5.2.0: Locally optimal solution.
objective 192; feasibility error 1.44e-10
7 major iterations; 11 function evaluations
x0 = 6
y0 = 3.0718
x1 = 2
y1 = 10
x2 = 10
y2 = 10
__________________________________________________________

Hope that in the future release of Knitro software can provide better
options of searching directions and/or decomposition strategies during
the infeasibility/feasibility analysis stages

Thanks for your kind attention. Your comments are welcome.

Best regards,
Henry Kar Ming Chan

> > Henry Kar Ming Chan- Hide quoted text -
>
> - Show quoted text -

[Richard Waltz]

Henry,

The current version of KNITRO (version 5.2.0) does not yet handle
integer variables. When you feed it an Ampl model with integer
variables, it ignores the integrality constraint and solves the
continuous relaxation. The next major release of KNITRO due out end
of this year or early next year will have some capabilities for
handling integer variables and solving MINLP problems.

-Richard

[Henry Kar Ming Chan]

Dear Richard,

First of all, thanks for your information.

Actually, I have used the Knitro software version 5.2 with Active Set
method to solve a number of MINLP applications, I can normally find
the optimum solution. For the test cases, I use the MACMINLP but I can
still find the optimum solution. FYI.

Once again, thanks for your valuable information.

In addition, please also include this algorithm for Active Set method
as you mentioned in April 2008 for the future release of Knitro.
_____________________________________________________________

Topic: New Active-Set Algorithms for Large-Scale Nonlinear Optimization

Active-set algorithms offer a powerful approach for solving nonlinear
optimization problems. These methods have many advantages over the
more recently popular interior-point methods; most notably the ability
to converge quickly (i.e., "warm start") from an advanced initial
point. However, current active-set methods are unable to scale to
large problem sizes as effectively as interior-point methods, and this
significantly limits their applicability.

This talk will present new techniques for identifying which inequality
constraints are "active" (i.e., hold as equalities) at the solution of
nonlinear optimization problems. These techniques, based on solving
linear programming subproblems, allow the active-set estimate to
change by many constraints at once and overcome the bottlenecks of
traditional active-set methods. We also present advances in penalty
methods used to relax constraints in nonlinear optimization models.
These penalty methods are integrated with our new active-set
identification techniques to form a novel active-set algorithm that
outperforms traditional active-set methods on large-scale nonlinear
optimization problems.
_________________________________________________________________

Thanks for your kind help and attention in advance.

Best regards,
Henry Kar Ming Chan