Migrating from Windows 7 to Ubuntu

Ubuntu desktop

If you, like me, get tired with Windows 7 and cannot wait for the free update to Windows 10, you might also want to consider migrating to Ubuntu Trusty 14.04, which is the Long Term Support (LTS) version of the Ubuntu operating system for desktop PCs and laptops. It can be downloaded from Ubuntu official site for fee and it is easy to install following the instructions there. Recently I just downloaded and installed it on my old HP Compaq 6510b laptop. Comparing to almost 20 GBs of my old Windows 7 system, my new Ubuntu system only occupies 6.3 GBs,  and runs much faster.

This post describes installation processes of some software that I have been using on a regular basis on Windows 7 and I would like to move to my fresh installed Ubuntu. Most of these processes followed instructions from Ubuntu support forums —Ask Ubuntu, where you can get nearly all answers to any technical issues you might encountered.  All processes posted here have been tested by myself and guaranteed working, well at least on my laptop. I hope you find them helpful.

Install Google Chrome

Ubuntu has its own default web browser, Firefox, which is also very powerful. But I have been using Google Chrome for so long time that I don’t want to switch. On Ubuntu, you can install either Google Chrome or Chromium-browser, see this post for difference between the two. Because Google Chrome includes a variety of closed-source bits that Chromium lacks, I decided to stay with Google Chrome.  I have followed steps below to download and install Google Chrome:

1. Goto: https://www.google.com/intl/en-CA/chrome/browser/
2. Click Download Chrome
3. Choose either 32 bit .deb(for 32bit Ubuntu) or 64 bit .deb (for 64bit Ubuntu)
4. Click Accept and Install
5. Download .deb file to a folder (Downloads is the default folder)
6. Open up your Downloads folder
7. Double-click the .deb file you just downloaded
8. This should launch Ubuntu Software Center
9. When it prompts you to whether you wish to install Chrome, just say yes
10. Input Password when asked to install

After install, Chrome will be updated through the normal Ubuntu update process, so you can get the latest version when Ubuntu updates.

Install Microsoft Fonts in LibreOffice Suits

By installing Microsoft Fonts on Ubuntu, I am not going to say Ubuntu default fonts are not good. In contract, I think they are more beautiful than the Microsoft fonts. I am still using Windows 7 on my office computer, and I need the popular fonts that are created by Microsoft, such as Times New Roman and Calibri,  installed on my Linux system to see the documents as they were intended to look on Windows.

According to the Chris Hoffman’s post, I have installed two Microsoft font packages:

(1) Microsoft’s TrueType Core Fonts

This font pack contains Arial, Arial Black, Andale Mono, Comic Sans MS, Courier New, Georgia, Impact, Times New Roman, Trebuchet, Verdana, and Webdings. Times New Roman was the default font for Microsoft Office documents before its 2007 version.

This package can be installed through following steps:

1. Run command  sudo apt-get install ttf-mscorefonts-installer  in the terminal
2. Type your password when promoted
3. Select yes when ask do you want to continue
4. When license agreement appears, use up/down arrow keys to scroll through it
5. Press Tab or Right Arrow key to select the OK button and press Enter to accept the EULA licence agreement to install

(2) Microsoft’s ClearType Fonts

This font pack includes fonts Calibri, Cambria, Candara, and Consolas, Constan, Corbel. These fonts have been added in Windows Vista and Office 2007.  Among them, Calibri became the default font since Microsoft Office 2007.

This package can be installed through following steps:

1. Create a hiden folder .fonts under the Home directory through running command mkdir .fonts in the terminal
2. Run following command in the terminal. This command downloads and runs the VistaFonts-Installer script, which downloads the fonts from Microsoft and installs them on the system:
   wget -qO- http://plasmasturm.org/code/vistafonts-installer/vistafonts-installer | bash

After install, these fonts are available in LibreOfficer.

Install Java 8 and Eclipse

Install Java 8

You can follow the steps from liquidweb to install Java 8 through the WebUpd8 Team Personal Package Archive (PPA). However, I adapted the manual process specified by this post directly from the tar.gz provided by Oracle.

1. Download the JDK 8 file from Oracle (I chose jdk-8u66-linux-x64.tar.gz)
2. Go to the directory where the downloaded file locates (usually Downloads) and extract the JDK file through GUI (right click -> Extract Here) or running command sudo tar -zxvf jdk-8u66-linux-x64.tar.gz.
3. Move the extracted folder to /usr/lib/jvm, through sudo mv jdk1.8.0_66 /usr/lib/jvm This is not required, but it is the place where Java runtime software is installed.
4. Create a file /etc/profile.d/oraclejdk.sh through gksudo gedit /etc/profile.d/oraclejdk.sh and put following content in it. TO make these environments effective, you have to reboot.

          export J2SDKDIR=/usr/lib/jvm/jdk1.8.0_66
          export J2REDIR=/usr/lib/jvm/jdk1.8.0_66/jre
          export PATH=$PATH:/usr/lib/jvm/jdk1.8.0_66/bin:/usr/lib/jvm/jdk1.8.0_66/jre/bin
          export JAVA_HOME=/usr/lib/jvm/jdk1.8.0_66
          export DERBY_HOME=/usr/lib/jvm/oracle_jdk8/jdk1.8.0_66/db

