ILP Part 76 — Dead ends – Random IT Utensils

This is the seventieth sixth part of the ILP series. For your convenience you can find other parts in the table of contents in Part 1 – Boolean algebra

Today we are going to solve Ślepe zaułki (Dead ends). We have a board with shapes. We need to choose shapes to build a one-lane road from start to end, going through all circles. Shapes with triangles must be selected as well but they must be in dead ends.

Data model:

public class Field{
	public IVariable SelectedInPath {get;set;}
	public IVariable SelectedShape {get;set;}
	public IVariable Up {get;set;}
	public IVariable Down {get;set;}
	public IVariable Left {get;set;}
	public IVariable Right {get;set;}
	public IVariable[] AllDirections { get { return new IVariable[]{Up, Down, Left, Right}; } }
	public IVariable DirectionsCount {get;set;}
	public IVariable Identifier {get;set;}	
	public IVariable LowerNeighbourCount {get;set;}	
}

public class Field{

public IVariable SelectedInPath {get;set;}

public IVariable SelectedShape {get;set;}

public IVariable Up {get;set;}

public IVariable Down {get;set;}

public IVariable Left {get;set;}

public IVariable Right {get;set;}

public IVariable[] AllDirections { get { return new IVariable[]{Up, Down, Left, Right}; } }

public IVariable DirectionsCount {get;set;}

public IVariable Identifier {get;set;}

public IVariable LowerNeighbourCount {get;set;}

}

SelectedInPath indicates whether given field is on the path from start to end. SelectedShape indicates whether this field is in a selected shape. Next, we have couple variables for directions (as usual). Identifier and LowerNeighbourCount are for building a connected graph representing the path.

Solution:

// Start - 1
// End - 2
// Circle - 3
// Triangle - 4
var board = new int[][]{
	new int[]{1,0,0,0,0,3},
	new int[]{0,0,0,0,0,0},
	new int[]{0,3,0,0,0,0},
	new int[]{4,0,0,0,0,0},
	new int[]{0,0,4,0,0,0},
	new int[]{0,0,0,0,0,2}
};
var shapes = new int[][]{
	new int[]{1,1,2,3,3,3},
	new int[]{4,2,2,5,6,3},
	new int[]{4,7,7,5,6,3},
	new int[]{8,9,9,10,11,12},
	new int[]{8,13,10,10,11,12},
	new int[]{13,13,14,14,11,12}
};

var height = board.Length;
var width = board[0].Length;

// Create fields
var fields = board.Select(r => r.Select(c => new Field{
	SelectedInPath = solver.CreateAnonymous(Domain.BinaryInteger),
	SelectedShape = solver.CreateAnonymous(Domain.BinaryInteger),
	Up = solver.CreateAnonymous(Domain.BinaryInteger),
	Down = solver.CreateAnonymous(Domain.BinaryInteger),
	Left = solver.CreateAnonymous(Domain.BinaryInteger),
	Right = solver.CreateAnonymous(Domain.BinaryInteger),
	Identifier = solver.CreateAnonymous(Domain.PositiveOrZeroInteger)
}).ToArray()).ToArray();

// Block invalid directions
for(int row=0;row<height;++row){
	for(int column=0;column<width;++column){
		if(row == 0)fields[row][column].Up.Set<Equal>(solver.FromConstant(0));
		if(row == height - 1)fields[row][column].Down.Set<Equal>(solver.FromConstant(0));
		if(column == 0)fields[row][column].Left.Set<Equal>(solver.FromConstant(0));
		if(column == width - 1)fields[row][column].Right.Set<Equal>(solver.FromConstant(0));
	}
}

// Match direction neighbours
for(int row=0;row<height;++row){
	for(int column=0;column<width;++column){
		if(row > 0)fields[row][column].Up.Set<Equal>(fields[row-1][column].Down);
		if(row < height - 1)fields[row][column].Down.Set<Equal>(fields[row+1][column].Up);
		if(column > 0)fields[row][column].Left.Set<Equal>(fields[row][column-1].Right);
		if(column < height - 1)fields[row][column].Right.Set<Equal>(fields[row][column+1].Left);
	}
}

