[Dip-tickets] [Dip] #76: Recompose solution error when in Phase I
Dip
coin-trac at coin-or.org
Tue Jul 5 17:21:15 EDT 2011
#76: Recompose solution error when in Phase I
--------------------+-------------------------------------------------------
Reporter: mosu001 | Type: defect
Status: new | Priority: major
Version: trunk | Keywords:
--------------------+-------------------------------------------------------
I have a facility location problem using price and cut and it generates an
error from recomposeSolution even though it has moved into Phase I after
generating a branch. As far as I can tell the m_firstPhase2Call causes the
solutionUpdateAsIP function to be called and this finds a feasible integer
solution, but it includes an artifical variable and so recomposeSolution
fails. I don't seem to be able to attach files to this ticket so I have
cut-and-paste the Dippy file below:
import coinor.pulp as pulp
from pulp import *
##import coinor.dippy as dippy
import dippy
from math import floor, ceil
from random import seed, shuffle
from copy import copy
from operator import itemgetter
tol = pow(pow(2, -24), 2.0 / 3.0)
from facility_ex1 import Requirement, PRODUCTS, LOCATIONS, Capacity
##from facility_test1 import Requirement, PRODUCTS, LOCATIONS, Capacity
##from facility_test2 import Requirement, PRODUCTS, LOCATIONS, Capacity
##from facility_test6 import Requirement, PRODUCTS, LOCATIONS, Capacity
prob = dippy.DipProblem("Facility_Location")
assign_vars = LpVariable.dicts("AtLocation",
[(i, j) for i in LOCATIONS
for j in PRODUCTS],
0, 1, LpBinary)
use_vars = LpVariable.dicts("UseLocation",
LOCATIONS, 0, 1, LpBinary)
waste_vars = LpVariable.dicts("Waste",
LOCATIONS, 0, Capacity)
# objective: minimise waste
prob += sum(waste_vars[i] for i in LOCATIONS), "min"
# assignment constraints
for j in PRODUCTS:
prob += sum(assign_vars[(i, j)] for i in LOCATIONS) == 1
# aggregate capacity constraints
for i in LOCATIONS:
prob.relaxation[i] += sum(assign_vars[(i, j)] * Requirement[j]
for j in PRODUCTS) + waste_vars[i] == \
Capacity * use_vars[i]
# disaggregate capacity constraints
for i in LOCATIONS:
for j in PRODUCTS:
prob.relaxation[i] += assign_vars[(i, j)] <= use_vars[i]
# ordering constraints
for n, i in enumerate(LOCATIONS):
if n > 0:
prob += use_vars[LOCATIONS[n-1]] >= use_vars[i]
# anti-symmetry branches
def choose_antisymmetry_branch(prob, sol):
num_locations = sum(sol[use_vars[i]] for i in LOCATIONS)
up = ceil(num_locations)
down = floor(num_locations)
if (up - num_locations > tol) and \
(num_locations - down > tol): # num_locations is fractional
# Define the down branch ubs, lbs = defaults
down_branch_ub = [(use_vars[LOCATIONS[n]], 0) for
n in range(int(down), len(LOCATIONS))]
# Define the up branch lbs, ubs = defaults
up_branch_lb = [(use_vars[LOCATIONS[n]], 1) for
n in range(0, int(up))]
return ([], down_branch_ub, up_branch_lb, [])
prob.branch_method = choose_antisymmetry_branch
def solve_subproblem(prob, index, redCosts, convexDual):
loc = index
## print "CUSTOMISED RELAXED SOLVER"
## print "Location = ", loc
## for j in PRODUCTS:
## print "redCosts for assign_vars[(", loc, ",", j, ")] =",
redCosts[assign_vars[(loc, j)]]
## print "redCosts for use_vars[", loc, "] =", redCosts[use_vars[loc]]
## print "redCosts for waste_vars[", loc, "] =",
redCosts[waste_vars[loc]]
# Calculate effective objective coefficient of products
effs = {}
for j in PRODUCTS:
effs[j] = redCosts[assign_vars[(loc, j)]] \
- redCosts[waste_vars[loc]] * Requirement[j]
vars = [assign_vars[(loc, j)] for j in PRODUCTS]
obj = [-effs[j] for j in PRODUCTS]
weights = [Requirement[j] for j in PRODUCTS]
# Use 0-1 KP to maximise total effective value of products at location
z, solution = knapsack01(obj, weights, Capacity)
# Get the reduced cost of the knapsack solution and waste
rc = redCosts[use_vars[loc]] -z + redCosts[waste_vars[loc]] * Capacity
waste = Capacity - sum(weights[i] for i in solution)
rc += redCosts[waste_vars[loc]] * waste
## print "z =", z, "rc = ", rc, ", convexDual =", convexDual, ",
solution =", solution
# Return the solution if the reduced cost is low enough
if rc < -tol: # The location is used and "useful"
if rc - convexDual < -tol:
var_values = [(vars[i], 1) for i in solution]
var_values.append((use_vars[loc], 1))
var_values.append((waste_vars[loc], waste))
dv = dippy.DecompVar(var_values, rc - convexDual, waste)
## print "var_values =", var_values
## print "rc =", rc - convexDual
## print "cost =", waste
return [dv]
elif -convexDual < -tol: # An empty location is "useful"
var_values = []
dv = dippy.DecompVar(var_values, -convexDual, 0.0)
## print "var_values =", var_values
## print "rc =", -convexDual
## print "cost =", 0.0
return [dv]
return []
##prob.relaxed_solver = solve_subproblem
def knapsack01(obj, weights, capacity):
""" 0/1 knapsack solver, maximizes profit. weights and capacity
integer """
assert len(obj) == len(weights)
n = len(obj)
if n == 0:
return 0, []
c = [[0]*(capacity+1) for i in range(n)]
added = [[False]*(capacity+1) for i in range(n)]
# c [items, remaining capacity]
# important: this code assumes strictly positive objective values
for i in range(n):
for j in range(capacity+1):
if (weights[i] > j):
c[i][j] = c[i-1][j]
else:
c_add = obj[i] + c[i-1][j-weights[i]]
if c_add > c[i-1][j]:
c[i][j] = c_add
added[i][j] = True
else:
c[i][j] = c[i-1][j]
# backtrack to find solution
i = n-1
j = capacity
solution = []
while i >= 0 and j >= 0:
if added[i][j]:
solution.append(i)
j -= weights[i]
i -= 1
return c[n-1][capacity], solution
def first_fit(prob):
lcs = []
sw = sorted(Requirement.items(), key=itemgetter(1), reverse=True)
unallocated = [s[0] for s in sw]
while len(unallocated) > 0:
lc = []
waste = Capacity
j = 0
while j < len(unallocated):
if Requirement[unallocated[j]] <= waste:
item = unallocated[j]
unallocated.remove(item)
lc.append(item)
waste -= Requirement[item]
else:
j += 1
lcs.append((lc, waste))
bvs = []
for k in range(len(lcs)):
loc = LOCATIONS[k]
lc = lcs[k][0]
waste = lcs[k][1]
var_values = [(assign_vars[(loc, j)], 1) for j in lc]
var_values.append((use_vars[loc], 1))
var_values.append((waste_vars[loc], waste))
dv = dippy.DecompVar(var_values, None, waste)
bvs.append((loc, dv))
return bvs
def one_each(prob):
bvs = []
for i, loc in enumerate(LOCATIONS):
lc = [PRODUCTS[i]]
waste = Capacity - Requirement[PRODUCTS[i]]
var_values = [(assign_vars[(loc, j)], 1) for j in lc]
var_values.append((use_vars[loc], 1))
var_values.append((waste_vars[loc], waste))
dv = dippy.DecompVar(var_values, None, waste)
bvs.append((loc, dv))
return bvs
##prob.init_vars = first_fit
##prob.init_vars = one_each
prob.writeLP('facility_main.lp')
for n, i in enumerate(LOCATIONS):
prob.writeRelaxed(n, 'facility_relax%s.lp' % i);
dippy.Solve(prob, {
'TolZero': '%s' % tol,
'doPriceCut': '1',
'generateInitVars': '1',
'LogDebugLevel': '5',
'LogDumpModel': '5',
})
# print solution
for i in LOCATIONS:
if use_vars[i].varValue > tol:
print "Location ", i, \
" produces ", \
[j for j in PRODUCTS
if assign_vars[(i, j)].varValue > tol]
--
Ticket URL: <https://projects.coin-or.org/Dip/ticket/76>
Dip <https://projects.coin-or.org/Dip>
An extensible software framework for implementing decompositon-based bounding algorithms for use in solving large-scale discrete optimization problems.
More information about the Dip-tickets
mailing list