Install Eclipse IDE

I used following steps to install the newest Eclipse Mars.1 (4.5.1):

1. Download the Eclipse IDE for Java EE Developers for my Linux version (64 bit) from http://www.eclipse.org/downloads/
2. Extract the downloaded file and move it to /opt/
3. Create a launcher shortcut for Eclipse through running gksudo gedit /usr/share/applications/eclipse.desktop and paste following content in it:

              [Desktop Entry]
              Name=Eclipse Mars.1 (4.5.1)
              Type=Application
              Exec=/opt/eclipse/eclipse
              Terminal=false
              Icon=/opt/eclipse/icon.xpm
              Comment=Integrated Development Environment
              NoDisplay=false
              Categories=Development;IDE;
              Name[en]=Eclipse

Then, I can open Eclipse from Unity search:

Install Python 3.5 and Packages

I used Anaconda (by Continuum Analytics), which is a free, cross-platform, and easy-to-install all-in-one scientific Python distribution. Anaconda comes with various packages that I’m using, such as NumPy (providing a practical array data structure), SciPy (scientific computing), matplotlib (graphical plotting), pandas (data analysis and statistics), scikit-learn (machine learning), SymPy (symbolic computing), and Jupyter/IPython (efficient interfaces for interactive computing).

Anaconda can be installed through following steps:

1. Go to Anaconda download page , download the installer with my system version (64-bit) and python version (Python 3.5) from Anaconda for Linux
2. Go to the directory where the downloaded file locates (usually Downloads ) and run the command  bash Anaconda3-2.4.1-Linux-x86_64.sh 
3. Follow the instructions to install Anaconda and choose put Anaconda to the system path, so that Anaconda’s Python will be the system default

Anaconda comes with a package manager named conda, which helps me manage myPython packages, environments, and more, please read my another post about installing and using Anaconda.

Install Fcitx for Chinese Language Input

Follow the instructions from post, I set up Fcitx for Chinese Language input:

1. Remove any IBus input methods in the system: Go to System Settings -> Text Entry, remove all entries in the ‘Input sources to use:’ pane, except the default keyboard layout, and remove the keyboard shortcuts for “Switch to next source” and “Switch to previous source” by clicking inside the corresponding boxes on the right and hitting Backspace.
2. Install googlepinyin packages via Software Center or sudo apt-get install:
   fcitx fcitx-googlepinyin
3. Use a terminal (Ctrl + Alt + T) to run: im-config
   When asked if you want to explicitly update the user preferences, select “Yes”, then select fcitx as the default input method framework.
4. Reboot, the a keyboard icon appears in the upper right screen corner, where the input method and skin can be managed.
5. Go to System Settings -> Text Entry, uncheck the ‘Show current input source in the menu bar’, which will hide the IBus input framework.

 

Advertisement

Installing and Managing Python and Packages with Anaconda

 

As more and more Python packages I need to install for my daily work and learn, I get tired of searching and installing individual packages, especially on my Window system, like what I did in how to install scientific Python packages on Windows. I decide to give Anaconda (by Continuum Analytics) a try, what it provides far exceed my expectation and I feel guilty did not try it earlier.

Anaconda is a free, cross-platform, and easy-to-install all-in-one analytic/scientific Python platform. Anaconda not only comes with various packages that I would like to use, such as NumPy, SciPy, matplotlib, pandas, scikit-learn,  and Jupyter/IPython, but also provides more functionalities, like creating and managing environments, installing and updating packages, and so on.

In this post, I describe some basic knowledge on Anaconda I have learned through my experience. If you did not start to use it yet, I highly recommend you a try.

Downloading and Installing

Installing Anaconda is as easy as 1-2-3:

