[Math] How to solve binary nonlinear programming problems

binary-programmingdiscrete optimizationlinearizationnon-convex-optimizationnonlinear optimization

I have written binary nonlinear programming problem:
a

Now I want to solve this problem. My decision variables are $x_{i,j}, y_{i,j}$ and $z_{i,j}$. The other terms are constants. N=30 and K=4.

I think this problem is considered as NP-hard but I’m not sure.

Therefore, I really appreciate if someone can guide me to know:

Is this problem is NP-Hard or not?

Is this problem is convex or non-convex?

How to solve this problem numerically?

How to apply Linearization methods to the objective and constraints to become a linear problem?

Is there any tool that is able to automatically solve this problem?

Is a there a good introductory book where I can start?

Thanks in advance!

Best Answer

Is this problem is NP-Hard or not?

In general, 0-1 integer linear programming is NP-hard. However, you've got a specific collection of constraints and any proof of NP-hardness for this specific problem would require an argument specialized to the problem.

Furthermore, you've got fixed values of $N$ and $K$, so you're really not interested in the whole class of problems but rather instances of that particular size and what might practically be done to solve them.

Thus there's little reason to invest any effort in proving NP-hardness of the problem.

Is this problem is convex or non-convex?

The 0-1 constraints make the problem inherently non-convex. In nonlinear integer programming, we sometimes speak of a problem as being a convex nonlinear integer programming problem if the continuous relaxation of the 0-1 constraints results in a convex nonlinear optimization problem. It appears to me that the continuous relaxation of your problem is non-convex because of products of the form $x_{i,j}y_{i,j}$ that are multiplied by negative coefficients.

How to solve this problem numerically?

You might try a linearization approach as discussed below. This is probably the easiest method to implement using non-specialized software but it may not be fastest.

Algorithms that use branch-and-bound and/or outer-approximation methods might be able to handle your problem and provide an optimal or near optimal (with bounds) solution.

You might also consider using a meta-heuristic approach to get a heuristic solution.

How to apply Linearization methods to the objective and constraints to become a linear problem?

The first thing to know about linearization of expressions involving binary variables is that If $x$ is a binary variable, then $x=x^{k}$ for any $k>1$. Thus any place where a power of a binary variable appears it can be replaced by the binary variable itself.

The next thing to know is that if $x$ and $y$ are binary variables, then we can create a new binary variable $z$ and add the following constraints to ensure that $z=xy$. The required constraints are:

$-x+z \leq 0$

$-y+z \leq 0$

$x+y-z \leq 1$

To see that this works, simply check all possible combinations of 0-1 values for $x$, $y$, and $z$. This approach can easily be extended to products of three or more binary variables.

In your problem, introduce a new collection of 0-1 variables $u$, where

$u_{i,j,k,l,m,n}=x_{i,j}y_{k,l}z_{m,n}$

Replace each product of three 0-1 variables in the original problem with the corresponding element of $u$. You'll also have to introduce linear constraints to enforce $u_{i,j,k,l,m,n}=x_{i,j}y_{k,l}z_{m,n}$. Similarly, you'll need $u$ entries corresponding to products of pairs $u_{i,j,k,l}=x_{i,j}y_{k,l}$, and pairs of $xz$ and $yz$. Your problem is now a 0-1 integer linear programming problem in the $u$ variables.

On the surface, this would seem to be hopeless because it would require millions of 0-1 variables in $u$. However, after examining your constraints and objective, it's clear that not all of the possible products of $x$, $y$, and $z$ binary variables actually appear in the constraints and objective. In fact, only $x_{i,j}$, $y_{i,j}$ and $z_{i,j}$ ever appear together in a product in a constraint or objective. Thus you will be able to dramatically reduce the number of 0-1 variables to $3 \times 120 + 3 \times 120 + 120=840$ 0-1 variables. (This comes from 120 $x_{i,j}$ variables, 120 $y_{i,j}$ variables, 120 $z_{i,j}$ variables, 120 $x_{i,j}y_{i,j}$ variables, 120 $x_{i,j}z_{i,j}$ variables, 120 $y_{i,j}z_{i,j}$ variables, and 120 $x_{i,j}y_{i,j}z_{i,j}$ variables.)

Is there any tool that is able to automatically solve this problem?

There are many software packages for integer linear programming that should be able to handle the linearized reformulation.

There are lots of software packages that can deal with general 0-1 mixed integer nonlinear programming problems by using branch-and-bound and/or outer-approximation methods. See the list of solvers supported by NEOS at:

https://neos-server.org/neos/solvers/index.html#minco

You can try these solvers out by formulating your problem in the GAMS modeling language and sending it to the NEOS server for a solution.

Is a there a good introductory book where I can start?

There are lots of books on the topic of nonlinear integer programming. A good starting point will depend somewhat on your background in algorithms and optimization as well as what approach you decide to take with this problem.

A reference that covers branch-and-bound and outer-approximation methods is C. A. Floudas, Nonlinear and Mixed-Integer Optimization, Oxford University Press, 1995.

The linearization approach is discussed in many textbooks on linear and integer programming. I'd suggest that you look at the discussion of this in H. P. Williams, Modeling Building in Mathematical Programming, 5th ed., Wiley, 2013. See pages 175-176.

Related Question