━━━━━━━━━━━━━━━━
			      OPTIMIZATION


			     Torsten Schaub
			    ━━━━━━━━━━━━━━━━


Table of Contents
─────────────────

1 Encoding
.. 1.1 Systems
.. 1.2 Basic encoding
.. 1.3 Optimization phases
.. 1.4 clasp output
.. 1.5 More demanding instance
.. 1.6 Advanced encoding
..... 1.6.1 Encodings
..... 1.6.2 Explanation
..... 1.6.3 Solving
..... 1.6.4 Important note
.. 1.7 More demanding instance, continued
2 Solving
.. 2.1 Options for optimization
.. 2.2 Progress saving
.. 2.3 Optimization strategies
..... 2.3.1 Multi-criteria optimization
.. 2.4 Optimization heuristics
.. 2.5 Structure-specific heuristics
.. 2.6 Domain-specific heuristics
.. 2.7 Parallel optimization
.. 2.8 Another example


Optimization in clasp 3 via the Traveling Sales Person problem

Torsten Schaub, torsten@cs.uni-potsdam.de

based on encodings by Martin Gebser (BIG thanks!)

[http://potassco.sourceforge.net/videos.html]


1 Encoding
══════════

1.1 Systems
───────────

  • _commands_ gringo4 –version clasp3 –version


1.2 Basic encoding
──────────────────

  • Example: Traveling Sales Person, Section 3.3 in [1]
    • *Note* [1] uses language of gringo 3
    • See also
      [http://en.wikipedia.org/wiki/Travelling_salesman_problem]

  • _commands_

    • problem instance view-file [graph.lp] view-file [costs.lp]

    • problem encoding view-file [tsp.lp4] [2]

    • problem solving gringo4 tsp.lp4 graph.lp costs.lp | clasp3


  [graph.lp] file:graph.lp

  [costs.lp] file:costs.lp

  [tsp.lp4] file:tsp.lp4


1.3 Optimization phases
───────────────────────

  • Branch and bound (top-down)
    1) converging to optimum (SAT … SAT)
    2) prove optimiality (UNSAT)

  • Unsatisfiable core driven (bottom-up; cf [4])
    1) identify and relax cores (UNSAT … UNSAT)
    2) until consistency (SAT)


1.4 clasp output
────────────────

  • option

    –quiet[=<m>,<o>],-q : Configure printing of models and optimize
       values <m>: print {0=all|1=last|2=no} models <o>: print
       {0=all|1=last|2=no} optimize values [<m>]

    • _commands_

      gringo4 tsp.lp4 graph.lp costs.lp | clasp3 –quiet=0,0 gringo4
      tsp.lp4 graph.lp costs.lp | clasp3 –quiet=1,0 gringo4 tsp.lp4
      graph.lp costs.lp | clasp3 –quiet=2,0


1.5 More demanding instance
───────────────────────────

  • Example: Clumpy graphs [5]

  • _commands_ gringo4 clumpy-08x08_06.lp tsp.lp4 | clasp3 –quiet=2,0


1.6 Advanced encoding
─────────────────────

  • Example: Traveling Sales Person, Section 8.3 in [1]
    • *Note* [1] uses language of gringo 3


1.6.1 Encodings
╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌

  • _commands_ view-file [tsp.lp4] [2] view-file [tspA.lp4] [2]
    • *ATTENTION* Objective value is different (though optimum models
       remain the same)!


  [tsp.lp4] file:tsp.lp4

  [tspA.lp4] file:tspA.lp4


1.6.2 Explanation
╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌

  Consider node 1:

  edge(1,4). cost(1,4,1).  % <<< lowest cost edge
  edge(1,2). cost(1,2,2).  edge(1,3). cost(1,3,3).

  order(1,1,2).  order(1,2,3).

                 % cycle(1,4) no penalty penalty(1,1,1) :- cycle(1,2).
  % penalty of one penalty(1,2,1) :- cycle(1,3).  % penalty of one …
  penalty(1,1,1) :- penalty(1,2,1).  % … plus one

  #minimize{ 1,.. : penalty(1,1,1), 1,.. : penalty(1,2,1), … }.


