Python discrete optimization with linear objective function

Question

I have some points(N). For these points I have a distance matrix D (N*N). Also I have an attribute data for these points A (1*N). I want to select fixed number of points(K) such that sum of attribute is maximum while distance between selected points lies between a range (min_dis,max_dis).

I tried implementing this optimization problem in Pulp with N=10,K=3.

A = [300,436,234,11,23,897,439,56,123,432].

    import pulp
    import numpy as np

    inds = range(10)

    #create a vector x which will only accept value 0,1
    x = pulp.LpVariable.dicts('x', inds, lowBound = 0,upBound = 1,cat = pulp.LpInteger)

    my_lp_problem = pulp.LpProblem("My LP Problem", pulp.LpMaximize)

    #sum of x should be equal to no of points I want (which is 3)
    my_lp_problem += sum([x[store] for store in inds]) == 3

    #maximize dot product A.x (which would be sum of attributes)
    my_lp_problem += sum([A[point] * x[point] for point in inds])

However I am not able to put the constraints on distance matrix. Which would be something like this:

    np.multiply(x,D).max() < max_dis and np.multiply(x,D).min() > min_dis

As I could not find how to use max(), min() and matrix multiplication kind of things in pulp. What I understand is this has a linear objective function while the constraints are not linear. I also explored scipy.optimize but as x can contain only 0 and 1 not a continuous variable I started with pulp. Any help appreciated!

sascha sascha · Accepted Answer · 2018-05-09T15:37:32

I don't see any non-linearities here. If i understood the task correctly, you could:

introduce aux-vars P[i,j] in {0,1}
- point i selected (let's assume: S[i] = 1) & point j selected IMPLIES P[i,j] = 1
- removing symmetries, this set is of size C(N,2)
- you can interpret it as active pair indicator
formulate the above relation:
- P[i,j] >= S[i] + S[j] - 1 (for all i; for all j)
- warning: we are only formulating the implication (not equivalence); not necessarily interested in the other direction
add a bounding-constraint for all C(N,2) distances (equivalent to bounding the max value; common reformulation):
- P[i,j] * DIST[i,j] <= max-dist (for all i; for all j)
- this is an affine-constraint (DIST & max-dist are constants)

Remark: the above is somewhat informal in regards to the dimensionality of P (flat 1D vs. 2D) and for all i; for all j. The details depend on this decision and if symmetries are removed.

Python discrete optimization with linear objective function

1 Answers