Relative Position Indexing Approach - Differential Evolution: A Topic for Global Permutation-Based Combinatorial Optimization - page 85

NMinimize::cvmit : Failed to converge to the
requested accuracy or precision within 1000 iterations.

{ 229 . 634 , {{ 0 ., { p → 22554 , n → 70469 , d → 24978 , q → 25266 }} ,

{

0 .,

{ →

4094 , n

→

79778 , d

→

42102 , q

→ }} ,

p 17293

{

0 .,

{ →

23139 , n

→

64874 , d

→

31502 , q

→ }} ,

p 23752

{

0 .,

{ →

26649 , n

→

72620 , d

→

15558 , q

→ }} ,

p 28440

{ 0 .,{ p → 2914 , n → 76502 , d → 48358 , q → 15493 }},

{ 0 .,{ p → 9714 , n → 49778 , d → 73110 , q → 10665 }},

{ 0 ., { p → 26019 , n → 26708 , d → 77782 , q → 12758 }} ,

{ 0 ., { p → 58229 , n → 31772 , d → 19494 , q → 33772 }} ,

{ 0 ., { p → 8609 , n → 70931 , d → 46674 , q → 17053 }} ,

{ 0 ., { p → 35049 , n → 55160 , d → 25398 , q → 27660 }}}}

We obtained valid solutions each time. Using only, say, 400 iterations we tend to get
solutions about half the time and “near” solutions the other half (wherein either the
number of coins and/or total value is off by a very small amount). Notice that this type
of problem is one of constraint satisfaction. An advantage to such problems is that we
can discern from the proposed solution whether it is valid; those are exactly the cases
for which we get an object value of zero, with all constraints satisfied.

4.3 Maximal Determinants

In this section we illustrate a heuristic methods on certain extremal matrix problems
of modest size. As motivation for looking at this particular problem, I remark that it is
sometimes important to understand extremal behavior of random polynomials or matri-
ces comprised of elements from a given set.
Below we apply knapsack-style optimization to study determinants of matrices of
integers with all elements lying in the set . The problem is to minimize the

determinant of such a matrix (since we can multiply any row by -1 and still satisfy the
constraints, the smallest negative value corresponds to the largest positive value). We
will make the simplifying assumption that all diagonal elements are 1. Strictly speaking
this is not combinatorial optimization, but it is a close relative, and will help to get the
reader acquainted with the programming commands we will be using in this chapter.
Thus is also a good example with which to begin this chapter.
Our objective function is simply the determinant. We want it only to evaluate when
the variables have been assigned numeric values. This is quite important because sym-
bolic determinants are quite slow to compute. So we set up the function so that it is only
defined when numeric values are plugged in.

{ -1,0,1 }

detfunc[ a : detfunc[ a : detfunc[ a : {{ {{ {{ ?NumberQ.. ?NumberQ.. ?NumberQ.. } } } .. .. .. } } } ]/;Length[ a ]==Length[First[ a ]]:=Det[ a ] ]/;Length[ a ]==Length[First[ a ]]:=Det[ a ] ]/;Length[ a ]==Length[First[ a ]]:=Det[ a ]

Our code will take a matrix dimension as argument, and also an optional argument
specifying whether to print the constraints. We use that in a small problem to show the