Received 26 August 2015; accepted 5 January 2016; published 11 January 2016
1. Introduction
The binary linear programming (BLP) model is NP-complete and up to now we have not been aware of any polynomial algorithm for this model. See for example Fortnow [1] [2] for more on complexity. In this paper we present a technique for transforming the BLP model into a convex quadratic programming (QP) problem. The optimal solution of the resultant convex QP is also the optimal solution of the original problem BLP. This solves one of the famous open problems of whether P = NP or not.
2. The BLP Model
Let any BLP model be represented by
(1)
Any minimization BLP can be converted into maximization form and vice versa. There are several strategies for solving mixed 0 - 1 integer problems that are presented in Adams and Sherali [3] .
3. Convex Quadratic Programming Model
Let a quadratic programming problem be represented by (2).
(2)
We assume that:
1) matrix Q is symmetric and positive definite,
2) function 
is strictly convex,
3) since constraints are linear then the solution space is convex,
4) any maximization quadratic problem can be changed into a minimization and vice versa.
When the function 
is strictly convex for all points in the convex region then the quadratic problem has a unique local minimum which is also the global minimum [4] -[6] .
4. Transforming BLP into a Convex/Concave Quadratic Programming Problem
Our problem is to transform problem (1) into (2) and once that is done then (2) can be solved in polynomial time implying P = NP. Interior point algorithms can solve the convex/concave QP problem in polynomial time.
4.1. Rules with Binary Variables
Binary variables have certain special features that we can capitalize on when solving.
4.1.1. Rule 1
Given any binary variable 
then slack variable 
is also binary in the optimal solution.
Proof
(3)
Case 1: When 
then 
Case 2: When 
then 
4.1.2. Rule 2
For any binary variable 
and slack variable 
the following must hold at optimality for BLPs.
(4)
The proof is the same as the one given in 4.1.1. Note that it is only binary variables that can satisfy (4). Even though none binary values such as 
then ![]()
can satisfy (3) the same values cannot satisfy (4), i.e., ![]()
The binary variable slack relationship given in (4) is the backbone of this paper.
4.2. Forcing Variables to Assume Binary Variables
The main weakness of the objective function given in (1) is that it does not force variables to assume binary values. In this paper we alleviate this challenge by adding a nonlinear extension to the objective function as given in (5).
![]()
(5)
where ![]()
and ![]()
is a very large constant. The constant ![]()
is very large in terms of its size compared to any of the coefficients in the objective function. This large value can be approximated as:
![]()
(6)
Proof
![]()
(7)
![]()
(8)
Since from Rule 2, ![]()
then ![]()
is minimized when
![]()
(9)
In other words ![]()
is maximized when variable ![]()
and slack variable ![]()
are integers. In this paper the nonlinear extension ![]()
is called an enforcer. An enforcer is a function, a set of constraint(s) or combination of both added to a problem to force an optimal solution with desired features such integrality.
4.3. Convexity of ![]()
A function ![]()
is convex if and only if it has second-order partial derivatives for each point ![]()
and for each ![]()
all principal minors of the Hessian matrix are none negative.
Proof
In this case
![]()
(10)
This has continuous second order partial derivatives and the 2n by 2n Hessian matrix is given by
![]()
(11)
Since all principal minors of ![]()
are nonnegative then ![]()
is convex. See Winston [7] for more on convex functions.
4.4. Convex Quadratic Programming Form
The function ![]()
can be expressed in the convex quadratic programming form
![]()
(12)
where matrix ![]()
is of dimension 2n by 2n, symmetric and positive definite as given in (13).
![]()
(13)
Thus matrix ![]()
is symmetric and positive definite. Note that ![]()
4.5. Complexity of Convex Quadratic Programming
The main reason for converting a BLP into a convex quadratic programming model is to take advantage of the availability of interior point algorithms which can solve convex QPs in polynomial time [8] . If any BLP can be converted into a convex quadratic problem, then any BLP can be solved in polynomial time.
4.6. Proof of Optimality
The proof is easily shown by reducing the convex quadratic objective function to the original linear form given in (1). The proposed objective function of the convex QP is reduced as follows:
![]()
Since ![]()
then,
![]()
(14)
![]()
(15)
In other words ![]()
is a constant and the objective function is the same as:
![]()
where ![]()
is binary for ![]()
this is the original form given in (1).
4.7. Infeasible Binary Integer Solution Space
In this case the solution of the convex OP will not be integer. The objective,
![]()
forces variables to binary or integral values if an integer point exists in the solution space. If an integer point does not exists in the solution space the large constant ![]()
in the objective forces variables to assume values whose sum of squares are near one and not necessarily one. In other words the variables will assume values ![]()
and ![]()
such that
![]()
(16)
![]()
(17)
4.8. Mixed BLP Models
In some BLP problems that occur in real life, a fraction of some of the variables may not be restricted to integer values. In this case the enforcer ![]()
is composed of only those variables that are supposed be binary and integer.
4.9. Interior Point Algorithm for Convex QP
Any maximization BLP problem can be converted into a minimization BLP and vice versa. This can be done by the substitution given in (18).
![]()
(18)
where ![]()
is also a binary variable.
Suppose the primal-dual pair of the convex QP is given by (19) and (20).
Primal:
![]()
(19)
Dual:
![]()
(20)
where ![]()
is free, ![]()
and ![]()
is a diagonal matrix.
The first order optimality conditions for (19) and (20) are given by (21)
![]()
(21)
where e is a vector of ones. The primal-dual central path method can be used to solve the convex QP. Detailed information on this interior point algorithm and other variants can be obtained in Gondzio [8] .
5. BLP and Convex QP Relationship
![]()
![]()
From the two versions of the same problem
![]()
(22)
6. Numerical Illustration
The following numerical illustration shows how a BLP problem is transformed into convex quadratic programming model and then solved.
6.1. Pure Binary Linear Programming
![]()
(23)
where ![]()
are binary variables.
Transforming into a convex quadratic programming problem becomes (24)
![]()
(24)
where ![]()
are also binary variables.
The solution to the convex quadratic problem is given in (25).
![]()
and ![]()
(25)
6.2. Mixed Binary Linear Programming Problem
In the case of a mixed binary linear programming problem, only the binary integer variables occupy the enforcer. In other words, if only the r binary variables ![]()
are integer then use
![]()
(26)
Suppose in 5.1, the variables ![]()
and ![]()
are not restricted to integer but both variables are less than 1.
The transformation becomes as shown in (27).
![]()
(27)
The solution to the convex quadratic problem is:
![]()
and ![]()
(28)
7. From Mixed Integer Problem to BLP
The problems that occur in real life do not have binary variables only. These practical problems occur as general mixed integer problem (MIP) where variables assume integer values greater than 1. There are methods that can be used to solve these problems but we are not aware of any method that can solve these mixed integer problems in polynomial time up now. The obvious strategy is to expand the general mixed integer variable into binary ones.
7.1. Converting MIP into BLP
Any MIP variable ![]()
can be expanded into binary variables as given in (29).
![]()
(29)
where ![]()
is a binary variable for ![]()
This procedure is explained in Owen and Mehrotra [9] .
7.2. Numerical Illustration
Convert the following MIP into a BLP.
![]()
(30)
where ![]()
are integers.
The following substitutions change the problem into a BLP.
![]()
(31)
where ![]()
is a binary variable for ![]()
and ![]()
8. Conclusion
The general BLP problem has been given so much attention by researchers all over the world for over half a century without a breakthrough. A difficult category of BLP models includes the traveling salesman, generalized assignment, quadratic assignment and set covering problems. The paper presented a technique to solve BLP problems by first transforming them into convex QPs and then applying interior point algorithms to solve them in polynomial time. We also showed that the proposed technique worked for both pure and mixed BLPs and also for the general linear integer model where variables were expanded into BLPs. We hope the proposed approach will give more clues to researchers in the hunt for efficient solutions to the general difficult integer programming problem.
Acknowledgements
The author is thankful to the referees for their helpful and constructive comments.