I ran into an interesting problem recently, similar to the coloring problem.
There are 24 grids that can be colored for us. There are three types of coloring, namely: yellow, blue, and red. The number of grids occupied by each color is different for each color, respectively, yellow occupies 1 2 squares for blue and 4 for red.
In addition, we have the following restrictions: (1) Each color cannot be colored continuously. If you want to color continuously, you must leave a blank grid between the two colorings. (2) Each coloring must be colored at least once and a maximum of 6 times. (3) All the grids occupied by all coloring cannot exceed the upper limit of 24.
The goal of our solution is: what is the maximum number of times of coloring?
We abstract the problem into a MIP model. build a model
We set 72 variables, which is Xij. When X11 is 1, it means that the first grid is occupied by the first resource, but this design has a flaw, and it is impossible to accurately know how the number of grids is colored by solving Xij. . This part is an issue to be improved in the future.
(1.1) represents the optimization objective, the sum of all Xij is the largest, which represents the largest accumulated coloring times
From (1.2) onwards are constraints.
(1.2) means that each grid can only be colored by one type
(1.3) Represents that the types of coloring between adjacent ones cannot be the same
(1.4) The total number of grids occupied by all coloring types cannot exceed 24
(1.5) - (1.7) means that the number of each coloring business is at least 1 and not more than 6
(1.8) means that i and j are both integers, and Xij can only take 0 or 1
The Java code is as follows (rough, basic functions can be completed):
public optimal() {
try {
GRBEnv grbEnv = new GRBEnv("coloring");
grbModel =new GRBModel(grbEnv);
grbVars = new ArrayList<>();
for (int i = 0; i < 24; i++) {
for (int j = 0; j < 3; j++) {
x[i][j] = grbModel.addVar(0,1,0,GRB.BINARY,"x_"+(i+1)+"_"+(j+1));
grbVars.add(x[i][j]);
x_total[i*3 + j] = x[i][j];
}
}
/*constr1*/
for (int i = 0; i < 24; i++) {
GRBLinExpr expr1 = new GRBLinExpr();
expr1.addTerms(new double[]{1,1,1},x[i]);
grbModel.addConstr(expr1,LESS_EQUAL,1,"expr1"+i);
}
/*constr2*/
for (int i = 0; i < 23; i++) {
for (int j = 0; j < 3 ; j++) {
GRBLinExpr expr2 = new GRBLinExpr();
GRBVar[] grbVars1 = {x[i][j],x[i+1][j]};
expr2.addTerms(new double[]{1,1},grbVars1);
grbModel.addConstr(expr2,LESS_EQUAL,1,"expr2_"+i+j);
}
}
/*constr3*/
GRBLinExpr expr3 = new GRBLinExpr();
double[] expr3_coffe = new double[72];
for (int i = 0; i < 24; i++) {
expr3_coffe[i*3 + 0] = 1;
expr3_coffe[i*3 + 1] = 2;
expr3_coffe[i*3 + 2] = 4;
}
expr3.addTerms(expr3_coffe,x_total);
grbModel.addConstr(expr3,LESS_EQUAL,24,"expr3");
/*constr4*/
double[] expr4_coffe = new double[24];
for (int i = 0; i < 24; i++) {
expr4_coffe[i] = 1;
}
GRBVar[][] grbVars_main = new GRBVar[3][24];
GRBVar[] grbVars1 = new GRBVar[24];
GRBVar[] grbVars2 = new GRBVar[24];
GRBVar[] grbVars4 = new GRBVar[24];
for (int i = 0; i < 24; i++) {
grbVars1[i] = x[i][0];
grbVars2[i] = x[i][1];
grbVars4[i] = x[i][2];
}
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 24; j++) {
if(i == 0){
grbVars_main[i][j] = grbVars1[j];
} else if (i == 1) {
grbVars_main[i][j] = grbVars2[j];
}else {
grbVars_main[i][j] = grbVars4[j];
}
}
}
for (int i = 0; i < 3; i++) {
GRBLinExpr expr4 = new GRBLinExpr();
expr4.addTerms(expr4_coffe,grbVars_main[i]);
if(i == 0){
grbModel.addConstr(0,LESS_EQUAL,expr4,"expr4_"+i+"_"+1);
grbModel.addConstr(expr4,LESS_EQUAL,5,"expr4_"+i+"_"+2);
}else if(i == 1){
grbModel.addConstr(0,LESS_EQUAL,expr4,"expr4_"+i+"_"+1);
grbModel.addConstr(expr4,LESS_EQUAL,3,"expr4_"+i+"_"+2);
}else {
grbModel.addConstr(0,LESS_EQUAL,expr4,"expr4_"+i+"_"+1);
grbModel.addConstr(expr4,LESS_EQUAL,3,"expr4_"+i+"_"+2);
}
}
/*target*/
double[] target_coffe = new double[72];
for (int i = 0; i < 72; i++) {
target_coffe[i] = 1;
}
GRBLinExpr target = new GRBLinExpr();
target.addTerms(target_coffe,x_total);
grbModel.setObjective(target,GRB.MAXIMIZE);
grbModel.optimize();
int type1_count = 0;
int type2_count = 0;
int type3_count = 0;
int seq_ini[] = new int[72];
int seq_final[] = new int[(int) grbModel.get(GRB.DoubleAttr.ObjVal)];
for (int i = 0; i < x_total.length; i++) {
if(x_total[i].get(GRB.DoubleAttr.X) == 1){
if(i % 3 == 0){
type1_count++;
seq_ini[i] = 1;
} else if (i % 3 == 1) {
type2_count++;
seq_ini[i] = 2;
}else {
type3_count++;
seq_ini[i] = 4;
}
}
}
int temp = 0;
for (int i = 0; i < seq_ini.length; i++) {
if(seq_ini[i] != 0){
seq_final[temp] = seq_ini[i];
temp++;
}
}
//output result
System.out.println("The optimal solution is:" + grbModel.get(GRB.DoubleAttr.ObjVal));
System.out.println("Type1 The quantity is:"+type1_count );
System.out.println("Type2 The quantity is:"+type2_count );
System.out.println("Type3 The quantity is:"+type3_count );
System.out.println("The order of business is:"+ Arrays.toString(seq_final));
for (int i = 0; i < x_total.length; i++) {
System.out.println(x_total[i].get(GRB.StringAttr.VarName) + "=" +
x_total[i].get(GRB.DoubleAttr.X));
}
//Working with models and environments
grbModel.dispose();
grbEnv.dispose();
}catch (Exception e){
e.printStackTrace();
}
}