#define ACCS 5
#define MAXCOST 100000
#define MUSTSETS 4
#define N 20
#define TOTEX 16
#define TOTMUST 15
#define TOTPRIN 15

continuous Article[N], Z;

double lo[N], hi[N], cost[N], profit[N];
double lwbnds[MUSTSETS];

int accs[ACCS], prinsz[ACCS];
int exsz[N], exindices[TOTEX];
int mustsz[MUSTSETS], mustindices[TOTMUST];
int prinindices[TOTPRIN], ratio[TOTPRIN];

data()	// As in Tables 10.2 - 10.5
{
cost =	{30,21,20,14,13,2,15,6,1,9,
		12,3,2,4,3,2,5,6,1,9};

profit =	{45,11,19,14,13,12,15,6,8,9,
		10,11,12,24,13,18,25,6,8,9};

lo =		{100,200,300,300,200,100,200,100,100,120,
		100,200,300,300,200,100,200,100,100,120};

hi =		{300,400,500,600,600,500,400,400,700,520,
		300,400,500,600,600,500,400,400,700,520};

mustindices = { 0, 1, 2, 3, 4, 5, 6, 1, 4, 9, 11, 12, 16, 17, 18 };

mustsz = { 3, 4, 4, 4 };

lwbnds = { 500, 400, 300, 200 };

prinindices = {2, 3, 4, 5, 7, 10, 11, 12, 13, 14, 15, 15, 16 };

ratio = {.5, .5, .6, .22, .44, .55, .66, .77, .33, .44, .55, .33, .66 };

accs = {8, 9, 17, 18, 19 };

prinsz = {3, 2, 3, 3, 2 };

exindices = { 1, 2, 5, 6, 6, 11, 12, 13, 4, 13, 15, 16, 16, 2, 15, 6 };

exsz = { 2, 2, 4, 4, 0, 0, 0, 0, 0, 0, 2, 2, 0, 0, 0, 0, 0, 0, 0, 0 };
}

basic_constraints()
{
	and(int i=0;i<N;i++) 
		Article[i] <= hi[i];
	sigma(int i=0;i<N;i++) cost[i]*Article[i] <= MAXCOST;
	Z == sigma(int i=0;i<N;i++) profit[i]*Article[i];
}

acc_constraints()
{	
int begin,end;

	end = 0;
	and(int i=0;i<ACCS;i++) {
		begin = end; 
		end = end + prinsz[i];
		Article[accs[i]] >= 
			sigma(int j=begin;j<end;j++)
					ratio[j]*Article[prinindices[j]];
	}
}

mustcarrysome()
{
int begin, end;

	end = 0;
	and(int k=0;k<MUSTSETS;k++) {
		begin = end;
		end = end + mustsz[k];
		lwbnds[k] <=
			sigma(int j=begin;j<end;j++)
					Article[mustindices[j]];
	}
}

random_access()
{
	and(int i=1;i<N;i++) 
		exsz[i] = exsz[i] + exsz[i-1]; 
}

setup()
{
	basic_constraints();
	acc_constraints();
	mustcarrysome();
	random_access();
}

carry(continuous Item, double low, int begin,end)
{
	Item >= low; 
	and(int j=begin;j<end;j++) 
		Article[exindices[j]] == 0;
}

donotcarry(continuous Item)
{
	Item == 0;
}

quick(continuous Item, double low, int begin,end)
{
double max_when_in,max_when_out;
 
	if not {
		donotcarry(Item);
		max: Z;
		max_when_out = wp(Z);
	}
	then {
		carry(Item,low,begin,end);
		return;
	}
	if not {
		carry(Item,low,begin,end);
		max: Z;
		max_when_in = wp(Z);
	}
	then {
 		donotcarry(Item);
		return;
	}
 
 	if max_when_in > max_when_out;
	then carry(Item,low,begin,end);
	else donotcarry(Item);
}

hill_climb(double & bluff)
{
	and(int i=0;i<N;i++)
		if i == 0;
		then quick(Article[i],lo[i],i,exsz[i]);
		else quick(Article[i],lo[i],exsz[i-1],exsz[i]);
	max: Z;
	bluff = wp(Z);
}

search()
{
	and(int i=0;i<N;i++) 
		if i == 0;
		then decide(Article[i],lo[i],i,exsz[i]);
		else 
		decide(Article[i],lo[i],exsz[i-1],exsz[i]);
}

decide(continuous Item, double low, int begin,end)
{
	either carry(Item,low,begin,end); 	
	or donotcarry(Item); 
}

output()
{
	and(int i=0;i<N;i++) 
		printf ("Purchase %.0f of item %d \n", Article[i], i);
}

2lp_main()
{
double bluff;

	data();
	setup();

	if not hill_climb(bluff);
	then bluff = 0.0;	
	else printf("Hillclimb found a bluff of %f\n",bluff);
	Z >= bluff;

	if 
		find_max: Z; 
		subject_to 
			search();
	then output();
	else printf("No solution can be found\n");
}
 