1. Go to Anaconda’s download page (http://continuum.io/downloads)
2. download the right installer for your OS type (Window, OSX, Linux), OS version(32- or 64 bit), and Python version(2.7 or 3.5)
3. Follow the instructions to install Anaconda

You might want to choose put Anaconda to your system path, so it will use Anaconda’s Python as the default python distribution.

Anaconda comes with a package manager named conda, which lets you manage your Python distributions and install new packages.

Managing Environments

Anaconda can help create different isolated Python environments. For example, you might use Python 3.5 as your default distribution, but sometimes you would switch to Python 2 for some rare cases.

Anaconda comes with a graphical launcher that you can use to  manage environments, install packages, start IPython, etc. You can find more details from http://docs.continuum.io/anaconda-launcher/

All these stuff can be realized through conda command. For example, a new environment for Python 2 (named py2, with Python 2.7) can be created through following command:

conda create -n py2 anaconda python=2.7

Then the new environment can be activated through

activate py2 on Windows
source activate py2 on Linux or Mac OSX

, and be deactivated by:

deactivate py2 on Windows
source deactivate py2 on Linux or Mac OSX

NOTE: For Windows system, the activate and deactivate commands do not work in PowerShell, but work in cmd. Here is one potential solution, if you want to keep using your PowerShell: Powershell activate and deactivate #626

Common Commands

Here is a list of frequently used conda commands, and you can see a longer list at the Conda cheet sheet..

• conda info: Displays information about current conda install.
• conda help: Displays the list of conda commands and their help strings.
• conda list: Lists all packages installed in the current environment.
• conda env list: Displays the list of environments installed and the currently active one is marked by a star *.
• conda serarch somepackage: search for a package to see if it is available.
• conda install somepackage: Installs a Python package.
• conda install somepackage=0.7: Installs a specific version of a package.
• conda update somepackage: Updates a Python package to the latest available version.
• conda update anaconda: Updates all packages.
• conda update conda: Updates conda itself.
• conda update --all: Updates all packages.
• conda remove somepackage: Uninstalls a Python package.
• conda remove -n myenv --all: Removes the environment named myenv.
• conda clean -t: Removes the old tarballs that are left over after installation and updates.

 

If the conda install somepackage fails, you can try pip install somepackage instead, which uses the PyPI instead of Anaconda. Many scientific Anaconda packages are easier to install than the corresponding PyPI packages because they are pre-compiled for your platform. However, many packages are available on PyPI but not on Anaconda.

A few references about Anaconda:

• Anaconda websit: https://store.continuum.io/cshop/anaconda/
• Conda user cheet sheet http://conda.pydata.org/docs/_downloads/conda-cheatsheet.pdf
• List of Anaconda packages: http://docs.continuum.io/anaconda/pkg-docs
• Conda main page: http://conda.io/
• Anaconda mailing list: https://groups.google.com/a/continuum.io/forum/#!forum/anaconda
• Conda FAQ: http://conda.pydata.org/docs/faq.html

How to Install Numpy, SciPy, Scikit-learn, Pandas, Matplotlib, and NLTK libraries for Python 3 on Windows

NumPy, SciPy, Pandas, and Matplotlib are fundamental scientific computing and visualization packages with Python. Scikit-learn is a simple and efficient package for data mining and analysis in Python. NLTK (the Natural Language Toolkit) is a leading platform for building Python programs to work with human language data. However, if you are using Python on Windows, it seems not easy to install these packages. Thanks to Christoph Gohlke, who provides the non-official Python extension packages for Windows. With these unofficial packages, there is a simple way to install these libraries on Windows.

For clarity, I’m using Python 3.4.3 on 64-bit Windows 7. The steps described below would also work for 32-bit. Please note, after installed Python, I added the ‘Scripts’ directory in Python package where the ‘pip.exe’ and ‘pip3.exe’ located, in my case the path is ‘C:\Python34\Scripts’, to the PATH environment variables. This step makes my life easier, because I don’t need to navigate to the scripts directory anytime I run ‘pip’ or ‘python’.

Install NumPy, SciPy, Pandas, and Matplotlib

The steps of installation of Numpy, SciPy, Pandas, and Matplotlib are the same. Here I take NumPy as an example:

1. Download appropriate wheel file, in my case, for numpy, it is “numpy-1.10.1+mkl-cp34-none-win_amd64.whl” from the unofficial extension packages site
2. On the command line, navigate to the directory where you saved the wheel file
3. Run pip install numpy-1.10.1+mkl-cp34-none-win_amd64.whl
4. To verify, start python and run

 >>> import numpy  
>>> numpy.__version__

Install Scikit-learn

With a working installation of Numpy and Scipy, it is easy to install scikit-learn through running: pip install -U scikit-learn

Install NLTK

To install NLTK we need to install the Pyyaml package. Follow the steps for installing Numpy above to install Pyyaml first and then NLTK.

References

https://www.codementor.io/numpy/tutorial/installing-numpy-64-bit-windows

http://scikit-learn.org/stable/install.html

Setting up Eclipse for Java API of IBM ILOG CPLEX

After installed IBM ILOG CPLEX Optimization Studio 12.6, I tried the instructions described in IBM Knowledge Center to set up Java APIs for CPLEX and CP in Eclipse, but they do not work completely. Here is what I did to build a java project with CPLEX  and CP Java APIs in Eclipse.

These steps have been done in Eclipse on Window 7, not sure if it works for other Java IDEs or other OSs. It also assumes that the IBM ILOG CPLEX Optimization Studio has already been installed.

• Create a new Java project in Eclipse, through File->New…>Java Project
• Import a java file from the example folder to the ‘src’ folder of the built project.
  • For CPLEX, in my case, they are located at: C:\Program Files\IBM\ILOG\CPLEX_Studio126\cplex\examples\src\java
  • For CP, the examples are located at: C:\Program Files\IBM\ILOG\CPLEX_Studio126\cpoptimizer\examples\src\java
• Include the JAR library to the project, through right click on project then Properties > Java Build Path > Libraries, then Add External JARs.
• Browse to the location ‘oplall.jar’, which is located at C:\Program Files\IBM\ILOG\CPLEX_Studio126\opl\lib in my case. Select this jar file and add it to the library.
• Make sure the CPLEX STUDIO BINARIES is included in the PATH environmental variables. In my case the path is C:\Program Files\IBM\ILOG\CPLEX_Studio126\opl\bin\x64_win64. What I did was defined a system variable with name CPLEX_STUDIO_BINARIES126 and value C:\Program Files\IBM\ILOG\CPLEX_Studio126\opl\bin\x64_win64;C:\Program Files\IBM\ILOG\CPLEX_Studio126\opl\oplide\;C:\Program Files\IBM\ILOG\CPLEX_Studio126\cplex\bin\x64_win64;C:\Program Files\IBM\ILOG\CPLEX_Studio126\cpoptimizer\bin\x64_win64. Then add %CPLEX_STUDIO_BINARIES126% to the PATH.
• Now you can run your project through Run As > Java Application

The last 2 steps are different to the description from above link. In addition, I found that the ‘oplall.jar’ works for both CP and CPLEX.

 

Join Multiple Excel Workbooks through Custom SQL Query in Tableau

Recently I came across the need of joining multiple excel files in Tableau. I did a hard research on how to do it. However, most of the instructions I found were about how to join two tabs in the same excel workbook. In this post, I will describe how to join multiple worksheets from different workbooks, which spent me about one hour to figure out. Please note the instructions here work for Tableau Desktop 9.0 or later.

Scenario

Suppose we have one Excel workbook that contains one worksheet that would be joined with another worksheet in another workbook. For example, there is a ‘Connections’ worksheet in workbook ‘testjoin01.xlsx’, recording the origin, destination, and travel times.

Connections in ‘testjoin01.xlsx’

We want to join it with the ‘Nodes’ worksheet in workbook ‘testjoin02.xlsx’. The sheet stores latitude and longitude of associated nodes.

Nodes in ‘testjoin02.xlsx’

Use Custom SQL to Create the Join

Step 1

Open a new Tableau workbook, select Excel in the Connect To a file section. Find the ‘testjoin01.xlsx’ workbook, and click the drop-down arrow next to Open, and select Open with Legacy Connection.

Step 2

Drag the New Custom SQL table from the left pane to the join area.

Step 3

In the custom SQL query field, copy and paste the LEFT JOIN query similar to the one shown below, change and update to your use case.

SELECT 
a.*,
b.[LAT] AS [OR_LAT], b.[LONG] AS [OR_LONG],
c.[LAT] AS [DE_LAT], c.[LONG] AS [DE_LONG]
FROM(([Connections$] AS a
  LEFT JOIN
   [C:\Users\lf\Desktop\testjoin02.xlsx].[Nodes$] AS b 
      ON a.[Orig] = b.[ICLOC])
  LEFT JOIN
   [C:\Users\lf\Desktop\testjoin02.xlsx].[Nodes$] AS c 
      ON a.[Dest] = c.[ICLOC])

In the SQL query above, nested left joins are used to join the Nodes sheet in the second workbook twice, one for the origin, the other for the destination. Please note, the full path of the second workbook has to be specified in the left joins.

Install and Run Jupyter (IPython) Notebook on Windows

To install Jupyter Notebook, you will need Python installed on your system. I assume that, like me, you already installed the newest Python package on your Windows system and now you want to install and use the Jupyter Notebook.

How to Install Jupyter Notebook

• Add the scripts directory in your Python package where the ‘pip.exe’ and ‘pip3.exe’ located, in my case the path is ‘C:\Python34\Scripts’, to the PATH environment variables.
• Run ‘pip3 install jupyter‘ in the command shell. Use pip instead of pip3 for legacy Python2. Note: if you are using the old cmd.exe shell, I strongly recommend you to switch to Windows PowerShell, which is integrated by default in Windows 7 and 8. The most common filesystem-related commands (like pwd, cd, ls, cp, ps, and so on) it has are the same ones in Unix.

The installation of Jupyter Notebook above will also install the IPython kernel which allows working on notebooks using the Python programming language.

• If the IPython console has been installed correctly, you should be able to run it from the command shell with the ‘ipython' command.
• Sometime it show a warning of readline service is not available. This is because the pyreadline, which is a dependency of IPython providing line-editing features, has not been installed in above installation process. You can run ‘pip install pyreadline‘ to install it.

How to Run the Notebook

1. Go to the notebook project directory and run ‘jupyter notebook‘ or ‘ipython notebook‘ in command shell. If you didn’t select the project directory, the notebook web application will open the directory where you run the command.
2. Use ‘Ctrl + C’ to stop any running server and shut down all kernels.

For detailed information on installation and configurations please go to Jupyter Documentation.

A Generic Comparator Class for Java Collections.sort()

Sort A List of Objects

As a Java programmer, I often need to sort a list of objects. If the object is a primitive type, such as String, Integer, Long, Float, Double, or Date, it is easy to use Collections.sort(). However, to sort a list of user defined objects, which do not implement the Comparable interface, for example, to sort a list of Person objects, as defined below, by id in ascending order, one has to provide a Comparator – an object that encapsulates an ordering.

public class Person {
    //fields
    private int id;
    private String name;
    private Payment pay;
    //constructor
    public Person(String name, int id,
                   int startSal, int startBon){
        this.name = name;
        this.id = id;
        this.pay = new Payment(startSal, startBon);
    }
    //method get name
    public String getName(){
        return name;
    }
    //method get id
    public int getId(){
        return id;
    }
    //method get start salary
    public int getStartSalary(){
        return pay.startSalary;
    }
    //method get start bonus
    public int getStartBonus(){
       return pay.startBonus;
    }
    //inner payment class
    private class Payment{
       int startSalary;
       int startBonus;
       public Payment(int sal, int bon){
          this.startSalary = sal;
          this.startBonus = bon;
       }
    }
}

One possible Comparator class with above aim might be:

import java.util.Comparator;

public class SortPersonById implements Comparator<Person>{
	@Override
	public int compare(Person p1, Person p2) {
		if(p1.getId() > p2.getId()){
			return 1;
		} else if (p1.getId() < p2.getId()){
			return -1;
		} else {
			return 0;
		}
	}
}

Then one can use

 Collections.sort(personList, new SortPersonById()); 

to sort the list personList by id in ascending order.

Generic Comparator

What if the user wants to sort the personList by name instead of the id? or in descending order instead of ascending? It is tedious to write one class for each of these situation. Is there any generic way to it? A GenericComparator class proposed in this post can be used to sort any object by any declared field in any specified order. The reflection technology is used for accessing fields in the class. This generic class can be used to sort lists of primitive as well as user defined objects.

There are two constructors, as shown below. Constructor 1 defines default ascending order and the sort field names. Please note, the varargs format of sort field names are used for different level of fields. For example, in the Person Class above, the first level of payment field is “pay” and the second level of field names in the “pay” field are “startSalary” and “startBonus”. Constructor 2 works in the same way, excepts the user defined sorting order.

public GenericComparator(String... sortFieldNames) {
    this.bAscendingOrder = true;
    this.sfieldNames = sortFieldNames;
}

public GenericComparator(final boolean sortAscending, 
                          String... sortFieldNames) {
    this.bAscendingOrder = sortAscending;
    this.sfieldNames = sortFieldNames;
}

How to Use

An example is posted here to illustrate how to use the GenericComparator class.

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class TestGenericComparator {

 public static void main(String[] args) {
    // Build a list of persons with different names and ids
    List<Person> personList = new ArrayList<Person>();
    personList.add(new Person("Angela", 102, 50000, 5000));
    personList.add(new Person("Mike",101, 65000, 5500));
    personList.add(new Person("Lisa", 104, 75000,4500));
    personList.add(new Person("Bob", 103, 58000, 4300));
    //print initial person list
    printPersonList(personList);

    //sort personList by name field
    Collections.sort(personList, new GenericComparator("name"));
    printPersonList(personList);
    //sort personList by id field in ascending order
    Collections.sort(personList, new GenericComparator(true,"id"));
    printPersonList(personList);
    //sort personList by id field in descending order
    Collections.sort(personList, new GenericComparator(false,"id"));
    printPersonList(personList);
    //sort personList by pay field's start salary
    Collections.sort(personList, new GenericComparator("pay","startSalary"));
    printPersonList(personList);

    //test primitive list
    List<Integer> iList = new ArrayList<Integer>();
    iList.add(12);
    iList.add(15);
    iList.add(13);
    iList.add(20);
    System.out.println(iList);

    //sort iList in descending order
   Collections.sort(iList, new GenericComparator(false));
    System.out.println(iList);
 }

 /**
 * Print person list.
 * @param personList
 */
 private static void printPersonList(List<Person> personList) {
    for(Person p: personList){
        System.out.println(p.getName() + "\t" + p.getId() + "\t"
                       + p.getStartSalary() + "\t" +p.getStartBonus());
    }
    System.out.println("-------------");
 }

}

Execution results:

Angela 102 50000 5000
Mike 101 65000 5500
Lisa 104 75000 4500
Bob 103 58000 4300
-------------
Angela 102 50000 5000
Bob 103 58000 4300
Lisa 104 75000 4500
Mike 101 65000 5500
-------------
Mike 101 65000 5500
Angela 102 50000 5000
Bob 103 58000 4300
Lisa 104 75000 4500
-------------
Lisa 104 75000 4500
Bob 103 58000 4300
Angela 102 50000 5000
Mike 101 65000 5500
-------------
Angela 102 50000 5000
Bob 103 58000 4300
Mike 101 65000 5500
Lisa 104 75000 4500
-------------
[12, 15, 13, 20]
[20, 15, 13, 12]

Detailed source code and implement examples are available through GitHub.

Reference

1. Making a Generic Comparator Class: http://stackoverflow.com/questions/15189949/making-a-generic-comparator-class

2. Generic Comparator in Java: http://myjeeva.com/generic-comparator-in-java.html

Solve Einstein’s Logic Puzzle through Constraint Programming in AIMMS

A brain teaser has been posed by Albert Einstein, who claimed that 98% of population in the world could not figure it out . I have tried with hands on it, unfortunately, I didn’t find a solution within half an hour. Thus, I built a Constraint Programming (CP) model in AIMMS to solve it. If you are interested, try your hand on it first. If you belong to that lucky 2%, please let me know how long it took you. If not, you can check out the CP model below for a solution.

Here is the puzzle, copied from Begent for completeness:

FACTS:

1. There are 5 houses in 5 different colors.
2. In each house lives a person with a different nationality.
3. These 5 owners drink a certain beverage, smoke a certain brand of cigarette and keep a certain pet.
4. No owners have the same pet, brand of cigarette, or drink.

CLUES:

1. The Brit lives in a red house.
2. The Swede keeps a dog.
3. The Dane drinks tea.
4. The green house is on the left of the white house.
5. The green house owner drinks coffee.
6. The person who smokes Pall Mall keeps birds.
7. The owner of the yellow house smokes Dunhill.
8. The man living in the house right in the center drinks milk
9. The Norwegian lives in the first house.
10. The man who smokes Blends lives next to the one who keeps cats.
11. The man who keeps horses lives next to the man who smokes Dunhill.
12. The owner who smokes Camel drinks beer.
13. The German smokes Marlborough.
14. The Norwegian lives next to the blue house.
15. The man who smokes Blends has a neighbor who drinks water.

The question is, who keeps the fish?

Mathematical Modeling

From mathematical perspective, this puzzle can be formulated as a combinatorial optimization problem. It can be converted to a problem that orders 5 sets (Nationality, House, Pet, Drink, and Smoke), each of which has 5 elements. The ordering has to satisfy above facts and clues. Elements in these sets with the same order correspond  to a statement of ‘which person lives in which house, keeps which pet, drinks which beverage and smokes which cigarette‘. Then the question ‘who keeps the fish’ can be answered.

I formulated and solved this puzzle as a Constraint Satisfaction Problem(CSP) in AIMMS. CSP which is a Constraint Programming (CP) model without objective function. The post Benefits of Constraint Programming gives an introduction of CP. Readers are referred to AIMMS-The Language Reference for more details on CP and associated modeling language in AIMMS. The built AIMMS CP model and interface are provided next.

Implementation in AIMMS

A CSP model called ‘Einstein_Puzzle’ was defined as below.

Model Definition

MAIN MODEL Main_Einstein_Puzzle

  DECLARATION SECTION 

    SET:

       identifier   :  Houses

       index        :  h

       definition   :  data {‘red’,’white’,’green’,’yellow’,’blue’} ;

    SET:

       identifier   :  Nationalities

       index        :  n

       definition   :  data {‘Brit’,’Swede’,’Dane’,’Norwegian’,’German’} ;

    SET:

       identifier   :  Drinks

       index        :  d

       definition   :  data {‘tea’,’coffee’,’milk’,’beer’,’water’} ;

    SET:

       identifier   :  Pets

       index        :  p

       definition   :  data {‘dog’,’birds’,’cats’,’horses’,’fish’} ;

    SET:

       identifier   :  Smokes

       index        :  s

       definition   :  data {‘Pall Mall’,’Dunhill’,’Blends’,’Camel’,’Marlborough’} ;

    ELEMENT VARIABLE:

       identifier   :  eV

       range        :  Nationalities ;

    VARIABLE:

       identifier   :  House

       index domain :  h

       range        :  {1..5} ;

    VARIABLE:

       identifier   :  National

       index domain :  n

       range        :  {1..5} ;

    VARIABLE:

       identifier   :  Drink

       index domain :  d

       range        :  {1..5} ;

    VARIABLE:

       identifier   :  Pet

       index domain :  p

       range        :  {1..5} ;

    VARIABLE:

       identifier   :  Smoke

       index domain :  s

       range        :  {1..5} ;

    CONSTRAINT:

       identifier   :  Fact01

       definition   :  CP::AllDifferent(h,House(h)) ;

    CONSTRAINT:

       identifier   :  Fact02

       definition   :  CP::AllDifferent(n, National(n)) ;

    CONSTRAINT:

       identifier   :  Fact03

       definition   :  CP::AllDifferent(d,Drink(d)) ;

    CONSTRAINT:

       identifier   :  Fact04

       definition   :  CP::AllDifferent(p,Pet(p)) ;

    CONSTRAINT:

       identifier   :  Fact05

       definition   :  CP::AllDifferent(s,Smoke(s)) ;

    CONSTRAINT:

       identifier   :  Clue01

       definition   :  National(‘Brit’) = House(‘red’)

       comment      :  “The Brit lives in a red house” ;

    CONSTRAINT:

       identifier   :  Clue02

       definition   :  National(‘Swede’) =Pet(‘dog’)

       comment      :  “The Swede keeps a dog” ;

    CONSTRAINT:

       identifier   :  Clue03

       definition   :  National(‘Dane’) =Drink(‘tea’)

       comment      :  “The Dane drinks tea” ;

    CONSTRAINT:

       identifier   :  Clue04

       definition   :  House(‘green’) = House(‘white’)-1

       comment      :  “The green house is on the left of the white house.” ;

    CONSTRAINT:

       identifier   :  Clue05

       definition   :  House(‘green’) = Drink(‘coffee’)

       comment      :  “The green house owner drinks coffee.” ;

    CONSTRAINT:

       identifier   :  Clue06

       definition   :  Smoke(‘Pall Mall’) = Pet(‘birds’)

       comment      :  “The person who smokes Pall Mall keeps birds.” ;

    CONSTRAINT:

       identifier   :  Clue07

       definition   :  House(‘yellow’) = Smoke(‘Dunhill’)

       comment      :  “The owner of the yellow house smokes Dunhill.” ;

    CONSTRAINT:

       identifier   :  Clue08

       definition   :  Drink(‘milk’) = 3

       comment      :  “The man living in the house right in the center drinks milk” ;

    CONSTRAINT:

       identifier   :  Clue09

       definition   :  National(‘Norwegian’) =1

       comment      :  “The Norwegian lives in the first house.” ;

    CONSTRAINT:

       identifier   :  Clue10

       definition   :  abs(Smoke(‘Blends’)-Pet(‘cats’))=1

       comment      :  “The man who smokes Blend lives next to the one who keeps cats” ;

    CONSTRAINT:

       identifier   :  Clue11

       definition   :  abs(Pet(‘horses’)-Smoke(‘Dunhill’))=1

       comment      :  “The man who keeps horses lives next to the man who smokes Dunhill” ;

    CONSTRAINT:

       identifier   :  Clue12

       definition   :  Smoke(‘Camel’) = Drink(‘beer’)

       comment      :  “The owner who smokes Camel drinks beer” ;

    CONSTRAINT:

       identifier   :  Clue13

       definition   :  National(‘German’) = Smoke(‘Marlborough’)

       comment      :  “The German smokes Marlborough.” ;

    CONSTRAINT:

       identifier   :  Clue14

       definition   :  abs(National(‘Norwegian’)-House(‘blue’))=1

       comment      :  “The Norwegian lives next to the blue house” ;

    CONSTRAINT:

       identifier   :  Clue15

       definition   :  abs(Smoke(‘Blends’)-Drink(‘water’))=1

       comment      :  “The man who smokes Blend has a neighbour who drinks water.” ;

    CONSTRAINT:

       identifier   :  Question

       definition   :  National(ev)=Pet(‘fish’)

       comment      :  “Who owns the pet fish? Result stored in element variable eV” ;

    MATHEMATICAL PROGRAM:

       identifier   :  EinsteinPuzzle

       direction    :  minimize

       constraints  :  AllConstraints

       variables    :  AllVariables

       type         :  CSP ;

  ENDSECTION  ;

  PROCEDURE

    identifier :  MainInitialization

  ENDPROCEDURE  ;

  PROCEDURE

    identifier :  MainExecution

    body       :  

      solve EinsteinPuzzle;

      

  ENDPROCEDURE  ;

  PROCEDURE

    identifier :  MainTermination

    body       :  

      return DataManagementExit();

  ENDPROCEDURE  ;

ENDMODEL Main_Einstein_Puzzle ;

Model Interface

Below shows the model interface and obtained solution. From the solution, one can conclude that the German keeps fish. In addition, one can also conclude other facts, such as ‘the Norwegian lives in yellow house, keeps cats, drinks water, and smokes Dunhill’.

Question:

Is this solution unique? Can you find out other feasible solution?

Please feel free go leave your answers, comments or suggestions. Any feedback is welcome.

Benefits of Constraint Programming

Constraints Programming (CP) is a relatively new, but evolving rapidly, paradigm in Operation Research. It was derived from Computer Science – Logic Programming, Graph Theory, and Artificial Intelligence. Like a Mathematical Programming (MP), such as Linear Programming, Integer Programming, or Nonlinear Program, CP works with the same concepts of decision variables, constraints, and/or objective function. Because of its flexible modeling language and powerful search strategy, CP is a powerful and easy-to-use optimization technology to solve highly combinatorial optimization problems, such as scheduling problems, timetabling problems, sequencing problems, and allocation or rostering problems. These problems might be difficult to solve for MP, due to: 1) constraints that are nonlinear in nature; 2) a con-convex solution space that contains many locally optimal solutions; 3) multiple disjunctions, which result in poor information returned by a linear relaxation of the problem. This post tries to summarize the major benefits of CP in contrast with MP models in modeling and solving standpoints.