// Set Selected properly
for(int row=0;row<height;++row){
	for(int column=0;column<width;++column){
		fields[row][column].SelectedInPath.Set<Equal>(solver.Operation<Disjunction>(fields[row][column].AllDirections));
	}
}
		
// Calculate lower neighbours
for(int row=0;row<height;++row){
	for(int column=0;column<width;++column){
		var result = solver.FromConstant(0);
		var self = fields[row][column].Identifier;
		if(row > 0)result = result.Operation<Addition>(fields[row][column].Up.Operation<Conjunction>(fields[row-1][column].Identifier.Operation<IsLessThan>(self)));
		if(row < height - 1)result = result.Operation<Addition>(fields[row][column].Down.Operation<Conjunction>(fields[row+1][column].Identifier.Operation<IsLessThan>(self)));
		if(column > 0)result = result.Operation<Addition>(fields[row][column].Left.Operation<Conjunction>(fields[row][column-1].Identifier.Operation<IsLessThan>(self)));
		if(column < width - 1)result = result.Operation<Addition>(fields[row][column].Right.Operation<Conjunction>(fields[row][column+1].Identifier.Operation<IsLessThan>(self)));
		
		fields[row][column].LowerNeighbourCount = result;
	}
}

// Make fields having correct number of neighbours
for(int row=0;row<height;++row){
	for(int column=0;column<width;++column){
		if(board[row][column] == 1){
			fields[row][column].LowerNeighbourCount.Set<Equal>(solver.FromConstant(0));
		}else{
			fields[row][column].SelectedInPath.Operation<MaterialImplication>(fields[row][column].LowerNeighbourCount.Operation<IsEqual>(solver.FromConstant(1))).Set<Equal>(solver.FromConstant(1));
		}
	}
}

// Propagate identifiers
for(int row=0;row<height;++row){
	for(int column=0;column<width;++column){
		List<Tuple<IVariable, IVariable>> neighbours = new List<Tuple<IVariable, IVariable>>();
		
		Field self = fields[row][column];
		
		if(row > 0)neighbours.Add(Tuple.Create(fields[row-1][column].Identifier, self.Up));
		if(row < height - 1)neighbours.Add(Tuple.Create(fields[row+1][column].Identifier, self.Down));
		if(column > 0)neighbours.Add(Tuple.Create(fields[row][column-1].Identifier, self.Left));
		if(column < width - 1)neighbours.Add(Tuple.Create(fields[row][column+1].Identifier, self.Right));
		
		
		foreach(var n in neighbours){
			var difference = self.Identifier.Operation<Subtraction>(n.Item1).Operation<AbsoluteValue>();
			
			n.Item2.Operation<MaterialImplication>(difference.Operation<IsEqual>(solver.FromConstant(1))).Set<Equal>(solver.FromConstant(1));
		}
		
		foreach(var n1 in neighbours){
			foreach(var n2 in neighbours){
				if(n1.Item1 == n2.Item1)continue;
				var difference = n1.Item1.Operation<Subtraction>(n2.Item1).Operation<AbsoluteValue>();
				n1.Item2.Operation<Conjunction>(n2.Item2).Operation<MaterialImplication>(difference.Operation<IsEqual>(solver.FromConstant(2))).Set<Equal>(solver.FromConstant(1));
			}
		}
	}
}

