# Author     : Manfred Scheucher and Paul Tabatabai
# Date       : Jun 29 2015
# Description: This python script generates an LP which can be solved by an
#              LP-solver. The following command gives an example how to
#              use this script with GLPK:
#                     python b.py 5 > 5b.lp && glpsol --lp 5.lp

from sys import argv
from itertools import combinations

assert(1^1==0) # use python, not sage

def b(x):
	return (n*'0'+bin(x)[2:])[-n:] # binary rep. with leading zeroes

def e(x,d):
	return " e_"+b(x)+"_"+b(x+2**d)

n = int(argv[1])
N = 2**n

i = 0

print "Maximize"
print " obj: "+'-'.join(['edgecount']+[e(x,d) for x in range(N) for d in range(n) if x^(2**d) > x])

print "Subject To"
print " asdf: edgecount = "+str(n*N/2)
for x in range(N):
	for d1,d2 in combinations(range(n),2):
		D1=2**d1
		D2=2**d2
		if x^D1 > x and x^D2 > x:
			print " c"+str(i)+":"+'+'.join([e(x,d1),e(x,d2),e(x+D1,d2),e(x+D2,d1)])+">= 1"
			i+=1

E = {}

for d1 in range(n):
	A = [(x,d2) for x in range(N) for d2 in range(n) if d1!=d2 and x^(2**d1) > x and x^(2**d2) > x]
	B = [(x,d2) for x in range(N) for d2 in range(n) if d1!=d2 and x^(2**d1) < x and x^(2**d2) > x]

	print " d"+str(i)+":"+'+'.join([e(x,d) for (x,d) in A])+'-'+'-'.join([e(x,d) for (x,d) in B])+"<= 0"
	i+=1

for d in range(1,n):
	A = [(x,d) for x in range(N) if x^(2**d) < x]
	B = [(x,d-1) for x in range(N) if x^(2**(d-1)) < x] # prev dimension

	print " e"+str(i)+":"+'+'.join([e(x,d) for (x,d) in A])+'-'+'-'.join([e(x,d) for (x,d) in B])+"<= 0"
	i+=1

print "Integer"
print " edgecount"
print "Binary"
for x in range(N):
	for d in range(n):
		print e(x,d)

print "End"