I'm trying to formulate what I think is a solveable integer linear programming problem. The use application is creating a set of mutually exclusive patrol areas for a police department, and I have formulated it similar to an assignment problem. The main difference is I want to limit the number of source locations assigned to a destination location.

So given S sources and J destinations, we then have a set of X_sd 0-1 variables, where source s covers destination d if X_sd equals 1, and there are C_sd costs associated with each pair. We then want to minimize C_sd*X_sd subject to constraints that each destination is only assigned once, and there are only P source locations selected.

Part of my confusion is other work hasn't formulated the table like this S*D decision variables, but has destinations and sources as separate variables, and then simply says the sum of the source variables equals P (see this paper for one example). I'm not quite sure how to formulate the problem like that though.

Here is my current code in python using the pulp library. Any suggestions are appreciated.

#Python code using pulp library
from pulp import *

Areas = ['A','B','C','D']

#Values on a line, with each area 1 distance apart
Calls = {'A': 4, 
         'B': 1, 
         'C': 2, 
         'D': 3}

Distances = {'A': {'A': 0, 'B': 1, 'C': 2, 'D': 3},
             'B': {'A': 1, 'B': 0, 'C': 1, 'D': 2},
             'C': {'A': 2, 'B': 1, 'C': 0, 'D': 1},          
             'D': {'A': 3, 'B': 2, 'C': 1, 'D': 0}}

def CostFunct(s,d):
    return Distances[s][d]*Calls[d]

ChoosePatrol = LpProblem("Creating Patrol Areas",LpMinimize)

assign_areas = LpVariable.dicts("Sources and Destinations", [(s,d) for s in Areas for d in Areas], lowBound=0, upBound=1, cat=LpInteger)

#Set up the problem, minimize weighted distances
ChoosePatrol += lpSum(CostFunct(s,d)*assign_areas[(s,d)] for s in Areas for d in Areas), "Minimize weighted travel"

#Need a constraint -- only 2 source areas are selected?

#Constraint - every destination area must be covered at least once
for d in Areas:
  ChoosePatrol += sum(assign_areas[(s,d)] for s in Areas) == 1, "Destination Area %s must be covered only one time" % (d)


#This should be 3
print("The total weighted travel", value(ChoosePatrol.objective))

#Want it to be A-A,A-B and D-C,D-D
#Currently will just assign A-A,B-B,C-C,D-D
for v in ChoosePatrol.variables():
    print (v.name, "=", v.varValue)

asked 28 Aug '17, 12:01

AndyW's gravatar image

accept rate: 0%

This is known as the \(p\)-median problem. Some formulations use both \(x_{ij}\) and \(y_i\) as binary decision variables, but you can also eliminate \(y_i\) by replacing it with \(x_{ii}\). The cardinality constraint is either \(\sum_i y_i = p\) or \(\sum_i x_{ii} = p\). You don't need any permutations.


answered 28 Aug '17, 14:45

Rob%20Pratt's gravatar image

Rob Pratt
accept rate: 28%

edited 28 Aug '17, 16:19

Thank you - I thought the second constraint you listed, just the sum of x_ii (on the diagonal) would work, but in my example if that is the only additional constraint then I get a solution for my example problem as A->A, A->B, B->C, D->D - hence I examined all of the row permutations. It appears what I was missing was to put in a set of additional constraints that X_sd <= X_ss for each s,d.

(28 Aug '17, 15:10) AndyW

One solution I've found -- for at least this particular problem -- is the idea to set constraints on the sum of the rows. So if you take one unique destination for each source, they should at max sum to the total number of areas you want to limit the solution to.

So in my example, the option X_aa + X_bb + X_cc + X_dd needs to be less than or equal to P. Then you need to do this for every potential permutation within the destination areas. So in the python code this results in a set of constraints that look like (for selecting two areas):

import itertools
#Constraint - the total number of selected source areas must equal TotalBeats
#For every particular combination of rows, each much only sum to 2 at max
perm = 0
for i in itertools.permutations(Areas,4):
  ChoosePatrol += sum(assign_areas[(s,d)] for s,d in zip(Areas,i)) <= TotalBeats, "Total Number of Source Beats Selected Iteration %s" % (perm)
  perm += 1

If folks have a simpler formula though I would appreciate the input.


answered 28 Aug '17, 14:28

AndyW's gravatar image

accept rate: 0%

Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported



Asked: 28 Aug '17, 12:01

Seen: 611 times

Last updated: 28 Aug '17, 16:19

OR-Exchange! Your site for questions, answers, and announcements about operations research.