// Make sure shape is filled
foreach(var shape in shapes.SelectMany(r => r).Distinct()){
	List<IVariable> shapeFields = new List<IVariable>();
	
	for(int row=0;row<height;++row){
		for(int column=0;column<width;++column){
			if(shapes[row][column] == shape){
				shapeFields.Add(fields[row][column].SelectedShape);
			}
		}
	}
	
	solver.Operation<Addition>(
		solver.Operation<Conjunction>(shapeFields.ToArray()),
		solver.Operation<Disjunction>(shapeFields.ToArray()).Operation<BinaryNegation>()
	).Set<Equal>(solver.FromConstant(1));
}

// Make sure S, G, circles and traingles are selected
for(int row=0;row<height;++row){
	for(int column=0;column<width;++column){
		if(board[row][column] > 0){
			fields[row][column].SelectedShape.Set<Equal>(solver.FromConstant(1));
			fields[row][column].SelectedInPath.Set<Equal>(solver.FromConstant(board[row][column] == 4 ? 0 : 1));
		}
	}
}

// Path can be on selected shapes only
for(int row=0;row<height;++row){
	for(int column=0;column<width;++column){
		fields[row][column].SelectedInPath.Set<LessOrEqual>(fields[row][column].SelectedShape);
	}
}

// Make sure path is "one lane only"
for(int row=0;row<height-1;++row){
	for(int column=0;column<width-1;++column){
		solver.Operation<Addition>(
			fields[row][column].SelectedShape,
			fields[row][column+1].SelectedShape,
			fields[row+1][column].SelectedShape,
			fields[row+1][column+1].SelectedShape
		).Set<LessOrEqual>(solver.FromConstant(3));
	}
}
		
solver.Solve();

for(int row=0;row<height;++row){
	for(int column=0;column<width;++column){
		Console.Write(board[row][column] + ",");
	}
	Console.WriteLine();
}
Console.WriteLine();

for(int row=0;row<height;++row){
	for(int column=0;column<width;++column){
		Console.Write(solver.GetValue(fields[row][column].SelectedInPath) + ",");
	}
	Console.WriteLine();
}
Console.WriteLine();

for(int row=0;row<height;++row){
	for(int column=0;column<width;++column){
		Console.Write(solver.GetValue(fields[row][column].SelectedShape) + ",");
	}
	Console.WriteLine();
}
Console.WriteLine();

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

// Start - 1

// End - 2

// Circle - 3

// Triangle - 4

var board = new int[][]{

new int[]{1,0,0,0,0,3},

new int[]{0,0,0,0,0,0},

new int[]{0,3,0,0,0,0},

new int[]{4,0,0,0,0,0},

new int[]{0,0,4,0,0,0},

new int[]{0,0,0,0,0,2}

};

var shapes = new int[][]{

new int[]{1,1,2,3,3,3},

new int[]{4,2,2,5,6,3},

new int[]{4,7,7,5,6,3},

new int[]{8,9,9,10,11,12},

new int[]{8,13,10,10,11,12},

new int[]{13,13,14,14,11,12}

};

var height = board.Length;

var width = board[0].Length;

// Create fields

var fields = board.Select(r => r.Select(c => new Field{

SelectedInPath = solver.CreateAnonymous(Domain.BinaryInteger),

SelectedShape = solver.CreateAnonymous(Domain.BinaryInteger),

Up = solver.CreateAnonymous(Domain.BinaryInteger),

Down = solver.CreateAnonymous(Domain.BinaryInteger),

Left = solver.CreateAnonymous(Domain.BinaryInteger),

Right = solver.CreateAnonymous(Domain.BinaryInteger),

Identifier = solver.CreateAnonymous(Domain.PositiveOrZeroInteger)

}).ToArray()).ToArray();

// Block invalid directions