1.6.3 Solving
╌╌╌╌╌╌╌╌╌╌╌╌╌

  gringo4 tsp.lp4 graph.lp costs.lp | clasp3 gringo4 tspA.lp4 graph.lp
  costs.lp | clasp3

  gringo4 tsp.lp4 clumpy-08x08_06.lp | clasp3 –quiet=2,0 gringo4
  tspA.lp4 clumpy-08x08_06.lp | clasp3 –quiet=2,0

  gringo4 tsp.lp4 clumpy-08x08_10.lp | clasp3 –quiet=2,0 gringo4
  tspA.lp4 clumpy-08x08_10.lp | clasp3 –quiet=2,0


1.6.4 Important note
╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌

  ALWAYS GET THE ENCODING RIGHT AT FIRST!  YOU CAN NEVER RECOVER FROM A
  BAD ENCODING!


1.7 More demanding instance, continued
──────────────────────────────────────

  • _commands_ gringo4 clumpy-08x08_10.lp tspA.lp4 > tspA10 clasp3
    tspA10 –quiet=2,0


2 Solving
═════════

2.1 Options for optimization
────────────────────────────

  • _commands_ (use less on shell ;) clasp3 –help=3 > helper

  • view-file [helper]


  [helper] file:helper


2.2 Progress saving
───────────────────

  • See [6]

  • view-file [helper]

  • _commands_

    clasp3 tspA10 –quiet=2,0 –save-progress=0 clasp3 tspA10 –quiet=2,0
    –save-progress=1

  • view-file [ham.lp4]
  • view-file [hamO.lp4]

  • _commands_

    gringo4 hamO.lp4 clumpy-08x08_10.lp | clasp3 –quiet=2,0
    –save-progress=1 gringo4 hamO.lp4 clumpy-08x08_10.lp | clasp3
    –quiet=2,0 –save-progress=0 gringo4 hamO.lp4 clumpy-08x08_10.lp |
    clasp3 –quiet=2,0 –save-progress=0 –restart-on-model


  [helper] file:helper

  [ham.lp4] file:ham.lp4

  [hamO.lp4] file:hamO.lp4


2.3 Optimization strategies
───────────────────────────

  • view-file [helper]

  • _commands_

    clasp3 tspA10 –quiet=2,0 –opt-strategy=0 clasp3 tspA10 –quiet=2,0
    –opt-strategy=2 clasp3 tspA10 –quiet=2,0 –opt-strategy=3 clasp3
    tspA10 –quiet=2,0 –opt-strategy=4 [4] clasp3 tspA10 –quiet=2,0
    –opt-strategy=5

  • _commands_

    gringo4 ham.lp4 clumpy-08x08_10.lp | clasp3 –quiet=2,0

    gringo4 hamO.lp4 clumpy-08x08_10.lp | clasp3 –quiet=2,0
    –opt-strategy=0 gringo4 hamO.lp4 clumpy-08x08_10.lp | clasp3
    –quiet=2,0 –opt-strategy=2 gringo4 hamO.lp4 clumpy-08x08_10.lp |
    clasp3 –quiet=2,0 –opt-strategy=3 gringo4 hamO.lp4
    clumpy-08x08_10.lp | clasp3 –quiet=2,0 –opt-strategy=4

    gringo4 hamO.lp4 clumpy-16x16_10.lp | clasp3 –quiet=2,0
    –opt-strategy=0 gringo4 hamO.lp4 clumpy-16x16_10.lp | clasp3
    –quiet=2,0 –opt-strategy=4


  [helper] file:helper


2.3.1 Multi-criteria optimization
╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌

  • view-file [tspMO.lp4] (see [hamO.lp4])

  • _commands_

    gringo4 tspMO.lp4 clumpy-08x08_10.lp | clasp3 –quiet=2,0
    –opt-strategy=0 gringo4 tspMO.lp4 clumpy-08x08_10.lp | clasp3
    –quiet=2,0 –opt-strategy=1


  [tspMO.lp4] file:tspMO.lp4

  [hamO.lp4] file:hamO.lp4


2.4 Optimization heuristics
───────────────────────────

  • view-file [helper]

  • _commands_ clasp3 tspA10 –quiet=2,0 –opt-heuristic=1 clasp3 tspA10
    –quiet=2,0 –opt-heuristic=2 clasp3 tspA10 –quiet=2,0
    –opt-heuristic=3


  [helper] file:helper


