Hexagon : Maximizing the Area of a Hexagon in Which the Diameter Must Be Less Than or Equal to One


  • Neculai Andrei, Nonlinear Optimization Applications Using the GAMS Technology,Springer Optimization and Its Applications, Model Hexagon (3.8) in chapter Some Mathematical Algorithms and Problems in GAMS Technology, 2013

Category : GAMS NOA library

Mainfile : hexagon.gms

The problem is to maximize the area of a hexagon in which the
diameter must be less than or equal to one.

In this formulation a vertex (the first one) is fixed at the origin and
the second one is on the x axis. The vector scalar products are used to
calculate the areas of all triangles originating from the origin.
Therefore, all terms in x(1), y(1) and y(2) vanish and the algebraic
expression of the problem is simplified.

Hock, W., Schittkowski, K., Test Examples for Nonlinear Programming Codes,
Lecture Notes in Economics and Mathematical Systems, vol. 187,
Springer Verlag, 1981. (Problem 108)

Gill, Ph.E., Murray, W., Saunders, M.A. and Wright, M., User's Guide for
SOL/NPSOL: A FORTRAN Package for Nonlinear Programming, Tech. Rep. 83-12,
Dept. of Operation Research, Stanford University.

Himmelblau, D.M., Applied Nonlinear Programming, McGraw-Hill, New York,
1972. Problem 16, pp.415.

Pearson, J.D., On variable metric methods of minimization. Research Analysis
Corp. Rept., RAC-TP-302, McLean, Va., May, 1968.

Graham, R.L., The largest small hexagon. Journal of Combinatorial Theory,
(A) 18, 1975, pp.165-170.

Set i indices for the 6 points /1*6/;

Alias (i,j);

Variable x(i)     x-coordinates of the points
         y(i)     y-coordinates of the points
         area(i)  area of the i'th triangle
         totarea  total area of the hexagon

Equations areadef(i)   area definition for triangle i
          maxdist(i,j) maximal distance between i and j
          areahexa     definition of objective;

areadef(i).. area(i) =e= 0.5*(x(i)*y(i+1)-y(i)*x(i+1)) ;

maxdist(i,j)$(ord(i) lt ord(j)).. sqr(x(i)-x(j))+sqr(y(i)-y(j)) =l= 1;

areahexa.. totarea =e= sum(i,area(i));

* initial conditions

x.fx("1") = 0;  y.fx("1") = 0;  y.fx("2") = 0;

x.l("2") = 0.5; x.l("3") = 0.5; x.l("4") = 0.5;
x.l("5") = 0;   x.l("6") = 0;
y.l("3") = 0.4; y.l("4") = 0.8; y.l("5") = 0.8;
y.l("6") = 0.4;

Model hexagon /all/;

$iftheni x%mode%==xbook
$onecho >bench.opt
  solvers conopt knitro minos snopt
option nlp=bench;

Solve hexagon using nlp maximizing totarea;

$iftheni x%mode%==xbook
file out /hexagon1.dat/
put out;
put x.l('1'):15:7,  y.l('1'):15:7 /;
put x.l('2'):15:7,  y.l('2'):15:7 /;
put x.l('3'):15:7,  y.l('3'):15:7 /;
put x.l('4'):15:7,  y.l('4'):15:7 /;
put x.l('5'):15:7,  y.l('5'):15:7 /;
put x.l('6'):15:7,  y.l('6'):15:7 /;
put totarea.l:15:7 /;

* End hexagon