Bintprog exceeds the max time for one set of parameters but optimizes the function in under a minute for other sets of parameters. What is wrong and how do I fix it?

The only difference between a successful run and an unsuccessful run is a weight parameter. The objective function has 10,000 variables. Why does the display only output one iteration?

Iteration display of unsuccessful bintprog run:

Explored nodes = 1

Obj of LP relaxation = -41.73

Obj of best integer point = -

Unexplored nodes = 2

Best lower bound on obj = -41.73

Relative gap between bounds = -

Iteration display of successful bintprog run:

Explored nodes = 1

Obj of LP relaxation = -39.98

Obj of best integer point = -39.98

Unexplored nodes = 0

Best lower bound on obj = -41.73

Relative gap between bounds = 0%

Answer 1

[Alan Weiss]

The successful run that you showed has the linear programming relaxation arrive at an integer solution. You cannot expect to be so lucky in general. The unsuccessful run showed that bintprog did not find an integer feasible point.

10,000 variables is a lot for bintprog. You would probably have better luck with the newer integer linear programming solver, intlinprog, which was introduced in R2014a. Even that solver can take many minutes or hours to solve an integer program with thousands of variables.

Alan Weiss

MATLAB mathematical toolbox documentation