A i icial In elligence 328 (2024) 104064
A ailable online 9 Janua y 2024
0004-3702/© 2024 The Au ho (s). Published by Else ie B.V. This is an open access a icle unde he CC BY-NC license
(h p://c ea i ecommons.o g/licenses/by-nc/4.0/).
Con en s lis s a ailable a ScienceDi ec
A ificial In elligence
jou nal homepage: www.else ie .com/loca e/a in
An a en ion model o he o ma ion o collec i es in eal-wo ld
domains
Ad ià Fenoyb,a, Filippo Bis affab,∗, Alessand o Fa inelli a
aUni e si y o Ve ona, I aly
bIIIA-CSIC, Spain
A R T I C L E I N F O A B S T R A C T
Keywo ds:
A en ion models
Rein o cemen lea ning
Collec i e o ma ion
Op imiza ion
We conside he p oblem o o ming collec i es o agen s inhe en in applica ion domains aligned
wi h Sus ainable De elopmen Goals 4 and 11 (i.e., eam o ma ion and idesha ing, espec i ely).
We p opose a gene al solu ion app oach based on a no el combina ion o an a en ion model and
an in ege linea p og am (ILP). In mo e de ail, we p opose an a en ion encode -decode model
ha ans o ms a collec i e o ma ion ins ance o a weigh ed se packing p oblem, which is hen
sol ed by an ILP. Resul s on collec i e o ma ion p oblems inhe en in he idesha ing and eam
o ma ion domains show ha ou app oach p o ides compa able solu ions (in e ms o quali y) o
he ones p oduced by s a e-o - he-a app oaches specific o each domain. Mo eo e , ou solu ion
ou pe o ms he mos ecen gene al app oach o o ming collec i es based on Mon e Ca lo ee
sea ch.
1. In oduc ion
In ecen yea s, mo e and mo e scena ios equi e Collec i e In elligence solu ions enabling no el ways o social p oduc ion, p o-
mo ing inno a ion, and encou aging he exchange o ideas [1]. Such new o ms o collabo a i e consump ion and p oduc ion pose
complex, mul i- ace ed challenges, bu hey ul ima ely all ely on a common and undamen al ask, i.e., he o ma ion o collec i es.
In his wo k, we conside wo eal-wo ld applica ion domains, i.e., idesha ing and eam o ma ion ( espec i ely aligned wi h UN
Sus ainable De elopmen Goals 11 and 4 [2]), whe e agen s comple e asks and achie e benefi s h ough he o ma ion o collec i es
o achie e coope a ion.
On he one hand, in idesha ing commu e s can o m g oups and a el oge he wi h he objec i e o educing anspo a ion
cos s, mi iga ing pollu an emissions, and alle ia ing affic conges ion in u ban en i onmen s [3,4]. Ano he p ominen example
can be ound in mode n educa ional ins i u ions ha aim a implemen ing coope a i e and ac i e lea ning echniques, which engage
s uden s in eams o pa icipa e in all lea ning ac i i ies in he class ooms. As ecen ly shown by And ejczuk e al. [5], collec i e
o ma ion app oaches can imp o e he o e all pe o mance o he s uden s by g ouping hem in eams ha maximize he syne gies
among membe s.
Due o he inhe en complexi y and specifici y o each applica ion domain, esea che s usually ackle he o ma ion o collec-
i es by designing e y specific sub-op imal app oaches ha can sol e he associa ed la ge-scale op imiza ion p oblem in a easible
un ime. Howe e , un o una ely, one domain-specific app oach usually canno be applied in a diffe en scena io.
* Co esponding au ho .
E-mail add ess: filippo.bis aff[email p o ec ed] (F. Bis affa).
h ps://doi.o g/10.1016/j.a in .2023.104064
Recei ed 22 June 2022; Recei ed in e ised o m 20 Decembe 2023; Accep ed 28 Decembe 2023
A i icial In elligence 328 (2024) 104064
2
A. Fenoy, F. Bis affa and A. Fa inelli
In con as , in his pape , we p opose a no el, gene al app oach o he o ma ion o collec i es ha is based on wo undamen al
s eps. Fi s , we apply deep ein o cemen lea ning echniques o ain an a en ion encode -decode model, wi h he objec i e o
au oma ically gene a ing a se o p omising collec i es based on he s uc u e o he conside ed scena io. In he second s ep, we
compile a weigh ed se packing (WSP) ins ance ha , by only aking in o accoun he p omising candida es gene a ed in he fi s s ep,
can be sol ed by off- he-shel ILP sol e s in a manageable ime budge . Thus, ou app oach does no equi e manually speci ying
any domain-specific knowledge, in con as wi h he abo e-men ioned sub-op imal s a e-o - he-a app oaches. Fu he mo e, by only
conside ing a se o p omising candida es a he han he en i e se o possible collec i es,1we educe he complexi y o he o iginal
p oblem by se e al o de s o magni ude while p oducing a high-quali y solu ion.
As such, his pape ad ances he s a e-o - he-a as ollows:
•We p opose a gene al app oach o he o ma ion o collec i es in eal-wo ld domains based on he no el combina ion o an
a en ion model and WSP o mula ion.
•We p oposed a no el aining p ocedu e o ou a en ion model based on Maximum En opy Rein o cemen Lea ning. In con as
o p e ious app oaches which use a en ion-based models o op imiza ion [6], ou solu ion achie es a wide a ie y o p omising
candida es. Such a ie y is a key ea u e ha allows he ILP sol e o compu e a high-quali y solu ion o he collec i e o ma ion
p oblem.
•We e alua e ou app oach on collec i e o ma ion p oblems inhe en in wo eal-wo ld domains (i.e., idesha ing and eam
o ma ion) by compa ing i wi h s a e-o - he-a app oaches specific o each domain. Ou esul s show ha ou app oach can
p oduce solu ions o compa able quali y wi hou equi ing any domain-specific knowledge. Mo eo e , we compa e ou app oach
wi h he mos ecen gene al app oach o o ming collec i es based on Mon e Ca lo ee sea ch (MCTS) [7],2showing ha ou
solu ions ou pe o m (in e ms o quali y) he ones compu ed by he coun e pa .
2. Backg ound & ela ed wo k
In his sec ion, we discuss he necessa y backg ound and he ele an li e a u e on he o ma ion o collec i es. We hen elabo a e
on p e ious a emp s a using machine lea ning echniques o sol e combina o ial op imiza ion p oblems.
2.1. Fo ma ion o collec i es o agen s
The p oblem o o ming collec i es o agen s has been deeply s udied om many diffe en pe spec i es in he scien ific li e a u e.
Depending on he con ex and he applica ion domain, collec i es o agen s a e also e e ed o as coali ions [8]o eams [5,9]o
agen s. He e we adop he e m “collec i e” o e e o he gene al concep o a “g oup” o agen s ha coope a e o comple e asks
o ob ain benefi s, as we deem i mo e gene al and in ui i e.
Mo e in pa icula , in his pape we ocus on he op imiza ion p oblem [10]o compu ing he bes se o non-o e lapping
collec i es (i.e., subse s) o agen s belonging o a uni e sal se 𝐴, o maximize he o al alue p o ided by a domain-specific u ili y
unc ion, e.g., he educ ion in e ms o cos o CO2emissions associa ed o he a angemen o a sha ed ip [3]o he imp o emen
hanks o coope a ion wi hin a eam o s uden s [5].
Fo mally, we conside a se o 𝑛agen s 𝐴 ={𝑎1, 𝑎2, … , 𝑎𝑛}and a u ili y unc ion 𝑓∶(𝐴) →ℝ(also e e ed o as cha ac e is ic
unc ion) ha maps e e y collec i e in he easible se 3o collec i es (𝐴) o a eal numbe . We o mula e he o ma ion o collec i es
as he p oblem o compu ing he bes se ∗o non-o e lapping subse s o 𝐴(also e e ed o as a coali ion s uc u e [8]) ha
maximizes he sum o he alues associa ed o each collec i e 𝐶∈∗, i.e.,
∗=a gmax
∈∏(𝐴)∑
𝐶∈
𝑓(𝐶),(1)
whe e
∏(𝐴)is he se o all pa i ions o 𝐴in o non-o e lapping easible subse s.
2.1.1. Comple e app oaches
By and la ge, he o ma ion o collec i es equi es o sol e a coali ion s uc u e gene a ion (CSG) p oblem [13,8]o , equi alen ly,
a se pa i ioning p oblem [14]. A weal h o comple e app oaches ha e been p oposed o sol e Equa ion (1) o op imali y [13],
depending on he p ope ies o he u ili y unc ion 𝑓. Comple e CSG algo i hms [15,16] usually make no assump ions on he u ili y
unc ion, which is ea ed as a black-box o acle. Un o una ely, he me e ac o p o iding he inpu o he solu ion algo i hm (wi hou
e en conside ing he un ime o he CSG algo i hm i sel ) equi es enume a ing a numbe o alues ha g ow exponen ially wi h he
numbe o agen s.
1The numbe o possible collec i es g ows exponen ially wi h he numbe o agen s, hence i is no manageable in eal-wo ld applica ions ha in ol e mo e han
a ew ens o agen s.
2By “gene al app oach” he e we mean an app oach ha can be applied ac oss diffe en domains wi hou significan changes, such as MCTS in his case.
3Depending on he conside ed domain, such a se o easible collec i es can be he en i e se o subse s o 𝐴o , o example, he se o all collec i es ha sa is y a
gi en cons ain (e.g., ca dinali y cons ain s [11]o g aph-based cons ain s [12]), as explained in Sec ion 2.1.2.
A i icial In elligence 328 (2024) 104064
3
A. Fenoy, F. Bis affa and A. Fa inelli
Fo his eason, comple e uncons ained CSG algo i hms a e limi ed o only 25–30 agen s, i.e., a scale ha is no sufficien o
ealis ic applica ions in ol ing hund eds o agen s (such as he ones we conside in his pape ), hence we will no conside hese
app oaches as benchma ks in ou expe imen al e alua ion.
2.1.2. App oaches o cons ained scena ios
In some applica ion domains, i is possible o exploi specific p ope ies o imp o e he un ime o he solu ion algo i hm by
conside ing cons ain s ha educe he numbe o easible collec i es. Ca dinali y cons ain s ha limi he maximum size o he
collec i es o 𝑘na u ally a ise in many ealis ic scena ios [3,5,11]. In addi ion, a s and o li e a u e pionee ed by Mye son [12]has
in es iga ed g aph- es ic ed scena ios [17–20]whe e collec i es can be o med only i hey induce a connec ed subg aph o an ini ial
g aph defined o e he se o agen s (e.g., a social ne wo k).
Despi e conside ing hese cons ain s can significan ly educe he numbe o o al collec i es (up o a polynomial numbe
(|𝐴|
𝑘)=
𝑂(|𝐴|𝑘)i collec i es a e es ic ed o a maximum ca dinali y o 𝑘agen s [11]), such a numbe emains p ohibi i ely la ge o
ealis ic applica ions in ol ing hund eds o agen s. Indeed, as obse ed by Bis affa e al. [3]and And ejczuk e al. [5], enume a ing
and compu ing he u ili y alue o all he collec i es o size up o 5can equi e hou s, especially when he compu a ion o he u ili y
unc ion is pa icula ly demanding (e.g., in eam o ma ion i equi es o sol e a small ask assignmen p oblem [5]). Along hese
lines, he au ho s o [3,5]concluded ha comple e algo i hms we e no a iable solu ion o eal-wo ld scena ios—e en cons ained
ones—, eso ing o domain-specific app oaches ha can compu e sub-op imal solu ions o good quali y in a manageable amoun o
ime (see Sec ion 2.1.5).
2.1.3. App oaches ocusing on specific unc ion ep esen a ions
Ano he s and o li e a u e [21–23]has ocused on al e na i e u ili y unc ion ep esen a ions, which allow one o educe he
compu a ional complexi y o he CSG p oblem by exploi ing specific p ope ies o he adop ed ep esen a ion. Fo example, Ieong
and Shoham [21] p oposed a concise ep esen a ion called ma ginal con ibu ion ne s, o MC-ne s, whe e he calcula ion o he u ili y
is based on a collec ion o ules. T an-Thanh e al. [22] p oposed a ep esen a ion called coali ional skill ec o model, whe e he e is
a se o skills in he sys em, and each agen has a skill ec o (a ec o consis ing o alues ha eflec he agen s’ le el in diffe en
skills). Mo e ecen ly, Bis affa e al. [23] ocused on he well-known induced subg aph game (ISG) ep esen a ion o iginally in oduced
by Deng and Papadimi iou [24]and p oposed a CSG algo i hm based on g aph-clus e ing ha exploi s he succinc ness o he
ep esen a ion.
By defini ion, hese app oaches can only be applied i he u ili y unc ion 𝑓o he collec i e o ma ion domain sa isfies some
specific p ope ies (e.g., i can be ep esen ed as a combina ion o ules in he case o MC-ne s, o i can be ep esen ed by a sum o he
weigh s o he g aph in case o ISGs). Un o una ely, hese specific p ope ies a ely hold in eal-wo ld applica ion domains. Indeed,
nei he o he wo conside ed eal-wo ld collec i e o ma ion domains (i.e., idesha ing and eam o ma ion) can be modeled as one
o he abo e-men ioned unc ion ep esen a ions. In con as , ou wo k goes in o he opposi e esea ch di ec ion, i.e., ob aining a
gene al app oach o collec i e o ma ion ha does no ely on any specific p ope y. Fo his eason, we will no compa e agains
hese app oaches in ou expe imen al e alua ion.
2.1.4. Team o ma ion app oaches
Collec i e o ma ion has also been widely s udied in he con ex o eam o ma ion, in which such a p oblem has been s udied om
diffe en pe spec i es. Fo ins ance, Gas on and desJa dins [25] ocused only on local op imiza ion wi hou conside ing any concep
o global op imal solu ion, p oposing a heu is ic o modi y he g aph connec ing he agen s based on local au onomous easoning.
Lappas e al. [26]s udied he complexi y o finding a single g oup o agen s who possess a gi en se o skills o minimize he
communica ion cos wi hin such a g oup, and p oposed a heu is ic algo i hm o sol e such a p oblem. Ma colino e al. [27] ocused
on o ming a single g oup o agen s ha has he maximum s eng h in he se o wo ld s a es, showing ha a di e se eam can
ou pe o m a eam o med by uni o m membe s, and p oposing op imal o ing ules o such a di e se eam. Finally, Liemhe cha a
and Veloso [28] ackled he ask o modeling he alues o he u ili y unc ion based on obse a ions, wi hou conside ing any
pa i ioning p oblem on op o i .
He e we ocus on he op imiza ion p oblem o o ming disjoin eams wi h he objec i e o maximizing he sum o he co espond-
ing u ili y alues. In his con ex , And ejczuk e al. [5] p oposed a local-sea ch algo i hm named SynTeam ha hea ily elies on he
s uc u e o he p oblem and he conside ed da ase o o m p oficien eams ha a e all assigned he same ask (e.g., an English
p oficiency ask, an a s and design ask, e c.). This local-sea ch app oach was la e ex ended by Geo ga a e al. [29,30] o accoun
o mul iple asks. P än a e and Hein z [9], on he o he hand, p oposed an op imal solu ion algo i hm o he same op imiza ion
p oblem, which in ol es sol ing a CSG and a ask assignmen p oblem a he same ime.
Since we conside he eam o ma ion scena io in ol ing one single ask, we only conside SynTeam [5]as a compe i o among
he abo e-discussed eam o ma ion app oaches.
2.1.5. Heu is ic app oaches
To o e come he scalabili y limi a ions discussed in p e ious sec ions, he o ma ion o collec i es in eal-wo ld domains is
usually ackled by means o sub-op imal app oaches ha ade gene ali y o scalabili y, i.e., ha exploi he specific s uc u e o he
conside ed domain o compu e good-quali y solu ions in a easible amoun o ime. No e ha , in his case, he domain knowledge
ha he app oaches exploi is no necessa ily ela ed o he cha ac e is ic unc ion ep esen a ion (in con as wi h he app oaches
discussed in Sec ion 2.1.3), a he i is ela ed o specific p ope ies o he applica ion domain.
A i icial In elligence 328 (2024) 104064
4
A. Fenoy, F. Bis affa and A. Fa inelli
Fo ins ance, Bis affa e al. [3] p oposed a solu ion algo i hm o la ge-scale idesha ing ha , by hea ily elying on he g eedy
na u e o he domain, is capable o compu ing solu ions o e y good quali y o hund eds o agen s wi hin one minu e. P e iously,
Fa inelli e al. [31] p oposed an app oach based on hie a chical clus e ing ha also elies on a g eedy heu is ic o iden i y he
mos p omising couple o coali ions ha can be me ged, un il no beneficial me ge can be execu ed. Un o una ely, hese app oaches
canno be applied in collec i e o ma ion domains ha a e no cha ac e ized by such a g eedy na u e, e.g., he eam o ma ion
domain discussed in [5].
Mo e ecen ly, Wu and Ramchu n [7] p oposed a CSG solu ion algo i hm based on MCTS ha can be used in any collec i e
o ma ion domain, including idesha ing and eam o ma ion. None heless, such a MCTS app oach employs a simula ion policy
based on a g eedy heu is ic simila o he one p oposed by Fa inelli e al. [31]. Indeed, he au ho s epo good pe o mance on
syn he ic da ase s ha a e cha ac e ized by a g eedy na u e.4
Along hese lines, in ou expe imen al e alua ion, we compa e agains he app oaches by Wu and Ramchu n [7]and by Bis affa
e al. [3].
2.2. Machine lea ning o op imiza ion
The use o machine lea ning echniques o sol e combina o ial op imiza ion p oblems is a ecen ye e y ac i e opic ha
has ecei ed a lo o a en ion du ing he las ew yea s. Acco ding o Bengio e al. [32], machine lea ning can con ibu e o
he op imiza ion field in wo old ways: i) eplace some hea y compu a ions by building as app oxima ions, and ii) imp o e he
op imiza ion app oach by lea ning domain-specific s uc u e.
Due o he wide di e si y among ways o combining machine lea ning and combina o ial op imiza ion, Bengio e al. [32] classi y
he diffe en app oaches along wo axes. Along he fi s axis, depending on he s uc u e o he o e all app oach, Bengio e al. [32]
iden ifies wo al e na i es: i) end- o-end machine lea ning app oaches ha a e able o di ec ly cons uc a solu ion o op imiza ion
p oblems, and ii) mixed app oaches ha use machine lea ning as a sub ou ine o a classical op imiza ion app oach, ei he as a
p ep ocessing s ep o used alongside he classical app oach in an online scheme. On he o he hand, he second axis conce ns he
adop ed lea ning me hodology, i.e., supe ised, unsupe ised, o ein o cemen lea ning.
Wi h espec o his classifica ion, in his pape we p opose a mixed app oach, whe e an a en ion model gene a es high- alued
candida e collec i es, which a e hen encoded as a iables in an ILP. Mo eo e , he a en ion model is ained by means o ein o ce-
men lea ning o lea n he domain-specific s uc u e o he applica ion domain.
Along hese lines, in wha ollows we fi s p o ide an o e iew o he ele an li e a u e on end- o-end app oaches, and hen we
ocus on mixed app oaches. A e wa d, we discuss app oaches ained wi h diffe en lea ning me hods.
2.2.1. End- o-end app oaches o op imiza ion
The e is a wide a ie y o end- o-end app oaches o op imiza ion, such as Poin e Ne wo ks by Vinyals e al. [33], G aph Con-
olu ional Ne wo ks by Joshi e al. [34], o A en ion mechanisms by Kool e al. [6]. These me hods ha e been applied o a ious
classic p oblems in Ope a ions Resea ch and Op imiza ion, such as he well-known a eling salespe son p oblem (TSP). Mo eo e ,
o he end- o-end app oaches ha e been de ised o a ian s o he ehicle ou ing p oblem (VRP), such as he capaci a ed VRP [35]
o he online capaci a ed VRP [36]. I is impo an o no e ha , while ou a en ion mechanism is inspi ed5by he one by Kool
e al. [6]—an end- o-end app oach—, ou o e all app oach is ins ead a mixed one, as men ioned in Sec ion 2.2. Mo e specifically,
ou a en ion model does no compu e he final solu ion o he conside ed p oblem (i.e., he o ma ion o collec i es), bu a he a
se o candida e collec i es ha cons i u e inpu o he ILP, which hen compu es he final solu ion. This combina ion o Machine
Lea ning and Op imiza ion makes ou app oach “mixed”.
In wha ollows, we discuss o he ele an wo ks in he ca ego y o mixed app oaches.
2.2.2. Mixed app oaches o op imiza ion
Mixed app oaches aim a combining machine lea ning wi h classic op imiza ion p ocedu es. In his line o esea ch, a s and
o li e a u e ocuses on using machine lea ning as a p ep ocessing s ep be o e a classical op imiza ion app oach. In pa icula , he
app oach p oposed by Ding e al. [37]sol es 8 diffe en classical p oblems, including TSP and VRP, by means o G aph Con olu ional
Neu al Ne wo ks which p edic he alue o bina y a iables in a mixed-in ege linea p og am (MILP) o mula ion o hese p oblems.
The solu ion is hen ound by employing a b anch and bound app oach which uses he alues o guide he sea ch. In he same
way, Li e al. [38] ackle benchma k sa isfiabili y and p oblems ela ed o social ne wo ks by means o G aph Con olu ional Neu al
Ne wo ks o selec he nodes in a g aph ha a e likely o appea in an op imal solu ion and hen sol e he p oblem o he educed
g aph. Simila o neu al ne wo k-based app oaches, suppo ec o machines (SVMs) also can play he ole o a heu is ic app oach as a
p ep ocessing s ep o op imiza ion p oblems. Examples o his a e he wo k o Xa ie e al. [39], which uses k-Nea es Neighbo s in
addi ion o SVMs o significan ly educe he p oblem size o Secu i y-Cons ained Uni Commi men p oblem in powe sys ems and
elec ici y ma ke s. Ano he example is he wo k o Sun e al. [40], which uses SVMs o find a educ ion o he g aph o he maximum
4Acco ding o he me hodology epo ed in [7], he alue o a coali ion 𝐶is co ela ed wi h i s ca dinali y |𝐶|, hence o ming bigge coali ions is, on a e age,
mo e beneficial.
5We ocus on a en ion models because ecen wo k [6] shows ha hey can significan ly ou pe o m Poin e Ne wo ks on ou ing p oblems. Mo eo e , since
inpu s o ou model a e se s o agen s (which a e pe mu a ion in a ian ), we p e e he use o an a en ion mechanism, whose ou pu is gua an eed o be in a ian o
pe mu a ions o he inpu se .
A i icial In elligence 328 (2024) 104064
5
A. Fenoy, F. Bis affa and A. Fa inelli
weigh clique p oblem. Many o he app oaches ha use machine lea ning as a p ep ocessing s ep ocus on educing he op imiza ion
p oblem (i.e., making he p oblem smalle and compu a ionally ac able). Despi e p oblem educ ion wi h machine lea ning does
no ensu e any op imali y gua an ee, hese app oaches can usually p o ide high-quali y solu ions hanks o he “backbone” s uc u e
o he op imiza ion p oblems hey ackle (acco ding o he e minology adop ed by [41]), i.e., op imal solu ion and high-quali y
solu ions a e likely o sha e a specific s uc u e. Ou wo k aims a ollowing a simila p oblem educ ion s a egy by lowe ing he
numbe o a iables in an ILP o mula ion o he collec i e o ma ion p oblem, bu in con as wi h he abo e-men ioned wo ks
(which build he en i e p oblem ins ance and hen educes i ), we di ec ly gene a e he educed ILP by gene a ing collec i es which
a e likely o be in he op imal solu ion.
Ano he amily o mixed app oaches is he one ha aims a in eg a ing machine lea ning wi hin a classical app oach o op imiza-
ion. Fo example, Ho ung and Tie ney [42]use an a en ion model o econs uc solu ions inside a La ge Neighbo hood Sea ch
se ing o he Capaci a ed VRP. Ano he example is he wo k o Ho ung and Tie ney [42], in which neu al ne wo ks a e used as
a heu is ic o guide sea ch inside a ee sea ch app oach o he con aine p e-ma shaling p oblem. In his espec , ou app oach is
simila o he one p oposed by Bis affa e al. [3], which uses a domain-specific heu is ic as a p ep ocessing s ep o he o ma ion o
candida e collec i es and hen compu es he final solu ion employing an ILP. Howe e , ins ead o using an ad-hoc heu is ic designed
o a specific domain, we in oduce an a en ion model ha lea ns he domain-specific s uc u e o a p oblem. The e o e, by no
elying on any domain-specific componen , ou app oach can be applied o s uc u ally diffe en collec i e o ma ion p oblems.
2.2.3. Lea ning me hods
Depending on he adop ed lea ning me hodology, an app oach can be classified as supe ised, unsupe ised, o based on ein-
o cemen lea ning. Se e al app oaches adop supe ised lea ning s a egies o imi a e he ou pu s o an al eady exis ing solu ion
algo i hm, hence, by ollowing Bengio e al. [32]’s e minology, “ eplacing i by i s ML app oxima ion”. Fo example, he abo e-
discussed wo k by Li e al. [38]makes use o supe ised lea ning o ain G aph Con olu ional Neu al Ne wo ks o Maximal
Independen Se , Minimum Ve ex Co e , Maximal Clique, and SAT. Khalil e al. [43] p opose an app oach o lea n om a p ecom-
pu ed da ase a anking unc ion which is hen used as a b anching heu is ic o MILP. Gasse e al. [44]and Nai e al. [45]also
aim a cons uc ing a b anching heu is ic o sol ing MILP, bu in hei case, hey di ec ly lea n o imi a e he decisions made by
an expe employing a c oss-en opy loss. The majo i y o hese app oaches aim a selec ing an op ion among se e al al e na i es
(e.g., a iable selec ion in b anch-and-bound app oaches), some app oaches use machine lea ning o decide i an ac ion (which is
usually e y demanding om a compu a ional poin o iew) needs o be pe o med o no . This is he case o he wo k by K ube
e al. [46]whe e hey use a supe ised lea ning app oach o decide whe he a Dan zig-Wol e decomposi ion should be applied o a
MIP ins ance o sol e i as e .
Unsupe ised lea ning ies o cap u e pa e ns appea ing in unlabeled da a. Since i s pu pose does no pu sue finding as
app oxima ions and i is no ob ious in which way i could imp o e he solu ion quali y o cu en app oaches, i s use when
combining machine lea ning wi h op imiza ion is no e y common. To he bes o ou knowledge, he only app oach ha applies
an unsupe ised machine lea ning echnique o op imiza ion is he wo k by Ka alias and Loukas [47], whe e a p obabilis ic loss is
p oposed o ain a G aph Neu al Ne wo k o he G aph pa i ioning and maximum clique p oblems.
Finally, ein o cemen lea ning (RL) aims a lea ning a policy (i.e., a sys em ha de e mines a cou se o ac ion) ha op imizes he
sum o u u e expec ed ewa ds obse ed om he ac ions pe o med by he policy. The policy is usually modeled inside a Ma ko
Decision P ocess and in e ac s wi h he en i onmen by execu ing an ac ion and ecei ing an obse a ion and a ewa d signal. The
use o RL is appealing in he con ex o mixing machine lea ning wi h op imiza ion because classical algo i hms used o his pu pose
usually in ol e sequen ial decisions, which can be modeled as a Ma ko Decision P ocess. Mo eo e , in con as wi h supe ised
lea ning, RL does no equi e o he app oaches o lea n om, since i lea ns pu ely om expe ience. Se e al app oaches aim a
eplacing supe ised lea ning wi h RL in he con ex o combina o ial op imiza ion. Fo example, he wo k by Bello e al. [48]and
he a o emen ioned wo k by Naza i e al. [35] which p oposes RL as an al e na i e way o ain Poin e Ne wo ks, p e iously ained
wi h supe ised lea ning [33].
Rela ed o ou wo k, he app oach by Kool e al. [6]employs he REINFORCE algo i hm, a RL app oach in oduced by
Williams [49], o ain an a en ion-based model o he T a eling Salespe son P oblem and he VRP. Along hese lines, we adop RL
ins ead o o he lea ning app oaches, since we aim a achie ing a gene al app oach ha is no limi ed by he quali y o he examples
used in a supe ised en i onmen . Because o he impo ance o he REINFORCE algo i hm, which cons i u es he aining amewo k
o ou a en ion-based model, we de o e he ollowing sec ion o discussing his algo i hm in mo e de ail.
2.3. The REINFORCE algo i hm
The REINFORCE algo i hm p oposed by Williams [49]cons i u es one o he pilla s o RL and has inspi ed many mode n RL
app oaches. The gene al idea o he algo i hm is o upda e he pa ame e s o a model u ilizing g adien me hods in he di ec ion ha
ein o ces ac ions wi h highe ewa ds.
A a gene al le el, a RL se up is cha ac e ized by a sequence o s a es, ac ions, and ewa ds, i.e., (𝑠1, 𝑎1, 𝑟1, 𝑠2, 𝑎2, 𝑟2, … , 𝑠𝐻, 𝑎𝐻, 𝑟𝐻).
An agen in his se up is modeled by a pa ame e ized policy 𝜋𝜽and i decides on he ac ions ha a e pe o med acco ding o he
obse ed s a es. Mo eo e , in he RL se up, he agen ecei es a ewa d as eedback om i s ac ions, which ein o ces ac ions leading
o a desi ed beha io . The ewa d is defined acco ding o he op imiza ion goal. In p ac ice, when conside ing RL o combina o ial
op imiza ion, he ewa d is assigned o be he u ili y unc ion o he op imiza ion domain. Howe e , his ewa d is usually no de-
fined o in e media e s a es. In such si ua ions, an expec ed e u n 𝐺𝑡is used ins ead, which can be compu ed om he p obabili ies

