ILP Part 72 — Self-descriptive numbers

This is the seventieth second 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’re going to solve self-descriptive numbers described in Delta article. Self-descriptive number is a number which “describes” itself: first digit denotes how many zeroes there are in decimal representation of the number. Second digit denotes how many ones and so on. We consider here decimal system only but the solution can be easily generalized to other systems as well.

Authors mention that optimized algorithm finds 10-digit number in couple seconds using Python. Let’s see if we can do better in ILP. Let’s use CplexMilpSolver as usual. The code:

var solver = new CplexMilpSolver(new CplexMilpSolverSettings
{
	IntegerWidth = integerWidth,
	Epsilon = epsilon,
	StoreDebugExpressions = storeDebugExpressions,
	CacheConstants = cacheConstants,
	StoreDebugConstraints = storeDebugConstraints
});
solver.Cplex.SetParam(ILOG.CPLEX.Cplex.Param.MIP.Tolerances.Integrality, epsilon);

var variables = Enumerable.Range(0, 10).Select(v => solver.CreateAnonymous(Domain.PositiveOrZeroInteger)).ToArray();

foreach(var v in variables){
	v.Set<LessOrEqual>(solver.FromConstant(variables.Length - 1));
}

variables[0].Set<GreaterOrEqual>(solver.FromConstant(1));

var counts = variables.Select(i => solver.FromConstant(0)).ToArray();

for(int i=0;i<counts.Length;++i){
	foreach(var v in variables){
		counts[i] = counts[i].Operation<Addition>(v.Operation<IsEqual>(solver.FromConstant(i)));
	}
}

for(int i=0;i<counts.Length;++i){
	variables[i].Set<Equal>(counts[i]);
}

solver.AddGoal("g", solver.FromConstant(0));
solver.Solve();

foreach(var l in variables){
	Console.Write(solver.GetValue(l));
}

var solver = new CplexMilpSolver(new CplexMilpSolverSettings

{

IntegerWidth = integerWidth,

Epsilon = epsilon,

StoreDebugExpressions = storeDebugExpressions,

CacheConstants = cacheConstants,

StoreDebugConstraints = storeDebugConstraints

});

solver.Cplex.SetParam(ILOG.CPLEX.Cplex.Param.MIP.Tolerances.Integrality, epsilon);

var variables = Enumerable.Range(0, 10).Select(v => solver.CreateAnonymous(Domain.PositiveOrZeroInteger)).ToArray();

foreach(var v in variables){

v.Set<LessOrEqual>(solver.FromConstant(variables.Length - 1));

}

variables[0].Set<GreaterOrEqual>(solver.FromConstant(1));

var counts = variables.Select(i => solver.FromConstant(0)).ToArray();

for(int i=0;i<counts.Length;++i){

foreach(var v in variables){

counts[i] = counts[i].Operation<Addition>(v.Operation<IsEqual>(solver.FromConstant(i)));

}

for(int i=0;i<counts.Length;++i){

variables[i].Set<Equal>(counts[i]);

}

solver.AddGoal("g", solver.FromConstant(0));

solver.Solve();

foreach(var l in variables){

Console.Write(solver.GetValue(l));

}

First, we create solver in lines 1-9.

In line 11 we define ten non-negative integer variables. Next, in line 13 we set their upper bound. Here we use the fact that $k$ -digit self-descriptive number must have digits which are less than $k$ . Finally, in line 17 we specify that first digit must be non-zero.

Next we calculate counts. We define counters in line 19. Then in lines 21-25 we simply iterate over digits and compare them with constants.

Finally, in lines 27-29 we add constraints to make the number self-descriptive. We take each counter and make it equal to the respective digit.

Output:

Tried aggregator 2 times.
MIP Presolve eliminated 79 rows and 25 columns.
MIP Presolve modified 1153 coefficients.
Aggregator did 218 substitutions.
Reduced MIP has 524 rows, 267 columns, and 1295 nonzeros.
Reduced MIP has 257 binaries, 10 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.00 sec. (1.65 ticks)
Found incumbent of value 0.000000 after 0.01 sec. (4.41 ticks)

Root node processing (before b&c):
  Real time             =    0.01 sec. (4.44 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) =    0.01 sec. (4.44 ticks)
6210001000

Tried aggregator 2 times.

MIP Presolve eliminated 79 rows and 25 columns.

MIP Presolve modified 1153 coefficients.

Aggregator did 218 substitutions.

Reduced MIP has 524 rows, 267 columns, and 1295 nonzeros.

Reduced MIP has 257 binaries, 10 generals, 0 SOSs, and 0 indicators.

Presolve time = 0.00 sec. (1.65 ticks)

Found incumbent of value 0.000000 after 0.01 sec. (4.41 ticks)

Root node processing (before b&c):

Real time = 0.01 sec. (4.44 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) = 0.01 sec. (4.44 ticks)

6210001000

So it looks like the solution was found in almost no time. Pretty good.