MIPLIB Contributed

This is a model of a funny combinatorial game called "EnLight" by FeejoSoft. You can get it as freeware for your PDA from this URL: http://www.feejo.com/index.php?page=productdetail&id=PPC0006. The model was built by Adrian Zymolka.

The setup is as follows: Given is a board of n x n light bulbs. In the initial setup, some bulbs are switched on and some are switched off. The goal is to switch all bulbs off in the minimal number of moves. One move consists of triggering a single bulb (i.e., changing its status from on to off or from off to on) which automatically also triggers its horizontal and vertical neighbors. The board is not circular, i.e. the bulbs at the border have fewer neighbors.

Here is an example (- denotes off, * denotes on):

. 1 2 3 4 5
a - - - - -
b - - - - -
c - - - * -
d - * - - -
e - - * * -

Triggering the bulb at position d3 yields the following situation:

. 1 2 3 4 5
a - - - - -
b - - - - -
c - - * * -
d - - * * -
e - - - * -

Triggering now the bulb at e5 yields the following:

. 1 2 3 4 5
a - - - - -
b - - - - -
c - - * * -
d - - * * *
e - - - - *

The ZIMPL model "enlight.zpl" describes instances of various board sizes with the initial configuration always being only one bulb switched on which is located at position a1. The additional model "enlight_hard.zpl" represents one particular level of the game, which is a 10x10 board with a special initial configuration.

We included the ZIMPL model "enlight.zpl" of this problem. The key observation to model the game is that it is unnecessary to trigger an individual bulb more than once. Therefore, the triggering can be modeled by binary variables. The constraints are that the initial board setup plus the number of state switches is an even number for all light bulbs. This is modeled by additional integer variables. Note that each bulb can be triggered at most 5 times (this is not in the model, but this should be observed by presolving the problem instance), which means that the upper bounds for the integer variables are 3.

The instances seem to be quite hard for larger board sizes, even though the size of the problem is very small. We think this is due to the modulo equations and the symmetry of the problem. However, it seems that a different branching rule is the key to solving these problems. By activating the "inference" branching rule instead of "reliability branching" in SCIP 0.81, the 10x10 instance can be solved in 18 seconds and 42000 branching nodes, while SCIP with default settings needed 2800 seconds and 6 million nodes. Activating conflict analysis reduces this even more to 11 seconds and 16000 branching nodes (the SCIP settings file is included as "enlight.set"). The enlight_hard.lp was solved with inference branching and conflict analysis by SCIP in 588 seconds and 587000 nodes with the solution found after 17 seconds in 17000 nodes. All results were obtained on a 3.8GHz Pentium-4.

Here are some optimal solutions we know. It is very interesting that some instances are infeasible (at least as long as SCIP doesn't have a bug). Maybe, someone can try to find out the reason for these infeasibilities. There should be some combinatorial argument for this.

enlight4.lp: infeasible
enlight5.lp: infeasible
enlight6.lp: 17
enlight7.lp: 19
enlight8.lp: 27
enlight9.lp: infeasible
enlight10.lp: 33
enlight11.lp: infeasible
enlight12.lp: 61
enlight13.lp: 71
enlight14.lp: infeasible
enlight15.lp: 69
enlight16.lp: infeasible
enlight_hard.lp: 37 

Icon  Name                    Last modified      Size  Description
[   ] enlight.set             2006-03-02 16:16   79K  
[TXT] enlight.txt             2006-03-02 16:16  3.4K  
[   ] enlight.zpl             2006-03-02 16:16  3.1K  
[   ] enlight10.lp            2006-03-02 16:16   13K  
[   ] enlight11.lp            2006-03-02 16:16   16K  
[   ] enlight12.lp            2006-03-02 16:16   19K  
[   ] enlight13.lp            2006-03-02 16:16   23K  
[   ] enlight14.lp            2006-03-02 16:16   26K  
[   ] enlight15.lp            2006-03-02 16:16   31K  
[   ] enlight16.lp            2006-03-02 16:16   35K  
[   ] enlight4.lp             2006-03-02 16:16  2.1K  
[   ] enlight5.lp             2006-03-02 16:16  3.2K  
[   ] enlight6.lp             2006-03-02 16:16  4.6K  
[   ] enlight7.lp             2006-03-02 16:16  6.2K  
[   ] enlight8.lp             2006-03-02 16:16  8.1K  
[   ] enlight9.lp             2006-03-02 16:16   10K  
[   ] enlight_hard.lp         2006-03-02 16:16   13K  
[   ] enlight_hard.zpl        2006-03-02 16:16  3.3K