Intuitive Modeling Language

Comparing to MP, CP allows more flexible modeling language, which is be more intuitive and closer to natural language. Virtually any expression over the variables is allowed.

Wide Types of Decision Variables

The decision variables types include the classical binary, integer, and continuous. Unlike in integer programming, where the range of a variable is specified and maintained as an interval, in constraint programming, the variables are maintained explicitly as a set of elements that is called domain.  In addition, CP can model special “structured” variable types. One example of this special variable types is the set variables that take a set of elements as value. Another example is activities or interval variables that are suitable to model the scheduling and sequence problem.

Nearly All Kinds of Constraints Expressions

With the explicit element representation, CP allows wider types of constraints to be defined by arbitrary expressions through algebraic or logical operators. Specially, logical constraints, such as AND, OR, NOT and IF-THEN, and ‘global constraints’, such as FORALL, EXISTS, SUM, ALLDIFFERENT can be easily formulated in CP. Here are some example expressions:

Arithmetic Expressions: x²·(y²-z) ≥ 25 + x²· max(x, y, z)

Extensional Constraints(‘Table’ Constraints): (x, y, z) in MyTupleSet

Variables as Subscripts (‘Element’ Constraints): y = cost(x), where y and x are variables, ‘cost’ is an array of parameters.

Reasoning with meta-constraints: ∑i (xi > Ti) ≤ 5

