Received 26 August 2015; accepted 5 January 2016; published 11 January 2016

ABSTRACT

The paper presents a technique for solving the binary linear programming model in polynomial time. The general binary linear programming problem is transformed into a convex quadratic programming problem. The convex quadratic programming problem is then solved by interior point algorithms. This settles one of the open problems of whether P = NP or not. The worst case complexity of interior point algorithms for the convex quadratic problem is polynomial. It can also be shown that every liner integer problem can be converted into binary linear problem.

Keywords:

NP-Complete, Binary Linear Programming, Convex Function, Convex Quadratic Programming Problem, Interior Point Algorithm and Polynomial Time

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.

Cite this paper

EliasMunapo, (2016) Solving the Binary Linear Programming Model in Polynomial Time. American Journal of Operations Research,06,1-7. doi: 10.4236/ajor.2016.61001

References