A i icial In elligence 328 (2024) 104064
6
A. Fenoy, F. Bis affa and A. Fa inelli
de e mined by he policy a each s a e o by es ima ing i h ough a simula ed ajec o y e e ed o as a ollou . In his wo k,
we employ he ollou echnique o es ima e he expec ed e u n o in e media e s a es co esponding o incomple e coali ions. To
upda e he policy pa ame e s 𝜽, Williams [49] p oposes o use g adien me hods, which upda e he pa ame e s in he di ec ion ha
maximizes he expec ed e u n wi h
𝜽←𝜽+𝛼𝐺𝑡∇𝜽log𝜋𝜽,(2)
whe e 𝛼is he size o he lea ning s ep. In his wo k, we adop a echnique om ac o -c i ic app oaches [50], which in oduces a
baseline o educe he a iance in he expec ed e u n. This echnique consis s o employing he inc emen o he expec ed e u n
wi h espec o a baseline 𝑏𝑡, which will be defined in he ollowing sec ions. Then, he upda e ule becomes
𝜽←𝜽+𝛼(𝐺𝑡−𝑏𝑡)∇𝜽log𝜋𝜽.(3)
P e ious wo k employs REINFORCE o ain a policy o p oduce solu ions o combina o ial op imiza ion p oblems [48,6], such
as he TSP and he VRP. Fo such applica ions, he cha ac e is ic unc ion o he p oblem is used as a ewa d o guide he models
owa ds gene a ing solu ions o con inuously imp o ing quali y un il hey con e ge o close- o-op imal solu ions. He e we employ
he REINFORCE algo i hm o ain a policy o gene a e collec i es o high quali y. Thus, he quali y o a collec i e, de e mined by
he u ili y unc ion o a specific collec i e o ma ion domain, is used as he ewa d.
Ve y ecen ly, he use o en opy wi hin REINFORCE has been independen ly p oposed by he esea che s o he eam Ra el
du ing he AI4TSP compe i ion [51]. Mo e specifically, Ra el’s app oach employs en opy egula iza ion “ o enhance explo a ion”
[51, Sec ion 4.2.2] wi hin RL o he solu ion o TSP. Simila ly, in ou collec i e o ma ion app oach, en opy is used o inc ease
he di e si y o he gene a ed candida es ( ia enhanced explo a ion), as we discuss in Sec ion 3.1.4. No ice ha , in con as o Ra el’s
app oach, we do no use machine lea ning o di ec ly p o ide a solu ion o he conside ed op imiza ion p oblem, bu o p o ide a
se o di e se candida e solu ions ha a e hen p ocessed by a classical op imiza ion app oach (i.e., an ILP).
A e ha ing discussed he RL se up, which will be pa o ou app oach, we now p oceed o p esen ou solu ion app oach o
op imiza ion p oblems in ol ing he o ma ion o collec i es.
3. Ou solu ion app oach
As seen in p e ious sec ions, collec i e o ma ion app oaches ha aim a conside ing he en i e se o possible collec i es canno
be applied o ealis ic applica ion domains since such a se is p ohibi i ely la ge o enume a e. In his espec , i is c ucial o a oid
he gene a ion o such an imp ac ically la ge p oblem ins ance in he fi s place since i would be impossible o handle o any
solu ion algo i hm. Indeed, ou app oach ollows his a ionale and wo ks by b eaking he p oblem in o wo pa s. Fi s , by means o
an a en ion model, we gene a e candida e collec i es, one a a ime, o cons uc a se o candida e collec i es. Second, we encode
hese collec i es in o an ILP, which compu es he final solu ion.
To accommoda e he discussion o ou app oach, we fi s e o mula e he op imiza ion p oblem in Equa ion (1)as an ILP:
maximize ∑
𝐶∈(𝐴)
𝑓(𝐶)⋅𝑥𝐶,
subjec o ∑
𝐶∈(𝐴)
𝑏𝑖,𝐶 ⋅𝑥𝐶≤1,∀𝑎𝑖∈𝐴,
(4)
whe e 𝑥𝐶is a bina y decision a iable ha encodes whe he collec i e 𝐶is in he se and 𝑏𝑖,𝐶 is a bina y alue ha encodes
whe he agen 𝑎𝑖∈𝐴belongs o he collec i e 𝐶.
No ice ha he ILP o mula ion in Equa ion (4) only conside s he cons ain ha collec i es mus be non-o e lapping. Depending
on he conside ed applica ion domain, i is also possible o impose ha he o med collec i es co e he en i e se 𝐴by en o cing
∑
𝐶∈(𝐴)
𝑏𝑖,𝐶 ⋅𝑥𝐶=1,∀𝑎𝑖∈𝐴. (5)
The p oblem in Equa ion (4) can be easily ecognized as a WSP, one o he o iginal 21 Ka p’s NP-comple e p oblems [52]. Because
o he compu a ional complexi y o such p oblems, he ILP can only be sol ed o small ins ances (i.e., 𝐴wi h less han a couple o
ens o agen s) by employing off- he-shel sol e s. On he o he hand, in eal-wo ld scena ios, he gene a ion o such an ILP (le alone
i s solu ion) can equi e hou s o compu a ion due o he necessi y o enume a ing all easible collec i es. This complexi y is u he
inc eased in scena ios whe e de e mining each alue 𝑓(𝐶) equi es a significan compu a ional effo , such as he syne gis ic alue
p oposed by And ejczuk e al. [5].
On he o he hand, by exploi ing he inhe en s uc u e o he domain, an expe migh p opose a educed se o p omising
collec i es (𝐴), om which a sub-op imal solu ion o high quali y can be ob ained. Following his app oach, in his pape we
p opose an a en ion-based model ha lea ns his s uc u e o gene a e an ILP o manageable size, i.e.,
maximize ∑
𝐶∈(𝐴)
𝑓(𝐶)⋅𝑥𝐶,
subjec o ∑
𝐶∈(𝐴)
𝑏𝑖,𝐶 ⋅𝑥𝐶≤1,∀𝑎𝑖∈𝐴.
(6)
A i icial In elligence 328 (2024) 104064
7
A. Fenoy, F. Bis affa and A. Fa inelli
Fig. 1. P oposed app oach o he o ma ion o collec i es. The a en ion model gene a es a educed se o collec i es om which an ILP sol e compu es he solu ion.
Fig. 1illus a es he wo-s ep app oach we p opose o he o ma ion o collec i es. In he fi s s ep, he a en ion model p oduces
collec i es, one by one, o build a se (𝐴)o candida e collec i es. In he second s ep, Equa ion (6)is sol ed wi h he se (𝐴)as
inpu o sol e he collec i e o ma ion p oblem. The a en ion model will be discussed in he ollowing sec ions.
Algo i hm 1 Pseudocode o ou app oach o he o ma ion o collec i es.
Inpu : se o agen s 𝐴, o e all ime budge 𝑡 ∈ℝ+, gene a ion po ion 𝑘 ∈[0, 1]
Ou pu : he compu ed se o collec i es
1: (𝐴) ←∅{Ini ialize emp y se o candida es}
2: epea
3: 𝐴′←𝐴{Local copy o inpu se o agen s}
4: while |𝐴′| >0do
5: 𝑆←subse o 𝐴′gene a ed by means o ou a en ion model
6: (𝐴) ←(𝐴) ∪𝑆{Add 𝑆 o he se o candida es}
7: 𝐴′←𝐴′⧵𝑆{Remo e 𝑆 om he local se o agen s}
8: end while
9: un il he ime budge 𝑡 ⋅𝑘expi es
10: Fo mula e he model in Equa ion (6)gi en (𝐴)compu ed in Lines 2–9
11: Sol e such a model wi h an ILP sol e gi en a ime budge o (1 −𝑘) ⋅𝑡
Algo i hm 1p o ides he pseudocode o ou gene al app oach o he o ma ion o collec i es. Following a s anda d p ac ice [3],
we assume ha ou en i e app oach is p o ided wi h a ime budge 𝑡and we dis ibu e such a ime budge be ween he wo phases
illus a ed in Fig. 1. Mo e specifically, we de o e a ime budge o 𝑘 ⋅𝑡(wi h 𝑘 ∈[0, 1]) o he fi s phase, in which we gene a e
he educed se (𝐴)by epea edly gene a ing a collec i e 𝑆wi h ou a en ion model and emo ing i om he ini ial se 𝐴un il
such a se has been en i ely consumed. I he gene a ion ime budge has no been exhaus ed, we epea he same p ocedu e wi h
ano he copy o he ini ial se . The emaining pa (1 −𝑘) ⋅𝑡is de o ed o he solu ion o he jus -compu ed educed ILP model in
Equa ion (6), by p o iding such a ime budge o he off- he-shel ILP sol e . In ou expe imen s in Sec ion 4we compu e he alue
o he pa ame e 𝑘 ia IRACE [53], a widely used so wa e o uning algo i hmic pa ame e s.
3.1. A en ion model
Ou a en ion model implemen s a decision-making p ocess whe e collec i es a e buil inc emen ally by selec ing elemen s om
he se o agen s 𝐴, one a e e y decision s ep, and adding hem o he collec i e 𝐶. Du ing such a decision-making p ocess, hese
wo undamen al pieces o in o ma ion (i.e., 𝐴and 𝐶) a e in e nally main ained as he s a e o he model.
Fig. 2illus a es an example o he p ocess o o ming a collec i e by means o he a en ion-based model in a idesha ing
applica ion domain. Ini ially, an emp y collec i e and he se 𝐴o agen s a e p o ided as inpu o he model, which ou pu s a
ec o o p obabili ies, one o each agen plus one o he “end-o -sequence” (𝑒𝑜𝑠) oken (indica ing ha no agen is selec ed and
e mina ing he p ocess o building he cu en collec i e). The p obabili ies, indica ing he bes agen o be selec ed, a e used o
sample one agen and add i o he collec i e. The collec i e is hen upda ed, and a new i e a ion s a s. A mask ha o ces he
p obabili y o selec ed agen s o ze o is used o a oid one agen being selec ed wice. The p ocess finishes when he 𝑒𝑜𝑠 oken is
sampled.
Mo e o mally, he in e nal s a e 𝑠o he model is ep esen ed by he uple 𝑠 =(𝐴, 𝐶), whe e 𝐴is he se o agen s and 𝐶is he
collec i e cu en ly being buil . Wi h a small abuse o no a ion,6ou model ecei es he se o agen s 𝐴as a lis o 𝑑𝑎dimensional
ea u e ec o s, whe e 𝑑𝑎is he numbe o ea u es. Following s anda d p ac ice [54], ou model assumes ha an elemen (in ou case
an agen ) can be ep esen ed as a ec o o ea u es (e.g., o igin and des ina ion loca ions in he idesha ing scena io, o s uden s’
pe sonali y ai s and compe ence le els in he eam o ma ion one). The model also ecei es a bina y encoding o a collec i e
𝐶={𝑏1,𝐶 , 𝑏2,𝐶 , … , 𝑏𝑛,𝐶 }, whe e 𝑏𝑖,𝐶 a e bina y alues de e mining whe he he espec i e agen s 𝑎𝑖a e in he collec i e o no .
Gi en a s a e 𝑠, we design an a en ion-based encode -decode model based on he one p oposed by [6], which defines a s ochas ic
policy 𝜋𝜽(𝑠)pa ame e ized by a se o lea nable pa ame e s 𝜽 ep esen ing he weigh s and biases o a neu al ne wo k) ha de e mine
he p obabili y o each elemen in he pool o agen s 𝐴 o be included in he collec i e 𝐶. Ou encode p oduces an embedding,
i.e., a con inuous ep esen a ion o he inpu , o each elemen in he pool. Then, as illus a ed in Fig. 3, he decode ecei es he
embedding and he collec i e o compu e he p obabili ies.
3.1.1. Mul i-head a en ion
The main block o ou encode -decode model is based on he a en ion mechanism by Vaswani e al. [55]. Wi hin ou app oach,
a en ion wo ks as a mapping whe e he inpu s a e, ollowing he s anda d nomencla u e [55,6], he que ies 𝑄and he keys 𝐾 ep e-
6Thus a , we conside ed 𝐴and 𝐶 o be se s o agen s. Now we edefine hem espec i ely as a lis o ec o s and a lis o bina y a iables.
A i icial In elligence 328 (2024) 104064
8
A. Fenoy, F. Bis affa and A. Fa inelli
Fig. 2. An illus a i e example o he p ocess ca ied ou by he a en ion model o o m a collec i e in a idesha ing en i onmen . In his example conce ning he
idesha ing domain, h ee agen s (1: ed, 2: g een, and 3: blue) a e he inpu o he model, oge he wi h he cu en collec i e, which is ini ialized emp y. The
collec i e is ep esen ed on a map o show he spa ial ela ions be ween he o igin (squa es) and des ina ion ( iangles) loca ions. The model ou pu s a ec o o
p obabili ies, one o each agen plus one o he “end-o -sequence” (𝑒𝑜𝑠) oken, which s ops he o ma ion o he collec i e. Du ing he selec ion p ocess, agen s ha
ha e al eady been selec ed a e masked ou (indica ed in g ay in his example). Bes iewed in colo s. (Fo in e p e a ion o he colo s in he figu e(s), he eade is
e e ed o he web e sion o his a icle.)
Fig. 3. Gene al scheme o he encode -decode app oach ha compu es he p obabili y 𝜋𝜽 o each agen in 𝐴 o be added o he collec i e 𝐶. The sizes o inpu ,
ou pu , and in e media e hidden s a es a e specified o each elemen . The specific de ails o he p obabili y compu a ion a e p o ided in Sec ion 3.1.1.
sen ed by a se o 𝑑𝑞and 𝑑𝑘dimensional ec o s espec i ely. The ou pu s a e he a en ion weigh s 𝑎𝑖𝑗 , which eflec he no malized
compa ibili y o he que y 𝒒𝑖wi h he key 𝒌𝑖. The fi s s ep o ob ain he a en ion weigh s is o compu e he compa ibili ies
𝑢𝑖𝑗 =(𝑊𝑞𝒒𝑖)𝑇(𝑊𝑘𝒌𝑗)
√𝑑𝑞
,(7)
whe e 𝑊𝑞and 𝑊𝑘a e wo lea nable linea ans o ma ions, and he ou pu is scaled wi h a ac o o
1
√𝑑𝑞
. The a en ion weigh s
a e hen ob ained by no malizing he compa ibili ies wi h a so max:
𝑎𝑖𝑗 =𝑒𝑢𝑖𝑗
∑𝑗′𝑒𝑢𝑖𝑗′.(8)
A i icial In elligence 328 (2024) 104064
9
A. Fenoy, F. Bis affa and A. Fa inelli
Fig. 4. Gene al scheme o ou encode a chi ec u e. Simila o he one p oposed by Vaswani e al. [55], i combines se e al s eps o mul i-head a en ion, eed o wa d
laye s, laye no maliza ion, and esidual connec ions. The encoding s ep is epea ed 𝑁 imes.
These a en ion weigh s al eady cap u e he desi ed in o ma ion (compa ibili y be ween que ies and keys) and can al eady be used
o a gi en pu pose, as we do in he las s ep o he decode , whe e we in e p e hese a en ion weigh s as p obabili ies o elemen s
in 𝐴 o be included in 𝐶; ha is, he highe he compa ibili ies, he highe he p obabili ies will be. Ne e heless, he main use o he
a en ion weigh s is o upda e a se o alues 𝑉 ep esen ed by a se o 𝑑𝑣dimensional ec o s by compu ing a linea combina ion o
he alues weigh ed by he a en ion weigh s
𝒗′
𝑖=∑
𝑗
𝑎𝑖𝑗(𝑊𝑣𝒗𝑗),(9)
whe e 𝑊𝑣is again a lea nable linea ans o ma ion. In p ac ice, acco ding o he mul i-head a en ion app oach, i is beneficial o
compu e a en ion in pa allel 𝑀 imes wi h diffe en pa ame e s 𝑊𝑞, 𝑊𝑘, and 𝑊𝑣, and combine he ou pu s a he end, i.e.,
𝒗′
𝑖=
𝑀
∑
𝑚=1
𝑊𝑜
𝑚𝒗′
𝑖𝑚,(10)
whe e 𝑊𝑜is again a lea nable linea ans o ma ion.
In ou app oach, we use he a en ion mechanism in he encode o inco po a e in o ma ion om he se o agen s 𝐴in o he
ep esen a ion o an agen 𝑎𝑖by using agen s in 𝐴as que ies, keys, and alues. Thus, he a en ion mechanism beha es as a message-
passing app oach be ween consecu i e neu al laye s in he a en ion-based model. This mechanism is known as sel -a en ion since
he elemen s in 𝐴a e upda ed acco ding o elemen s in he same se [55]. Fu he , in he decode , we upda e he ep esen a ion o
a collec i e 𝐶wi h in o ma ion abou he agen s 𝐴, i.e., we employ 𝐶as que y and alue, while 𝐴beha es as keys, ollowing he
s anda d nomencla u e adop ed o a en ion models [55,6].
3.1.2. Encode
Ou encode is inspi ed by he one p oposed by Vaswani e al. [55], bu in con as wi h he o iginal model, we omi posi ional
encoding since he o de o he elemen s in he pool o agen s is no ele an o he o ma ion o collec i es. Ins ead, we use an inpu
eed- o wa d laye o encode elemen s in he pool o agen s 𝐴 om i s 𝑑𝑎dimensional ea u e ep esen a ion o a 𝑑ℎdimensional
embedding be o e he main a en ion blocks.
To ge he encoded ep esen a ion o he pool o agen s 𝒉𝐴, he inpu embeddings a e upda ed using 𝑁a en ion blocks depic ed
in Fig. 4, each one consis ing o wo sub-laye s: a mul i-head sel -a en ion and a eed- o wa d laye . Each sub-laye adds a esid-
ual connec ion [56]and pe o ms laye no maliza ion [57]on i s ou pu s, i.e., Laye No m(𝑥 +sub-laye (𝑥)). To acili a e esidual
connec ions, all sub-laye s in he encode use he same dimensionali y 𝑑ℎ.
A i icial In elligence 328 (2024) 104064
16
A. Fenoy, F. Bis affa and A. Fa inelli
Da a a ailabili y
Da a will be made a ailable on eques .
Acknowledgemen s
The au ho s g a e ully acknowledge he compu e esou ces a A emisa, unded by he Eu opean Union ERDF and Comuni a
Valenciana ( h ough he 2014–2020 FEDER Ope a i e P og amme o Comuni a Valenciana, p ojec IDIFEDER/2018/048) as well
as he echnical suppo p o ided by he Ins i u o de Fisica Co puscula , IFIC (CSIC-UV). This wo k was suppo ed by he “ACISUD”
p ojec (PID2022-136787NB-I00) unded by MCIN/AEI/10.13039/501100011033 and by he “YOMA Ope a ional Resea ch” p ojec
(OPE02570) unded by he Bo na Founda ion.
Re e ences
[1] Eu opean Commission, Collec i e awa eness pla o ms o sus ainabili y and social inno a ion, h ps://ec .eu opa .eu /digi al -single -ma ke /en /collec i e -
awa eness, 2021.
[2] Uni ed Na ions, Sus ainable de elopmen goals, h ps://www .un .o g /sus ainablede elopmen /sus ainable -de elopmen -goals, 2015.
[3] F. Bis affa, C. Blum, J. Ce quides, A. Fa inelli, J.A. Rod íguez-Aguila , A compu a ional app oach o quan i y he benefi s o idesha ing o policy make s and
a elle s, IEEE T ans. In ell. T ansp. Sys . 22 (2021) 119–130.
[4] J. Alonso-Mo a, S. Sama anayake, A. Walla , E. F azzoli, D. Rus, On-demand high-capaci y ide-sha ing ia dynamic ip- ehicle assignmen , P oc. Na l. Acad.
Sci. 114 (2017) 462–467.
[5] E. And ejczuk, F. Bis affa, C. Blum, J.A. Rod íguez-Aguila , C. Sie a, Syne gis ic eam composi ion: a compu a ional app oach o Fos e di e si y in eams,
Knowl.-Based Sys . 182 (2019) 104799.
[6] W. Kool, H. an Hoo , M. Welling, A en ion, lea n o sol e ou ing p oblems!, in: P oceedings o he In e na ional Con e ence on Lea ning Rep esen a ions,
2019, pp. 1–25.
[7] F. Wu, S.D. Ramchu n, Mon e-Ca lo ee sea ch o scalable coali ion o ma ion, in: P oceedings o he In e na ional Join Con e ence on A ificial In elligence,
2020, pp. 407–413.
[8] G. Chalkiadakis, E. Elkind, M. Woold idge, Compu a ional Aspec s o Coope a i e Game Theo y, Syn hesis Lec u es on A ificial In elligence and Machine
Lea ning, Mo gan and Claypool Publishe s, 2011.
[9] F. P än a e, F. Hein z, An any ime algo i hm o op imal simul aneous coali ion s uc u e gene a ion and assignmen , Au on. Agen s Mul i-Agen Sys . 34 (2020)
1–31.
[10] J. Ce quides, A. Fa inelli, P. Mesegue , S.D. Ramchu n, A u o ial on op imiza ion o mul i-agen sys ems, Compu . J. 57 (2014) 799–824.
[11] O. Sheho y, S. K aus, Me hods o ask alloca ion ia agen coali ion o ma ion, A i . In ell. 101 (1998) 165–200.
[12] R.B. Mye son, G aphs and coope a ion in games, Ma h. Ope . Res. 2 (1977) 225–229.
[13] T. Rahwan, T.P. Michalak, M. Woold idge, N.R. Jennings, Coali ion s uc u e gene a ion: a su ey, A i . In ell. 229 (2015) 139–174.
[14] C.-H. Lin, Co po a e ax s uc u es and a special class o se pa i ioning p oblems, Ph.D. hesis, Case Wes e n Rese e Uni e si y, Cle eland, OH, USA, 1975.
[15] N. Changde , S. Aknine, S. Ramchu n, A. Du a, Odss: efficien hyb idiza ion o op imal coali ion s uc u e gene a ion, in: P oceedings o he AAAI Con e ence
on A ificial In elligence, 2020, pp. 7079–7086.
[16] T. Michalak, T. Rahwan, E. Elkind, M. Woold idge, N.R. Jennings, A hyb id exac algo i hm o comple e se pa i ioning, A i . In ell. 230 (2016) 14–50.
[17] T. Voice, M. Poluka o , N.R. Jennings, Coali ion s uc u e gene a ion o e g aphs, J. A i . In ell. Res. 45 (2012) 165–196.
[18] F. Bis affa, A. Fa inelli, G. Chalkiadakis, S.D. Ramchu n, A coope a i e game- heo e ic app oach o he social idesha ing p oblem, A i . In ell. 246 (2017)
86–117.
[19] T. Voice, S.D. Ramchu n, N.R. Jennings, On coali ion o ma ion wi h spa se syne gies, in: P oceedings o he In e na ional Con e ence on Au onomous Agen s
and Mul i-Agen Sys ems, 2012, pp. 223–230.
[20] F. Bis affa, A. Fa inelli, J. Ce quides, J. Rod íguez-Aguila , S.D. Ramchu n, Algo i hms o g aph-cons ained coali ion o ma ion in he eal wo ld, ACM T ans.
In ell. Sys . Technol. 8 (2017) 1–24.
[21] S. Ieong, Y. Shoham, Ma ginal con ibu ion ne s: a compac ep esen a ion scheme o coali ional games, in: P oceedings o he ACM Con e ence on Elec onic
Comme ce, 2005, pp. 193–202.
[22] L. T an-Thanh, T.-D. Nguyen, T. Rahwan, A. Roge s, N.R. Jennings, An efficien ec o -based ep esen a ion o coali ional games, in: P oceedings o he
In e na ional Join Con e ence on A ificial In elligence, 2013, pp. 383–389.
[23] F. Bis affa, G. Chalkiadakis, A. Fa inelli, Efficien coali ion s uc u e gene a ion ia app oxima ely equi alen induced subg aph games, IEEE T ans. Cybe n. 52
(2021) 5548–5558.
[24] X. Deng, C. Papadimi iou, On he complexi y o coope a i e solu ion concep s, Ma h. Ope . Res. 19 (1994) 257–266.
[25] M.E. Gas on, M. desJa dins, Agen -o ganized ne wo ks o dynamic eam o ma ion, in: P oceedings o he In e na ional Con e ence on Au onomous Agen s and
Mul i-Agen Sys ems, 2005, pp. 230–237.
[26] T. Lappas, K. Liu, E. Te zi, Finding a eam o expe s in social ne wo ks, in: P oceedings o he ACM SIGKDD Con e ence on Knowledge Disco e y and Da a
Mining, 2009, pp. 467–476.
[27] L.S. Ma colino, A.X. Jiang, M. Tambe, Mul i-agen eam o ma ion: di e si y bea s s eng h?, in: P oceedings o he In e na ional Join Con e ence on A ificial
In elligence, 2013, pp. 279–285.
[28] S. Liemhe cha a , M. Veloso, Weigh ed syne gy g aphs o effec i e eam o ma ion wi h he e ogeneous ad-hoc agen s, A i . In ell. 208 (2014) 41–65.
[29] A. Geo ga a, J.A. Rod íguez-Aguila , C. Sie a, Towa ds a compe ence-based app oach o alloca e eams o asks, in: P oceedings o he In e na ional Con e ence
on Au onomous Agen s and Mul i-Agen Sys ems, 2021, pp. 1504–1506.
[30] A. Geo ga a, J.A. Rod íguez-Aguila , C. Sie a, O. Mich, R. Kazhamiakin, A. Palme o App osio, J.-C. Pazzaglia, An any ime heu is ic algo i hm o alloca ing
many eams o many asks, in: P oceedings o he In e na ional Con e ence on Au onomous Agen s and Mul i-Agen Sys ems, 2022, pp. 1598–1600.
[31] A. Fa inelli, M. Bicego, F. Bis affa, S.D. Ramchu n, A hie a chical clus e ing app oach o la ge-scale nea -op imal coali ion o ma ion wi h quali y gua an ees,
Eng. Appl. A i . In ell. 59 (2017) 170–185.
[32] Y. Bengio, A. Lodi, A. P ou os , Machine lea ning o combina o ial op imiza ion: a me hodological ou d’ho izon, Eu . J. Ope . Res. (2020).
[33] O. Vinyals, M. Fo una o, N. Jai ly, Poin e ne wo ks, Ad . Neu al In . P ocess. Sys . (2015) 2692–2700.
[34] C.K. Joshi, T. Lau en , X. B esson, An efficien g aph con olu ional ne wo k echnique o he a elling salesman p oblem, p ep in , a Xi :1906 .01227, 2019.
[35] M. Naza i, A. O oojlooy, L. Snyde , M. Takác, Rein o cemen lea ning o sol ing he ehicle ou ing p oblem, Ad . Neu al In . P ocess. Sys . 31 (2018).
[36] J. James, W. Yu, J. Gu, Online ehicle ou ing wi h neu al combina o ial op imiza ion and deep ein o cemen lea ning, IEEE T ans. In ell. T ansp. Sys . 20
(2019) 3806–3817.