2.5 Structure-specific heuristics
─────────────────────────────────

  • See [7]

  • view-file [helper]

  • _commands_ clasp3 tspA10 –quiet=2,0 –heuristic=domain –dom-pref=16
    –dom-mod=4 clasp3 tspA10 –quiet=2,0 –heuristic=domain –dom-pref=16
    –dom-mod=5


  [helper] file:helper


2.6 Domain-specific heuristics
──────────────────────────────

  • See [7]

  • _commands_ gringo4 clumpy-08x08_10.lp tspA.lp4 | clasp3
    –heuristic=domain –quiet=2,0 gringo4 clumpy-08x08_10.lp tspA.lp4
    tspH.lp4 | clasp3 –heuristic=domain –quiet=2,0


2.7 Parallel optimization
─────────────────────────

  • view-file [helper]

  • _commands_
    • auto configuration clasp3 –print-portfolio clasp3 tspA10
      –quiet=2,0 –parallel-mode=4,compete

    • homogeneous configuration clasp3 tspA10 –quiet=2,0
      –configuration=tweety –opt-strategy=0 –parallel-mode=4,compete

    • customized configuration view-file [optfolio-heterogeneous] clasp3
      tspA10 –quiet=2,0 –configuration=optfolio-heterogeneous
      –parallel-mode=4,compete


  [helper] file:helper

  [optfolio-heterogeneous] file:optfolio-heterogeneous


2.8 Another example
───────────────────

  • Example: Ricochet Robots [8] See also
    [http://en.wikipedia.org/wiki/Ricochet_Robot] Fix horizon to 15 and
    try to find a minimum number of moves to reach target position (viz
    -c goal=4)

  • _commands_ view-file [RR/robotsN.lp4] [2]

    gringo4 RR/board16-1.lp RR/robots.lp RR/goals16-1.lp RR/robotsN.lp4
    -c horizon=15 -c goal=4 > rico16hor15goal4 clasp3 rico16hor15goal4
    –quiet=2,0 –opt-strategy=0 clasp3 rico16hor15goal4 –quiet=2,0
    –opt-strategy=2 clasp3 rico16hor15goal4 –quiet=2,0 –opt-strategy=3
    clasp3 rico16hor15goal4 –quiet=2,0 –opt-strategy=4 clasp3
    rico16hor15goal4 –quiet=2,0 –opt-strategy=5


  [RR/robotsN.lp4] file:RR/robotsN.lp4



Footnotes
─────────

[1] M. Gebser, R. Kaminski, B. Kaufmann, and T. Schaub: Answer Set
Solving in Practice.  Synthesis Lectures on Artificial Intelligence
and Machine Learning, Morgan and Claypool December 2012, 238 pages,
[doi:10.2200/S00457ED1V01Y201211AIM019]

[2] We use extension lp4 to indicate encodings for gringo 4 (along the
ASP-Core-2 standard [3])

[3] F. Calimeri, W. Faber, M. Gebser, G. Ianni, R. Kaminski,
T. Krennwallner, N. Leone, F. Ricca, and T. Schaub: ASP-Core-2: Input
language format. 2012.  Available at
[https://www.mat.unical.it/aspcomp2013/files/ASP-CORE-2.0.pdf].

[4] B. Andres, B. Kaufmann, O. Mattheis and T. Schaub:
Unsatisfiability-based optimization in clasp.  ICLP: 212-221, 2012.
Available at
[http://www.cs.uni-potsdam.de/wv/pdfformat/ankamasc12a.pdf]

[5] J. Ward, J. Schlipf: Answer Set Programming with Clause Learning.
LPNMR: 302-313, 2004.

[6] K. Pipatsrisawat, A. Darwiche: A lightweight component caching
scheme for satisfiability solvers.  SAT: 294-299, 2007.

[7] M. Gebser, B. Kaufmann, R. Otero, J. Romero, T. Schaub and
P. Wanko: Domain-specific Heuristics in Answer Set Programming.  AAAI:
350-356, 2013.  Available at
[http://www.cs.uni-potsdam.de/wv/pdfformat/gekaotroscwa13a.pdf]

[8] M. Gebser, H. Jost, R. Kaminski, P. Obermeier, O. Sabuncu,
T. Schaub and M. Schneider: Ricochet Robots: A transverse ASP
benchmark.  LPNMR: 348-360, 2013.  Available at
[http://www.cs.uni-potsdam.de/wv/pdfformat/gejokaobsascsc13a.pdf]