Date: 1 May 1995 14:59:24 GMT
From: pchu@ms.ic.ac.uk (Mr P.C. Chu)
Subject: New Paper Availble-- A Genetic Algorithm for the Set Partitioning
Problem
We announce the availability of a new paper. A key feature of this paper is a new
approach for solving constrained problems using genetic algorithms.
A Genetic Algorithm for the Set Partitioning Problem
P.C.Chu and J.E. Beasley
The Management School Imperial College London SW7 2AZ, England
April 1995
Abstract
In this paper we present a genetic algorithm-based heuristic for solving the set partitioning problem. The set partitioning problem is an important combinatorial optimisation problem used by many airlines as a mathematical model for flight crew scheduling. We develop a steady-state genetic algorithm in conjunction with a specialised heuristic feasibility operator for solving the set partitioning problem. Some basic genetic algorithm components, such as fitness definition, parent selection and population replacement are modified. The performance of our algorithm is evaluated on a large set of real-world set partitioning problems provided by the airline industry. Computational results show that the genetic algorithm-based heuristic is capable of producing high-quality solutions. In addition a number of the ideas presented (separate fitness, unfitness scores and subgroup population replacement) are applicable to any genetic algorithm for constrained problems.
Keywords: combinatorial optimisation; crew scheduling; genetic algorithms; set partitioning.
This paper (in postscript version) can be obtained by sending an e-mail request to: p.chu@ic.ac.uk
or it can be downloaded from the Web site:
http://mscmga.ms.ic.ac.uk/pchu/pchu.html
--
Paul Chu
The Management School
Imperial College of Science, Technology and Medicine London, United Kingdom SW7
2AZ
--
+-------------------------------------------------------+
| Paul Chu
| WWW: http://mscmga.ms.ic.ac.uk/pchu/pchu.html |
| PhD Student, Operations Research Group |
Date: Tue, 11 Apr 1995 12:48 MET
From: M.Voorneveld@kub.nl (VOORNEVELD M.)
Subject: Enumerating the partitions of a set
I haven't given it much thought, but the tric seems to be as follows: you know
the
number of subsets of a given set; take any subset, consider its complement; once
again,
you know how many subsets this set has; this will give you some kind of
recursion.
Make sure not to double-count partitions, for instance by showing that it
suffices to
actually start with 1 particular element and use the above argument on this
singleton set,
which after each iteration you extend with an element of the complement. Hope
this
makes things clearer, rather than worse!
Mark Voorneveld , M.Voorneveld@kub.nl
Date: Tue, 11 Apr 1995 07:48:12 -0600
From: umholme0@ccu.umanitoba.ca (Douglas Holmes)
Subject: Enumerating the partitions of a set
My old text references the following: Erlich, G. "Loopless Algorithms for
Generating
Permutations, Combinations, and Other Combinatorial Configurations,", J. ACM,
3(1973),
500-513
Date: 11 Apr 1995 12:36:05 GMT
From: takriti@engin.umich.edu (samer Takriti)
Subject: Enumerating the partitions of a set
Usually, I use depth-first search to do that. I do not know what you mean exactly
by
efficient since you are enumerating all possible partitions.
-Samer
Date: 14 Apr 1995 14:38:24 GMT
From: rubin@msu.edu (Paul A. Rubin)
Subject: Enumerating the partitions of a set
Here's an easy (?) approach. I'll assume the set to be partitioned is {1,...,N},
and I'll
use two integer vectors of dimension N: set[i] will be the index of the subset
in the
partition containing element i, and used[i] will be the number of subsets used to
contain
the first i elements. To avoid redundancy, I'll adopt the convention that
subsets are
numbered according to the smallest element in them, so that element 1 always
belongs
to subset 1, element 2 must belong to either subset 1 or subset 2, etc. At any
stage,
used[N] will be the total number of subsets in the current partition, and the
chore of
converting set[] to the desired format (e.g., a list of lists) is left to the
reader as an
exercise.
The actual algorithmic part is simple. Initialize both set[] and used[] to
contain all unit
(1) entries, corresponding to the trivial partition {{1,...,N}}. To get the next
partition,
use the following logic:
With my indexing convention for the subsets, as we truck through set[] from front to back, either entry j goes into a subset already in use (so used[j] = used[j-1]) or starts a new subset (so set[j] = used[j-1]+1 = used[j]).
Given N, there's nothing you can do about the number of partitions you'll
generate (the
Stirling numbers provide the bad news there). Unless I'm missing something, the
time
spent per partition in this method is linear in N. I don't know if you'll be
able to do
any better than that.
I've tested this for N=3, 4, 5 and it seems to work as advertised.
Paul A. Rubin, Department of Management, Eli Broad Graduate School of Management , Michigan State University, East Lansing, MI 48824-1122 (USA), Phone: (517) 432-3509 , Fax: (517) 432-1111, Net: RUBIN@MSU.EDU
Date: Fri, 14 Apr 1995 17:19:33 GMT
From: tomi@wri.com (Tom Issaevitch)
Subject: Enumerating the partitions of a set Here is a recursive Mathematica
program
that will do it.
rep[x_, d_]:= Map[ReplacePart[ x, Append[x[[#]],d], #]&, Range[Length[x]]]
addOne[ old_, ad_ ]:=
Union[ Map[ Join[{ad}, #]&, old ], Flatten[Map[ rep[#, ad[[1]]]&, old ], 1 ]
]
totpart[ list_ ]:=
With[ {init = {{{list[[1]]}}}, rest = Transpose[{Rest[list]}]},
Fold[ addOne, init, rest ]]
To give a sense of the sizes and times involved, here are the times and lengths for sets of size 7 through 10. Beyond this and memory becomes a problem, so this may not be efficient memory-wise (though you can continue by building up the answer in steps--- see below). However, the time is linear with the size of the answer.
In[17]:= Length[totpart[{a,b,c,e,f,g,h}]]//Timing
Out[17]= {0.683333 Second, 877}
In[18]:= Length[totpart[{a,b,c,e,f,g,h,i}]]//Timing
Out[18]= {3.23333 Second, 4140}
In[19]:= Length[totpart[{a,b,c,e,f,g,h,i,j}]]//Timing
Out[19]= {16.8667 Second, 21147}
In[20]:= Length[totpart[{a,b,c,e,f,g,h,i,j,k}]]//Timing
Out[20]= {95.4167 Second, 115975}
This is on a powermac 6100. As noted above, beyond 10, I run out of memory but you can get partions of (n+1) elements by acting piecewise on a partition of the set of partitions of length n. For example, here is how to build the partitions of four elements from a splitting of the partitions of three elements using addOne:
In[33]:= t1 = totpart[{a,b,c}] (* partitions of three elements *)
Out[33]= {{{a, b, c}}, {{b}, {a, c}}, {{c}, {a, b}}, {{b, c}, {a}},
{{c}, {b}, {a}}}
In[36]:= t2 = Take[t1,3]; t3 = Complement[t1,t2]; (* t1 = Union[t2, t3] *)
In[44]:= t4 = addOne[t2, {d}]
Out[44]= {{{a, b, c, d}}, {{b}, {a, c, d}}, {{c}, {a, b, d}}, {{d}, {a, b, c}},
{{b, d}, {a, c}}, {{c, d}, {a, b}}, {{d}, {b}, {a, c}}, {{d}, {c}, {a, b}}}
In[45]:= t5 = addOne[t3, {d}]
Out[45]= {{{b, c}, {a, d}}, {{b, c, d}, {a}}, {{c}, {b}, {a, d}},
{{c},{b, d}, {a}}, {{d}, {b, c}, {a}}, {{c, d}, {b}, {a}}, {{d}, {c}, {b},
{a}}}Br>
In[47]:= Complement[totpart[{a,b,c,d}], Join[t4,t5]]
Out[47]= {}
Hope this helps, Tom, Wolfram Research
SCI.OP-RESEARCH Digest Mon, 24 Apr 95 Volume 2: Issue
17
Date: 18 Apr 1995 22:22:17 GMT
From: rubin@msu.edu (Paul A. Rubin)
Subject: Enumerating the partitions of a set
In article <23191.larso171@maroon.tc.umn.edu>,
"James Albert Larson" < larso171@maroon.tc.umn.edu > wrote:
-> Tom,
->
-> Is there a list of Operations Research / optimization algorithms
available
-> for Mathematica? Built into MMA are linear programming, and
unconstrained
-> nonlinear optimization of continous functions that hill climb to the
->nearest local optimal answer. I did some keyword searches on my
Mathsource
-> CDROM, and found not much, though I use MixedIntegerLinearProgramming.m
-> Is there any work towards an optimization toolbox for MMA?
I'm not Tom, but I play him on a network. I've seen similar queries on
sci.math.symbolic (and will probably see them again on comp.soft
sys.math.mathematica). Adding to what the real Tom (accept no cheap
substitutes!) has posted elsewhere, there's a chap in France who has put together
a notebook that does some continuous optimization. I hesitate to post his name,
lest he be deluged by (two or more) requests, but if you e-mail me I can pass
along his address. Also, I have a small package implementing penalty functions.
It would be in alpha test (equivalent to a 1.0 version from a certain nameless
software conglomerate) if I were actively testing it. You're welcome to a peek
if it's something you would find useful, but be warned it lacks almost all bells
and whistles.
Paul Rubin
Date: Sun, 23 Apr 1995 06:56:33 GMT
From: "James Albert Larson" < larso171@maroon.tc.umn.edu>
Subject: Enumerating the partitions of a set
To: rubin@msu.edu
>put together a notebook that does some continuous optimization.
> Also, I have a small package implementing penalty functions.
Thanks very much, but the nonlinear continuous optimization stuff is over
my head. I am mostly focussed on discrete optimization, combinatorial
explosion, and mixed integer linear programming. My research involves the
electric utility unit commitment problem, which is plagued by 2^(NU*NH)
combinations of on/off states of units, where NU = number of generating
units (say 20 or more), and NH is number of hours (24..120).
I am familiar with dynamic programming and lagrangian relaxation, and mixed
integer linear programming. But that's about all.
Jim
SCI.OP-RESEARCH Digest Mon, 10 Jul 95 Volume 2: Issue
28
Date: Mon, 3 Jul 1995 16:43:21 GMT
From: John Chionglo
Subject: Request for pointers to articles and/or software on the set
partitioning problem
Hello.
--
John Chionglo, P.Eng.
Date: 5 Jul 1995 12:34:54 GMT
A paper on GA for the spp is available at
Date: Wed, 10 Apr 1996 01:53:38 -0400
I have the following question and would appreciate any help.
QUESTION: We have a set S = \{1,...,n\} and a collection of subsets
of S, C = \{ A(1), A(2), ..., A(m) \}. Each A(i) is a subset of S.
We want to choose a subcollection Q of C, such that the quantity
(number of sets in Q)x(cardinality of the intersection os all sets in Q)
is maximized.
I would like to know is the above problem is NP-complete ? If not,
any suggestions for an algorithm.
Thanks a lot,
Date: Sat, 13 Apr 1996 15:11:19 GMT
I'm looking for information on solving a gerrymandering problem.
The problem: Given a set of counties, I want to create a set of districts such that
Any pointers as to how to solve this problem will be appreciated.
Thanks,
Date: Sat, 13 Apr 1996 08:46:49 -0700
To get the discussion going: would this work?
Solve the problem as Set Partitioning, the elements being the counties
(each should be in exactly one district), and the sets being the
districts.
This would require a 'district generator' where you could create a large collection of districts/sets. You would allow only neighboring counties in a district, and limit this creation process by setting upper and lower limits on population and acreage of the districts being built up.
As Set Partitioning algorithms can handle many thousands of sets, you
may be able to enumerate ALL possible districts if your number of
counties is low.
The trickiest point is how to set the cost of each district, which would
need to be something like a weighted combination of the deviations of
population and acreage from some average.
Do you know how many districts you want in the end? If so, this is
(probably) automatically handled by using the above mentioned average (which is, of course, a total divided by this target number of
districts).
RJ
Come to think of it: isn't there a 'Political districting' article from
many years ago. Wasn't George Nemhauser one of the authors? Anyone?
Roy Jonker
Date: Sat, 13 Apr 1996 09:15:03 -0700
(Sorry for this multi-stage response).
An approach that may well be preferable over something relatively
complex as Set Partitioning is to use Tabu Search.
Write a routine that gives you an initial set of districts. Introduce
two Tabu Search moves: (1) shifting a county from one district into
an other one, and (2) exchanging two counties between districts.
As Tabu Search allows a very flexible move evaluation, you can build all sorts of rules into that evaluation to handle the double-objective
aspect of your problem.
Roy Jonker @ MagicLogic Optimization Inc.
Date: 13 Apr 1996 23:52:32 -0600
Garfinkel, R.S. and G.L. Nemhauser (1970). "Optimal Political
Districting by Implicit Enumeration Techniques", Management
Science, vol. 16, pp. 495-508.
Hess, S.W.; Weaver, J.B.; Siegfeldt, H.J.; Whelan, J.N. and
P.A. Zitlau (1965). "Nonpartisan Political Redistricting by
Computer", Operations Research, vol. 13, pp. 998-1008.
Regards,
Keith A. Willoughby
Date: Wed, 17 Apr 1996 17:35:10 -0600
I am interested in a version where we do not have this restriction. Are
there any (nice) computational geometry techniques that one can apply in this case?
Also, what is the constraint (wrt the counties) in the original problem?
i.e., can they be split?
-Raghu-
Date: Thu, 18 Apr 1996 09:07:01 -0400
Mike Trick
Date: Mon, 06 May 1996 02:09:44 GMT
Date: 30 Apr 1996 14:57:54 GMT
Given:
RJ
Date: Thu, 9 May 1996 12:24:53 -0400
It was by Anuj Mehrotra, U of Miami, Dept of MS, Sch of Bus Adm, 417K Jenkins Bldg, Coral Gables, FL 33124-8237, with Johnson and Nemhauser.
For more info:
http://www.bus.miami.edu/~amehrotr/research.html
http://www.bus.miami.edu/~amehrotr/districting
Abstract:
Redistricting, the redrawing of congressional
district boundaries within the states, may
occur every 10 years on the basis of the population census.
Many redistricting plans are designed with
partisan politics in mind resulting in disputes and forcing
judges to intervene.
We address this problem from a nonpolitical viewpoint and
present a method for districting that is based on
desirable characteristics that are universally agreed upon. We
model the problem as a constrained graph partitioning problem
and develop a specialized branch-and-price based solution
methodology. We demonstrate the feasibility of our methodology
by showing how to satisfy the one-person, one-vote principle
with compact and contiguous districts for the states
of North Carolina and South Carolina.
Date: 13 Sep 1996 10:17:03 GMT
Hi,
I am looking for an exact algorithm for the maximum cardinality independent
(stable) set problem.
Thanks in advance.
Date: 14 Sep 96 05:11:22 GMT
Enumerate all possible subsets of the vertex set. Throw out those that are
not stable, and choose the largest.
Implement this process by a back-tracking algorithm to eliminate trivially
redundant work.
Let me know if you find anything significantly better.. :-)
Cheers
gordon
Date: 16 Sep 1996 10:24:57 -0400
Crawl back to front page.
I am looking for special purpose algorithms and/or software implementations
for solving the set partitioning problem. Thanks.
Research Assistant
University of Toronto
email: chionglo@ie.utoronto.ca
WWW: http://www.ie.utoronto.ca/EIL/profiles/chionpro.html
------------------------------
From: jeb1@ic.ac.uk (Dr J.E. Beasley)
Subject: Request for pointers to articles and/or software on the set
partitioning problem
http://mscmga.ms.ic.ac.uk/jeb/jeb.html
From: Milind Dawande <md68+@andrew.cmu.edu>
Subject: A question
.
Hello,
-- Milind
From: sslash@rs6000.cmp.ilstu.edu (Susan 'WIP' Lash)
Subject: Gerrymandering
Susan
sslash@rs6000.cmp.ilstu.edu
From: Roy Jonker <roy_jonker@magiclogic.com>
Subject: Gerrymandering
Susan 'WIP' Lash wrote .....:
From: Roy Jonker <roy_jonker@magiclogic.com>
Subject: Gerrymandering
Susan 'WIP' Lash wrote ...:
From: Roy Jonker <roy_jonker@magiclogic.com>
Subject: Gerrymandering
Susan 'WIP' Lash wrote ...:
From: kwilloug@acs.ucalgary.ca (Keith Willoughby)
Subject: Gerrymandering
Try the following two articles:
Ph.D. Candidate
Operations Management
University of Calgary
Calgary, Alberta, Canada
From: raghava@uswest.com (S. Raghavan)
Subject: Gerrymandering
One possible method to tackle the problem was suggested by Roy Jonker (see below). However one assumption that he makes is that an entire county must be in a district.
From: Michael Trick <trick+@andrew.cmu.edu>
Subject: Gerrymandering
Anuj Mehrotra (http://www.bus.miami.edu/~amehrotr/) and George Nemhauser have a new paper on this, including issues of dividing counties, combinatorial (though not geometric) methods for compactness and so on.
From: jfw@radix.net (Jim Ward)
Subject: Gerrymandering
sslash@rs6000.cmp.ilstu.edu (Susan 'WIP' Lash) wrote .....:
From: teb07@cas.org (Tom Bangert)
Subject: Understanding Basic Set Partitioning Problems
I am trying to learn more about linear and integer programming. I have a specific problem that I trying to understand and this problem realtes to set partitioning. I am having difficulty understanding the notation.
From: Roy Jonker <roy_jonker@magiclogic.com>
Subject: Understanding Basic Set Partitioning Problems
The original question asked for an explanation of the Set Partitioning
problem.
From: Craig Schmidt <cs76+@andrew.cmu.edu>
Subject: Gerrymandering
sslash@rs6000.cmp.ilstu.edu (Susan 'WIP' Lash) wrote:..
From: zeb@math-appli-uco.fr (Laurent Péridy)
Subject: Independent set
From: gordon@cs.uwa.edu.au (Gordon Royle)
Subject: Independent set
From: jeckstei@rutcor.rutgers.edu (Jonathan Eckstein)
Subject: Independent set