Logical rations in which (meta-) constraints can be mixed: if ((x < y) OR (y < z)) then c = min(x, y)

Global Constraints: Alldifferent(x1, x2, …, xn)

In general, CP contraints can be non-linear, non-differentiable, and discontinuous.

With or Without Objective Function

Depending on with or without an objective function, constraint programming models can be categorized into two types: constraint optimization problem (COP) with an objective function and constraint satisfaction problem (CSP) without an objective function. COP aims to find an optimal solution, while CSP can provide a feasible solution or proves that no solution exists.

Powerful Search Strategy

The solving process underlying CP involves a systematic search over a search space. Initially, the search space contains all combinations of the values in the domains of all decision variables. To avoid exploring the entire search space, CP first removes inconsistent values from the domains of the variables involved in each constraint. Then a search strategy (depth first, width first or multi-start) is applied to guide the search for a solution within the reduced search space. The search process can be viewed as traversing a tree, where the root is the starting point, a leaf node is a combination of values in the reduced search space and each branch represents a move (branching) within the search. Each leaf node is evaluated to determine if it will produce a feasible solution. A solution is a set of value assignments to the decision variables such that each variable is assigned to exactly one value from its domain.

Combination With Other Solution Framework

Constraint programming can also be used as a fast generator of feasible solutions. This can be extremely useful in combination with other models and engines, for instance to implement column generation for a complex optimization model.

References

1. AIMMS Language Reference – Constraint Programming 
2. Willem-Jan van Hoeve. Introduction to Constraint Programming and Operations Research Techniques in Constraint Programming. ACP Summer School on Constraint Programming, 2012.