I came to numerical optimization from symbolic AI, and more precisely from Knowledge
Representation and Reasoning (KR&R), i.e., expert systems, logic programming,
constraint satisfaction and SAT. In my view, the two fields share one premise:
the difficulty of a problem depends (often to a large extent) on how it is
written. Hence, the useful move is frequently to rewrite it, either as a set of
smaller problems coordinated by a master or in a different formalism for which an
efficient algorithm is available.
Sono arrivato all’ottimizzazione numerica dall’intelligenza
artificiale simbolica, e più precisamente dalla rappresentazione della conoscenza e dal ragionamento
automatico (KR&R), cioè dai sistemi esperti, dalla programmazione logica, dal
soddisfacimento di vincoli e da SAT. A mio avviso i due campi condividono una
premessa: la difficoltà di un problema dipende (spesso in larga misura) da come è
scritto. Di conseguenza, spesso conviene riscriverlo, come un insieme di problemi più piccoli coordinati da un problema master oppure in un formalismo diverso per
il quale sia disponibile un algoritmo efficiente.
Symbolic AI. I started with expert systems and logic programming, for
domains whose knowledge is codified and whose reasoning has to remain
inspectable, and with ontologies as a representation of lexical knowledge; I also
worked on heuristic search, in which the efficiency of an algorithm such as A*
depends (often almost entirely) on the heuristic that guides it. Of these, I have
pursued further the translation between formalisms: a planning
problem can be stated as a Constraint Satisfaction Problem and, from there, as a
propositional formula, at which point the machinery of logical reasoning applies
to it. I implemented that chain of translators in
aima-python, together with
the SAT solver at its end. The same question now comes back in the opposite
direction: whether a satisfiability problem can be decomposed along its structure
in the way one would decompose a mixed-integer program.
IA Simbolica. Ho iniziato con i sistemi esperti e la programmazione logica,
per domini in cui la conoscenza è codificata e il ragionamento deve restare
ispezionabile, e con le ontologie come rappresentazione della conoscenza lessicale; mi sono
occupato anche di ricerca euristica, in cui l’efficienza di un algoritmo come
A* dipende (spesso quasi interamente) dall’euristica che lo guida. Di questi
temi ho approfondito soprattutto la traduzione fra
formalismi: un problema di pianificazione può essere formulato come un problema di soddisfacimento di vincoli (CSP) e, da
lì, come una formula proposizionale, alla quale si
applicano gli strumenti del ragionamento logico. Ho implementato questa catena di
traduttori in aima-python,
insieme al SAT solver che la conclude. La stessa domanda si ripresenta ora nella
direzione opposta: se un problema di soddisfacibilità possa essere decomposto
lungo la sua struttura, così come si decompone un problema di programmazione lineare intera mista.
Mathematical Optimization. Decomposition performs the same operation on the
structure of a model instead of on its formalism. This covers Lagrangian
(Dantzig-Wolfe) Relaxation and Decomposition, Benders Decomposition, the Bundle
Methods that solve the nondifferentiable duals they give rise to, and the parallel solution of the
subproblems, which are typically many and independent by construction. This is
the premise of SMS++,
where a model is declared as a tree of nested blocks; hence, the same instance can
be solved monolithically, dualized along its linking constraints or split by
scenario, and the choice among these is a matter of configuration that does not
require the model to be rewritten. Reformulation comes back inside the
subproblems, as the recognition of a structure for which a specialized (often
combinatorial) algorithm exists. In fact, a decomposition method solves each
subproblem many times, with data that change (usually rather little) from one
call to the next. Much of my current work is therefore on re-optimization, i.e.,
on reusing what has been computed for one instance in the solution of the next
one, and on enlarging the class of subproblems that dynamic programming can solve
efficiently.
Ottimizzazione Matematica. La decomposizione compie la stessa operazione
sulla struttura di un modello anziché sul suo formalismo. Vi rientrano il Rilassamento Lagrangiano e la corrispondente
Decomposizione di Dantzig-Wolfe, la Decomposizione di Benders, i Metodi Bundle che risolvono i duali non differenziabili che ne
derivano, e la risoluzione in parallelo dei sottoproblemi, che sono tipicamente
molti e indipendenti per costruzione. È la premessa di
SMS++, dove un
modello è dichiarato come un albero di blocchi annidati; di conseguenza, la stessa
istanza può essere risolta in modo monolitico, dualizzata rispetto ai vincoli accoppianti o decomposta per scenari, e la scelta fra queste alternative è una
questione di configurazione che non richiede di riscrivere il modello. La
riformulazione ritorna all’interno dei sottoproblemi, come riconoscimento di
una struttura per la quale esiste un algoritmo specializzato (spesso
combinatorio). Infatti, un metodo di decomposizione risolve ciascun sottoproblema
molte volte, con dati che cambiano (di solito piuttosto poco) da una chiamata
all’altra. Buona parte del mio lavoro attuale riguarda quindi la re-optimization,
cioè il riuso di quanto calcolato per un’istanza nella
risoluzione della successiva, e l’allargamento della classe di sottoproblemi
che la programmazione dinamica può risolvere in modo efficiente.
Machine Learning, connecting the two. I see machine learning mainly as
a way of learning heuristics, to be placed at the points where an exact algorithm
makes a choice, and hence of making that algorithm faster. On the symbolic side this is the heuristic that guides a search algorithm such
as A*, or the branching of a SAT solver (as in
NeuroSAT); on the numerical side
it is the branching of a branch-and-bound whose bounds come from a specialized
relaxation, e.g., a Lagrangian one. In both cases the learned part makes the
choice, while the guarantees still come from the exact method (at least as long
as the learned choice is one that the method may take anyway); thus, a poor
prediction may somewhat slow the method down without affecting the correctness
of its result. Conversely, learning problems can be written as structured
optimization models, to which the same decomposition and re-optimization
machinery applies.
Machine Learning, ponte fra i due ambiti. Vedo il machine learning
soprattutto come un modo per apprendere euristiche da collocare nei punti in cui
un algoritmo esatto compie una scelta, e quindi per rendere quell’algoritmo
più veloce. Dal lato simbolico si tratta dell’euristica che guida un algoritmo di
ricerca come A*, o del branching di un SAT solver (come in
NeuroSAT); dal lato numerico,
del branching di un branch-and-bound le cui valutazioni (bound) provengono da un
rilassamento specializzato, per esempio lagrangiano. In entrambi i casi la parte appresa compie
la scelta, mentre le garanzie continuano a venire dal metodo esatto (almeno finché
la scelta appresa è una di quelle che il metodo potrebbe comunque compiere); di
conseguenza, una previsione sbagliata può rallentare in parte il metodo senza
intaccare la correttezza del risultato. Viceversa, i problemi di apprendimento
possono essere scritti come modelli di ottimizzazione strutturati, ai quali si
applicano gli stessi strumenti di decomposizione e di re-optimization.
