Can you solve the Static Weapon Target Assignment problem in CVXPY?

Question

I am trying to analyse the static weapon target assignment (WTA) problem with CVXPY. My first goal is to get a small instance of the problem running in order to test that I have implemented the objective function and constraints correctly (and subsequently scale up and add parameters), but I am encountering errors that I do not know how to resolve.

The problem description is as follows:

My code is below (please forgive any poor coding, I am a relative novice). Here, I am only considering two weapons and two targets and I have specified notional probability values. The decision variable is boolean because each weapon can only be assigned once to each target.

import cvxpy as cp
import numpy as np

# Parameters
m = cp.Parameter(nonneg=True, value=2)  # Number of weapons
n = cp.Parameter(nonneg=True, value=2)  # Number of targets
q = cp.Parameter((m.value, n.value), nonneg=True)  # Probability of weapon i not destroying target j, q_{ij}=(1-p_{ij})

# Other values
ones_w = np.ones((m.value, 1))
ones_t = np.ones((n.value, 1))

# Specify notional values for q
q.value = np.array([[0.9, 0.8], [0.5, 0.7]])

# Variables
x = cp.Variable(q.shape, boolean=True) # Assignment of weapon i to target j

# Constraints
constraints = []
constraints += [x @ ones_t == ones_w]  # A weapon must be assigned to only one target

# Objective
objective = cp.Minimize(cp.sum(cp.exp(cp.multiply(x, cp.log(q)))))

# Form and solve problem
swta = cp.Problem(objective, constraints)
swta.solve(solver=SCIPY)

Weapon 1 should be assigned to target 2 and weapon 2 to target 1. However, when I run my code, I receive the following error message:

cvxpy.error.SolverError: Either candidate conic solvers (['SCIPY']) do not support the cones output by the problem (ExpCone, Zero), or there are not enough constraints in the problem.

I have tried various other CVXPY solvers (CBC, CPLEX, GLPK_MI, GUROBI, XPRESS) and have encountered the same error message.

If I add an additional constraint to limit the number of weapons that can be aimed at a target (see below), the error remains.

constraints += [x.T @ ones_t == ones_w]  # A target must only have one weapon assigned to it

I suspect there is an issue with my objective function because if I interchange it with something simpler (see below for an example), the problem can be solved. However, this does not reflect the objective function of the static WTA problem. In my code, I have attempted to capture the x_{ij} decision variable as an exponent in the objective function, but this may be causing the issues. I am not sure how else the objective function can be specified whilst working within the constraints of CVXPY.

objective = cp.Minimize(cp.sum(cp.multiply(x, q)))

Does anyone know how I can get my code to run in CVXPY according to the problem that I am considering? Should the objective function be specified differently? Is the problem incompatible with CVXPY?

Answer 1

With CPLEX (outside of cvxpy) you could use constraint programming and write:

using CP;

int m =2; // Number of weapons
int n = 2; // Number of targets

range M=1..m;
range N=1..n;

float q[M][N]=[[0.9, 0.8], [0.5, 0.7]];

// Assignment of weapon i to target j
dvar boolean x[M][N];

minimize sum(w in M,t in N) exp(x[w][t]*log(q[w][t]));
subject to
{
  // A weapon must be assigned to only one target
  forall(w in M) sum(t in N) x[w][t]==1;
}

with the OPL API.

Which gives

// solution with objective 3.647693
x = [[0 1]
             [1 0]];

You can do the same within python through docplex cplex python API