A i icial In elligence 328 (2024) 104064
17
A. Fenoy, F. Bis affa and A. Fa inelli
[37] J.-Y. Ding, C. Zhang, L. Shen, S. Li, B. Wang, Y. Xu, L. Song, Accele a ing p imal solu ion findings o mixed in ege p og ams based on solu ion p edic ion, in:
P oceedings o he AAAI Con e ence on A ificial In elligence, 2020, pp. 1452–1459.
[38] Z. Li, Q. Chen, V. Kol un, Combina o ial op imiza ion wi h g aph con olu ional ne wo ks and guided ee sea ch, Ad . Neu al In . P ocess. Sys . 31 (2018).
[39] A.S. Xa ie , F. Qiu, S. Ahmed, Lea ning o sol e la ge-scale secu i y-cons ained uni commi men p oblems, INFORMS J. Compu . 33 (2021) 739–756.
[40] Y. Sun, X. Li, A. E ns , Using s a is ical measu es and machine lea ning o g aph educ ion o sol e maximum weigh clique p oblems, IEEE T ans. Pa e n Anal.
Mach. In ell. 43 (2019) 1746–1760.
[41] P. Kilby, J. Slaney, T. Walsh, e al., The backbone o he a elling salespe son, in: P oceedings o he In e na ional Join Con e ence on A ificial In elligence,
2005, pp. 175–180.
[42] A. Ho ung, K. Tie ney, Neu al la ge neighbo hood sea ch o he capaci a ed ehicle ou ing p oblem, in: P oceedings o he Eu opean Con e ence on A ificial
In elligence, 2020, pp. 443–450.
[43] E. Khalil, P. Le Bodic, L. Song, G. Nemhause , B. Dilkina, Lea ning o b anch in mixed in ege p og amming, in: P oceedings o he AAAI Con e ence on A ificial
In elligence, 2016, pp. 724–731.
[44] M. Gasse, D. Ché ela , N. Fe oni, L. Cha lin, A. Lodi, Exac combina o ial op imiza ion wi h g aph con olu ional neu al ne wo ks, Ad . Neu al In . P ocess. Sys .
(2019) 15580–15592.
[45] V. Nai , S. Ba uno , F. Gimeno, I. on Glehn, P. Lichocki, I. Lobo , B. O’Donoghue, N. Sonne a , C. Tjand aa madja, P. Wang, e al., Sol ing mixed in ege
p og ams using neu al ne wo ks, p ep in , a Xi :2012 .13349, 2021.
[46] M. K ube , M.E. Lübbecke, A. Pa men ie , Lea ning when o use a decomposi ion, in: P oceedings o he In e na ional Con e ence on he In eg a ion o Cons ain
P og amming, A ificial In elligence, and Ope a ions Resea ch, 2017, pp. 202–210.
[47] N. Ka alias, A. Loukas, E dos goes neu al: an unsupe ised lea ning amewo k o combina o ial op imiza ion on g aphs, Ad . Neu al In . P ocess. Sys . (2020)
6659–6672.
[48] I. Bello, H. Pham, Q.V. Le, M. No ouzi, S. Bengio, Neu al combina o ial op imiza ion wi h ein o cemen lea ning, p ep in , a Xi :1611 .09940, 2016.
[49] R.J. Williams, Simple s a is ical g adien - ollowing algo i hms o connec ionis ein o cemen lea ning, Mach. Lea n. 8 (1992) 229–256.
[50] V. Konda, J. Tsi siklis, Ac o -c i ic algo i hms, Ad . Neu al In . P ocess. Sys . 12 (1999).
[51] Y. Zhang, L. Bliek, P. da Cos a, R.R. A sha , R. Reijnen, T. Ca shoek, D. Vos, S. Ve we , F. Schmi -Ulms, A. Ho ung, T. Shah, M. Sellmann, K. Tie ney, C.
Pe eaul -Lafleu , C. Leboeu , F. Bobbio, J. Pepin, W.A. Sil a, R. Gama, H.L. Fe nandes, M. Zaeffe e , M. López-Ibáñez, E. I u ozki, The fi s AI4TSP compe i ion:
lea ning o sol e s ochas ic ou ing p oblems, A i . In ell. 319 (2023) 103918.
[52] R.M. Ka p, Reducibili y Among Combina o ial P oblems, Sp inge , 2010.
[53] M. López-Ibáñez, J. Dubois-Lacos e, L.P. Cáce es, M. Bi a a i, T. S ü zle, The IRACE package: i e a ed acing o au oma ic algo i hm configu a ion, Ope . Res.
Pe spec . 3 (2016) 43–58.
[54] I. Good ellow, Y. Bengio, A. Cou ille, Deep Lea ning, MIT P ess, 2016.
[55] A. Vaswani, N. Shazee , N. Pa ma , J. Uszko ei , L. Jones, A.N. Gomez, Ł. Kaise , I. Polosukhin, A en ion is all you need, Ad . Neu al In . P ocess. Sys . (2017)
5998–6008.
[56] K. He, X. Zhang, S. Ren, J. Sun, Deep esidual lea ning o image ecogni ion, in: P oceedings o he IEEE Con e ence on Compu e Vision and Pa e n Recogni ion,
2016, pp. 770–778.
[57] J.L. Ba, J.R. Ki os, G.E. Hin on, Laye no maliza ion, p ep in , a Xi :1607 .06450, 2016.
[58] A.G. Ba o, R.S. Su on, C.W. Ande son, Neu onlike adap i e elemen s ha can sol e difficul lea ning con ol p oblems, IEEE T ans. Sys . Man Cybe n. (1983)
834–846.
[59] J. Schulman, F. Wolski, P. Dha iwal, A. Rad o d, O. Klimo , P oximal policy op imiza ion algo i hms, p ep in , a Xi :1707 .06347, 2017.
[60] Y. Kwon, J. Choo, B. Kim, I. Yoon, Y. Gwon, S. Min, POMO: policy op imiza ion wi h mul iple op ima o ein o cemen lea ning, Ad . Neu al In . P ocess. Sys .
33 (2020).
[61] D.P. Kingma, J. Ba Adam, A me hod o s ochas ic op imiza ion, p ep in , a Xi :1412 .6980, 2014.
[62] T.P. Lillic ap, J.J. Hun , A. P i zel, N. Heess, T. E ez, Y. Tassa, D. Sil e , D. Wie s a, Con inuous con ol wi h deep ein o cemen lea ning, p ep in , a Xi :
1509 .02971, 2015.
[63] T. Haa noja, A. Zhou, P. Abbeel, S. Le ine, So ac o -c i ic: off-policy maximum en opy deep ein o cemen lea ning wi h a s ochas ic ac o , in: P oceedings o
he In e na ional Con e ence on Machine Lea ning, 2018, pp. 1861–1870.
[64] B.W. Sil e man, Densi y Es ima ion o S a is ics and Da a Analysis, Rou ledge, 2018.
[65] E. Liscio, R. Le a-Le i, F. Bis affa, R.I.J. Dobbe, C.M. Jonke , M. Lopez-Sanchez, J. Rod íguez-Aguila , P.K. Mu ukannaiah, Value in e ence in socio echnical
sys ems, in: P oceedings o he In e na ional Con e ence on Au onomous Agen s and Mul i-Agen Sys ems, 2023, pp. 1774–1780.