Nonlinear integer (0/1) programming solver

Operations Research Asked by Rajya on March 1, 2021

I have the following optimisation problem.begin{align}max&quadsum_isum_jsum_k x_{ji}y_{kj} operatorname{cost}(i,k)\text{s.t.}&quadsum_j x_{ji}=1quadforall i\&quadsum_k y_{kj}=1quadforall jend{align}

Please suggest any solver for this. The cost function is stored in a matrix.

Maybe I am missing something but it looks like there is no need for a library: begin{align} sum_i sum_j sum_k x_{ji} y_{kj} cost(i,k)&=sum_i sum_j x_{ji} sum_k y_{kj} cost(i,k) end{align} Now since $$sum_k y_{kj}=1$$, exactly one row is 1, the others zero. We pick the best one: $$=sum_i sum_j x_{ji} max_k cost(i,k)$$ Since $$sum_j x_{ji}=1$$ we get $$=sum_i max_k cost(i,k)$$

So basically go through the cost matrix row by row and pick the largest entry. This must have been homework :)

Answered by phil on March 1, 2021

Besides the traditional linearization suggested by @MarkL.Stone and @Richard, you might consider using the constraints to obtain a compact linearization. Explicitly, multiply both sides of your second constraint by $$x_{j,i}$$: $$sum_k x_{j,i} y_{k,j} = x_{j,i}$$ Now replace $$x_{j,i} y_{kj}$$ with $$z_{i,j,k}$$ and impose an additional constraint to enforce $$y_{k,j} = 0 implies z_{i,j,k} = 0$$. The resulting linear formulation is:

begin{align} &text{maximize} &sum_isum_jsum_k text{cost}(i,k) z_{i,j,k}\ &text{subject to} &sum_j x_{j,i} &= 1 &&text{for all i}\ &&sum_k z_{i,j,k} &= x_{j,i} &&text{for all i and j} \ &&0 le z_{i,j,k} &le y_{k,j} &&text{for all i, j, and k} end{align}

Answered by RobPratt on March 1, 2021

Your optimization problem seems like a special variant of the quadratic assignment problem (qap). One difference is that you have only products of variables coming from two different sets (x and y). This structure is called separable or disjoint bilinear programming.

The standard qap is one of the simplest quadratic problems, there are often examples from the solvers for this problem (some official/some from third-party people). They can easily be changed for your problem.

Localsolver:

Gurobi:

Answered by user3680510 on March 1, 2021

In my opinion your best bet is to define an auxiliary variable $$z_{ijk}$$ such that: $$begin{equation} z_{ijk} geq x_{ji} + y_{kj} -1 \ z_{ijk} leq x_{ji} \ z_{ijk} leq y_{kj} end{equation}$$

Now this may become a really huge problem depending on the dimensions of $$i$$, $$j$$ and $$k$$. However, you gain the linearity of the problem which is worth a lot in my experience.

Lastly, you may be able to prune some stuff if you know more about the problem, but nothing comes to my mind right now.

Answered by Richard on March 1, 2021

You can try our own Octeract Engine, it solves all classes of optimisation problems up to (and including) DMINLP to global optimality. If you are a student/academic, you can also use it for it free! On the free side, there's also SCIP (only free for academics) and Couenne (open source).

Answered by Nikos Kazazakis on March 1, 2021

Option 1: Submit as is to a solver which can globally optimize MIQPs having non-convex objective, and which might reformulate to a linearized MILP model under the hood. Such solvers include CPLEX, Gurobi 9.x, and BARON, among others.

Option 2:

Step 1 Linearize the products of binary variables, per How to linearize the product of two binary variables? . <Edit: This step is written out explicitly in this thread in @Richard 's subsequent answer.>

Step 2: Submit your linearized model to a MILP solver, such as CPLEX, Gurobi, XPress, Mosek, SCIP, or many others.

Note:Some solvers, such as CPLEX, give you the option of specifying whether the solver should reformulate the Binary MIQP to a MILP. There may be a default to let the solver decide which way is better. See indefinite MIQP switch:Decides whether CPLEX will attempt to reformulate a MIQP or MIQCP model that contains only binary variables.

Answered by Mark L. Stone on March 1, 2021

Related Questions

What is a general procedure to prove that the LP relaxation of an IP delivers the optimal IP solution?

2  Asked on August 19, 2021 by k88074

CPLEX MIP warm start seems slow down the program?

1  Asked on August 19, 2021 by mengfan-ma

(Iterative?) Solutions to a certain quadratic program with non-convex constraints

2  Asked on August 19, 2021 by cfp

Problem with implementing squared terms in the objective function

1  Asked on August 19, 2021 by poofybridge

Scheduling with setup cost

0  Asked on August 19, 2021 by dirk-nachbar

Is a convex or MILP (without big-M) formulation possible for this problem

1  Asked on August 19, 2021 by batwing

MINLP Solution same as Global Optimum?

2  Asked on August 19, 2021 by clement

Linear objective function with non-linear constraints

2  Asked on August 19, 2021 by fightmilk

Meta papers on operations research

2  Asked on August 19, 2021 by luke599999

Verifying the correctness of KKT conditions

0  Asked on August 19, 2021 by s_scouse

How can I use warm start in C#

1  Asked on August 19, 2021 by fhm-ider

Feasible sets represented as point clouds

1  Asked on August 19, 2021 by harry-cohen

Is this the same as Agent Based DES or something different?

0  Asked on August 19, 2021 by brendan-hill

Column generation when intractable variables appear in the objective function

1  Asked on August 19, 2021 by mostafa

Is there any OR way to solve this problem?

3  Asked on August 19, 2021 by samiczy

Find a particular optimal solution

1  Asked on August 19, 2021 by ljg

How to find all vertices of a polyhedron

3  Asked on August 19, 2021

Can every convex problem use Lagrangian dual method?

0  Asked on August 19, 2021

Does strong duality hold when I dualize only a subset of the constraints?

1  Asked on August 19, 2021 by george-chang