for(int row=0;row<height;++row){

for(int column=0;column<width;++column){

if(row == 0)fields[row][column].Up.Set<Equal>(solver.FromConstant(0));

if(row == height - 1)fields[row][column].Down.Set<Equal>(solver.FromConstant(0));

if(column == 0)fields[row][column].Left.Set<Equal>(solver.FromConstant(0));

if(column == width - 1)fields[row][column].Right.Set<Equal>(solver.FromConstant(0));

}

// Match direction neighbours

for(int row=0;row<height;++row){

for(int column=0;column<width;++column){

if(row > 0)fields[row][column].Up.Set<Equal>(fields[row-1][column].Down);

if(row < height - 1)fields[row][column].Down.Set<Equal>(fields[row+1][column].Up);

if(column > 0)fields[row][column].Left.Set<Equal>(fields[row][column-1].Right);

if(column < height - 1)fields[row][column].Right.Set<Equal>(fields[row][column+1].Left);

}

// Set Selected properly

for(int row=0;row<height;++row){

for(int column=0;column<width;++column){

fields[row][column].SelectedInPath.Set<Equal>(solver.Operation<Disjunction>(fields[row][column].AllDirections));

}

// Calculate lower neighbours

for(int row=0;row<height;++row){

for(int column=0;column<width;++column){

var result = solver.FromConstant(0);

var self = fields[row][column].Identifier;

if(row > 0)result = result.Operation<Addition>(fields[row][column].Up.Operation<Conjunction>(fields[row-1][column].Identifier.Operation<IsLessThan>(self)));

if(row < height - 1)result = result.Operation<Addition>(fields[row][column].Down.Operation<Conjunction>(fields[row+1][column].Identifier.Operation<IsLessThan>(self)));

if(column > 0)result = result.Operation<Addition>(fields[row][column].Left.Operation<Conjunction>(fields[row][column-1].Identifier.Operation<IsLessThan>(self)));

if(column < width - 1)result = result.Operation<Addition>(fields[row][column].Right.Operation<Conjunction>(fields[row][column+1].Identifier.Operation<IsLessThan>(self)));

fields[row][column].LowerNeighbourCount = result;

}

// Make fields having correct number of neighbours

for(int row=0;row<height;++row){

for(int column=0;column<width;++column){

if(board[row][column] == 1){

fields[row][column].LowerNeighbourCount.Set<Equal>(solver.FromConstant(0));

}else{

fields[row][column].SelectedInPath.Operation<MaterialImplication>(fields[row][column].LowerNeighbourCount.Operation<IsEqual>(solver.FromConstant(1))).Set<Equal>(solver.FromConstant(1));

}

// Propagate identifiers

for(int row=0;row<height;++row){

for(int column=0;column<width;++column){

List<Tuple<IVariable, IVariable>> neighbours = new List<Tuple<IVariable, IVariable>>();

Field self = fields[row][column];

if(row > 0)neighbours.Add(Tuple.Create(fields[row-1][column].Identifier, self.Up));

if(row < height - 1)neighbours.Add(Tuple.Create(fields[row+1][column].Identifier, self.Down));

if(column > 0)neighbours.Add(Tuple.Create(fields[row][column-1].Identifier, self.Left));

if(column < width - 1)neighbours.Add(Tuple.Create(fields[row][column+1].Identifier, self.Right));

foreach(var n in neighbours){

var difference = self.Identifier.Operation<Subtraction>(n.Item1).Operation<AbsoluteValue>();

n.Item2.Operation<MaterialImplication>(difference.Operation<IsEqual>(solver.FromConstant(1))).Set<Equal>(solver.FromConstant(1));

}

foreach(var n1 in neighbours){

foreach(var n2 in neighbours){

if(n1.Item1 == n2.Item1)continue;

var difference = n1.Item1.Operation<Subtraction>(n2.Item1).Operation<AbsoluteValue>();

n1.Item2.Operation<Conjunction>(n2.Item2).Operation<MaterialImplication>(difference.Operation<IsEqual>(solver.FromConstant(2))).Set<Equal>(solver.FromConstant(1));

}

// Make sure shape is filled

foreach(var shape in shapes.SelectMany(r => r).Distinct()){

List<IVariable> shapeFields = new List<IVariable>();

for(int row=0;row<height;++row){

for(int column=0;column<width;++column){

if(shapes[row][column] == shape){

shapeFields.Add(fields[row][column].SelectedShape);

}

solver.Operation<Addition>(

solver.Operation<Conjunction>(shapeFields.ToArray()),

solver.Operation<Disjunction>(shapeFields.ToArray()).Operation<BinaryNegation>()

).Set<Equal>(solver.FromConstant(1));

}

// Make sure S, G, circles and traingles are selected

for(int row=0;row<height;++row){

for(int column=0;column<width;++column){

if(board[row][column] > 0){

fields[row][column].SelectedShape.Set<Equal>(solver.FromConstant(1));

fields[row][column].SelectedInPath.Set<Equal>(solver.FromConstant(board[row][column] == 4 ? 0 : 1));

}

// Path can be on selected shapes only

for(int row=0;row<height;++row){

for(int column=0;column<width;++column){

fields[row][column].SelectedInPath.Set<LessOrEqual>(fields[row][column].SelectedShape);

}

// Make sure path is "one lane only"

for(int row=0;row<height-1;++row){

for(int column=0;column<width-1;++column){

solver.Operation<Addition>(

fields[row][column].SelectedShape,

fields[row][column+1].SelectedShape,

fields[row+1][column].SelectedShape,

fields[row+1][column+1].SelectedShape

).Set<LessOrEqual>(solver.FromConstant(3));

}

solver.Solve();

for(int row=0;row<height;++row){

for(int column=0;column<width;++column){

Console.Write(board[row][column] + ",");

}

Console.WriteLine();

}

Console.WriteLine();

for(int row=0;row<height;++row){

for(int column=0;column<width;++column){

Console.Write(solver.GetValue(fields[row][column].SelectedInPath) + ",");

}

Console.WriteLine();

}

Console.WriteLine();

for(int row=0;row<height;++row){

for(int column=0;column<width;++column){

Console.Write(solver.GetValue(fields[row][column].SelectedShape) + ",");

}

Console.WriteLine();

}

Console.WriteLine();

In lines 5-23 we define an input.

In lines 26-34 we create variables representing the model.

Next, we make sure directions for the path are propagated okay (lines 36-44, 46-54, 56-61).

Next, we calculate lower neighbours. We propagate an identifier through the graph (distance from the source) and here we just check directions and calculate neighbours with lower identifier. Next, in lines 77-86 we make sure the source has no lower neighbours and other fields on the path do. This is to make sure the path is connected.

Next, in 88-115 we propagate identifiers for the path. We make sure they differ by one accordingly.

Finally, we encode some rules for the task specifically. We make sure that shape is selected as one piece (lines 117-133). We then make sure that start, end, circles and triangles are selected and are on the path (or, for triangles, they are not on the path). We then make sure the path goes through selected shapes only (145-150). And at the end we guarantee that the path is “one lane” (lines 152-162).

Finally, solution:

Tried aggregator 3 times.
MIP Presolve eliminated 4975 rows and 1893 columns.
MIP Presolve modified 5978 coefficients.
Aggregator did 2787 substitutions.
Reduced MIP has 7501 rows, 4384 columns, and 22839 nonzeros.
Reduced MIP has 3939 binaries, 445 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.08 sec. (69.66 ticks)
Probing fixed 10 vars, tightened 3 bounds.
Probing changed sense of 10 constraints.
Probing time = 0.00 sec. (2.95 ticks)
Tried aggregator 1 time.
MIP Presolve eliminated 87 rows and 45 columns.
MIP Presolve modified 31 coefficients.
Reduced MIP has 7414 rows, 4339 columns, and 22585 nonzeros.
Reduced MIP has 3894 binaries, 445 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.01 sec. (16.60 ticks)
Probing fixed 222 vars, tightened 107 bounds.
Probing changed sense of 19 constraints.
Probing time = 0.02 sec. (3.01 ticks)
Cover probing fixed 0 vars, tightened 4 bounds.
Clique table members: 8099.
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: deterministic, using up to 8 threads.
Root relaxation solution time = 0.08 sec. (55.88 ticks)

        Nodes                                         Cuts/
   Node  Left     Objective  IInf  Best Integer    Best Bound    ItCnt     Gap

      0     0        0.0000   284                      0.0000      839
      0     0        0.0000   183                   Cuts: 150      938
      0     0        0.0000   147                   Cuts: 157     1028

Repeating presolve.
Tried aggregator 3 times.
MIP Presolve eliminated 5111 rows and 3003 columns.
MIP Presolve modified 251 coefficients.
Aggregator did 19 substitutions.
Reduced MIP has 2284 rows, 1317 columns, and 6858 nonzeros.
Reduced MIP has 1147 binaries, 170 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.05 sec. (21.57 ticks)
Probing time = 0.00 sec. (1.94 ticks)
Tried aggregator 1 time.
Reduced MIP has 2284 rows, 1317 columns, and 6858 nonzeros.
Reduced MIP has 1147 binaries, 170 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.02 sec. (2.85 ticks)
Represolve time = 0.06 sec. (31.84 ticks)
Probing fixed 2 vars, tightened 0 bounds.
Probing time = 0.02 sec. (1.65 ticks)
Clique table members: 1357.
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: deterministic, using up to 8 threads.
Root relaxation solution time = 0.01 sec. (13.26 ticks)

        Nodes                                         Cuts/
   Node  Left     Objective  IInf  Best Integer    Best Bound    ItCnt     Gap

      0     0        0.0000    97                      0.0000     1408
      0     0        0.0000    52                    Cuts: 56     1449
      0     0        0.0000    73                    Cuts: 70     1502
      0     0        0.0000    98                    Cuts: 10     1510
*     0+    0                            0.0000        0.0000     1510    0.00%
      0     0        cutoff              0.0000        0.0000     1510    0.00%
Elapsed time = 1.30 sec. (606.96 ticks, tree = 0.00 MB, solutions = 1)

GUB cover cuts applied:  28
Clique cuts applied:  5
Cover cuts applied:  27
Implied bound cuts applied:  74
Zero-half cuts applied:  38
Gomory fractional cuts applied:  29

Root node processing (before b&c):
  Real time             =    1.31 sec. (607.25 ticks)
Parallel b&c, 8 threads:
  Real time             =    0.00 sec. (0.00 ticks)
  Sync time (average)   =    0.00 sec.
  Wait time (average)   =    0.00 sec.
                          ------------
Total (root+branch&cut) =    1.31 sec. (607.25 ticks)
1,0,0,0,0,3,
0,0,0,0,0,0,
0,3,0,0,0,0,
4,0,0,0,0,0,
0,0,4,0,0,0,
0,0,0,0,0,2,

1,0,0,1,1,1,
1,0,0,1,0,1,
1,1,1,1,0,1,
0,0,0,0,0,1,
0,0,0,0,0,1,
0,0,0,0,0,1,

1,1,0,1,1,1,
1,0,0,1,0,1,
1,1,1,1,0,1,
1,0,0,1,0,1,
1,0,1,1,0,1,
0,0,0,0,0,1,

100

101

Tried aggregator 3 times.

MIP Presolve eliminated 4975 rows and 1893 columns.

MIP Presolve modified 5978 coefficients.

Aggregator did 2787 substitutions.

Reduced MIP has 7501 rows, 4384 columns, and 22839 nonzeros.

Reduced MIP has 3939 binaries, 445 generals, 0 SOSs, and 0 indicators.

Presolve time = 0.08 sec. (69.66 ticks)

Probing fixed 10 vars, tightened 3 bounds.

Probing changed sense of 10 constraints.

Probing time = 0.00 sec. (2.95 ticks)

Tried aggregator 1 time.

MIP Presolve eliminated 87 rows and 45 columns.

MIP Presolve modified 31 coefficients.

Reduced MIP has 7414 rows, 4339 columns, and 22585 nonzeros.

Reduced MIP has 3894 binaries, 445 generals, 0 SOSs, and 0 indicators.

Presolve time = 0.01 sec. (16.60 ticks)

Probing fixed 222 vars, tightened 107 bounds.

Probing changed sense of 19 constraints.

Probing time = 0.02 sec. (3.01 ticks)

Cover probing fixed 0 vars, tightened 4 bounds.

Clique table members: 8099.

MIP emphasis: balance optimality and feasibility.

MIP search method: dynamic search.

Parallel mode: deterministic, using up to 8 threads.

Root relaxation solution time = 0.08 sec. (55.88 ticks)

Nodes Cuts/

Node Left Objective IInf Best Integer Best Bound ItCnt Gap

0 0 0.0000 284 0.0000 839

0 0 0.0000 183 Cuts: 150 938

0 0 0.0000 147 Cuts: 157 1028

Repeating presolve.

Tried aggregator 3 times.

MIP Presolve eliminated 5111 rows and 3003 columns.

MIP Presolve modified 251 coefficients.

Aggregator did 19 substitutions.

Reduced MIP has 2284 rows, 1317 columns, and 6858 nonzeros.

Reduced MIP has 1147 binaries, 170 generals, 0 SOSs, and 0 indicators.

Presolve time = 0.05 sec. (21.57 ticks)

Probing time = 0.00 sec. (1.94 ticks)

Tried aggregator 1 time.

Reduced MIP has 2284 rows, 1317 columns, and 6858 nonzeros.

Reduced MIP has 1147 binaries, 170 generals, 0 SOSs, and 0 indicators.

Presolve time = 0.02 sec. (2.85 ticks)

Represolve time = 0.06 sec. (31.84 ticks)

Probing fixed 2 vars, tightened 0 bounds.

Probing time = 0.02 sec. (1.65 ticks)

Clique table members: 1357.

MIP emphasis: balance optimality and feasibility.

MIP search method: dynamic search.

Parallel mode: deterministic, using up to 8 threads.

Root relaxation solution time = 0.01 sec. (13.26 ticks)

Nodes Cuts/

Node Left Objective IInf Best Integer Best Bound ItCnt Gap

0 0 0.0000 97 0.0000 1408

0 0 0.0000 52 Cuts: 56 1449

0 0 0.0000 73 Cuts: 70 1502

0 0 0.0000 98 Cuts: 10 1510

* 0+ 0 0.0000 0.0000 1510 0.00%

0 0 cutoff 0.0000 0.0000 1510 0.00%

Elapsed time = 1.30 sec. (606.96 ticks, tree = 0.00 MB, solutions = 1)

GUB cover cuts applied: 28

Clique cuts applied: 5

Cover cuts applied: 27

Implied bound cuts applied: 74

Zero-half cuts applied: 38

Gomory fractional cuts applied: 29

Root node processing (before b&c):

Real time = 1.31 sec. (607.25 ticks)

Parallel b&c, 8 threads:

Real time = 0.00 sec. (0.00 ticks)

Sync time (average) = 0.00 sec.

Wait time (average) = 0.00 sec.

------------

Total (root+branch&cut) = 1.31 sec. (607.25 ticks)

1,0,0,0,0,3,

0,0,0,0,0,0,

0,3,0,0,0,0,

4,0,0,0,0,0,

0,0,4,0,0,0,

0,0,0,0,0,2,

1,0,0,1,1,1,

1,0,0,1,0,1,

1,1,1,1,0,1,

0,0,0,0,0,1,

1,1,0,1,1,1,

1,0,0,1,0,1,

1,1,1,1,0,1,

1,0,0,1,0,1,

1,0,1,1,0,1,

0,0,0,0,0,1,