0

I am currently developing a solver to return an optimized set of questions based off of an item response theory 3pl equation.

Initially I developed this without any "elasticity" in the constraints, to meet specific targets. However I found the results were often returned as infeasible, though it worked properly. The inflexibility of the constraint targets were causing issues.

I've since refactored a bit to utilize elastic constraints to allow for a range +/- for each target.

An example is listed below (only showing a single target constraint...there are several however):

self.solver_run.items = #list of items
self.solver_run.bundles = #list of bundles

# setup vars
items = LpVariable.dicts(
    "Item", [item.id for item in self.solver_run.items],
    lowBound=1,
    upBound=1,
    cat='Binary')
bundles = LpVariable.dicts(
    "Bundle", [bundle.id for bundle in self.solver_run.bundles],
    lowBound=1,
    upBound=1,
    cat='Binary')

problem = LpProblem("ata-form-generate", LpMinimize)
problem_objective_functions = []

# constraints - limit number of items used (for example 10)
problem += lpSum(
    [
        bundle.count * bundles[bundle.id]
        for bundle in self.solver_run.bundles
    ] + [
        1 * items[item.id]
        for item in self.solver_run.unbundled_items()
    ]
) == self.solver_run.total_form_items, 'Total bundle form items for form'

# create objective function
tcc = lpSum([
    bundle.trf(self.solver_run.irt_model, target.theta) *
    bundles[bundle.id] for bundle in self.solver_run.bundles
] + [
    item.irf(self.solver_run, target.theta) * items[item.id]
    for item in self.solver_run.items
])
...
problem_objective_functions.append(tcc)

e = LpAffineExpression(
    [(bundles[bundle.id],
      bundle.trf(self.solver_run.irt_model, target.theta))
     for bundle in self.solver_run.bundles] +
      [(items[item.id], item.irf(self.solver_run, target.theta))
     for item in self.solver_run.items])
constraint = LpConstraint(
    e=e,
    sense=0,
    name=f'trf theta ({target.theta}) @{target.value}',
    rhs=target.value)
elastized_constraint = constraint.makeElasticSubProblem(
    penalty=1, proportionFreeBound=0.25)
problem.extend(elastized_constraint)
...

problem.sequentialSolve(problem_objective_functions)

The target value I am providing for the right hand side of the LpConstraint is 20.00 however I know in testing the resulting sum is ~0.01 - 0.02. I set this target to make sure the optimazation failed. However it still passes.

In inspecting the constructed problem, I see:

...

SUBJECT TO
Total_bundle_form_items_for_form: 3 Bundle_1 + 3 Bundle_2 + 5 Bundle_3
 + Bundle_4 + 4 Bundle_5 + 2 Bundle_6 + Item_20 + Item_21 + Item_22 + Item_23
 + Item_24 + Item_25 + Item_26 + Item_27 + Item_28 + Item_29 + Item_30
 + Item_34 = 10

...

tcc_theta_(_2.5)_@20.0_elastic_SubProblem_Constraint: 0.0102267186003 Bundle_1
+ 0.00689950699362 Bundle_2 + 0.0114991783227 Bundle_3
+ 0.00229983566454 Bundle_4 + 0.00919934265816 Bundle_5
+ 0.00459967132908 Bundle_6 + 0.00229983566454 Item_10
+ 0.00229983566454 Item_11 + 0.00229983566454 Item_12
+ 0.00229983566454 Item_13 + 0.00229983566454 Item_14
+ 0.00229983566454 Item_15 + 0.00229983566454 Item_16
+ 0.00229983566454 Item_17 + 0.00229983566454 Item_18
+ 0.00229983566454 Item_19 + 0.00229983566454 Item_20
+ 0.00229983566454 Item_21 + 0.00229983566454 Item_22
+ 0.00229983566454 Item_23 + 0.00229983566454 Item_24
+ 0.00229983566454 Item_25 + 0.00229983566454 Item_26
+ 0.00229983566454 Item_27 + 0.00229983566454 Item_28
+ 0.00229983566454 Item_29 + 0.00229983566454 Item_30
+ 0.00229983566454 Item_32 + 0.00229983566454 Item_33
+ 0.00229983566454 Item_34 + 0.00562704727121 Item_4
+ 0.00229983566454 Item_6 + 0.00229983566454 Item_7
+ 0.00229983566454 Item_75 + 0.00229983566454 Item_8
+ 0.00229983566454 Item_9
+ tcc_theta_(_2.5)_@20.0_elastic_SubProblem_free_bound
+ tcc_theta_(_2.5)_@20.0_elastic_SubProblem_neg_penalty_var
+ tcc_theta_(_2.5)_@20.0_elastic_SubProblem_pos_penalty_var = 20

...

 VARIABLES
 0 <= Bundle_1 <= 1 Integer
 0 <= Bundle_2 <= 1 Integer
 0 <= Bundle_3 <= 1 Integer
 0 <= Bundle_4 <= 1 Integer
 0 <= Bundle_5 <= 1 Integer
 0 <= Bundle_6 <= 1 Integer
 0 <= Item_10 <= 1 Integer
 0 <= Item_11 <= 1 Integer
 0 <= Item_12 <= 1 Integer
 0 <= Item_13 <= 1 Integer
 0 <= Item_14 <= 1 Integer
 0 <= Item_15 <= 1 Integer
 0 <= Item_16 <= 1 Integer
 0 <= Item_17 <= 1 Integer
 0 <= Item_18 <= 1 Integer
 0 <= Item_19 <= 1 Integer
 0 <= Item_20 <= 1 Integer
 0 <= Item_21 <= 1 Integer
 0 <= Item_22 <= 1 Integer
 0 <= Item_23 <= 1 Integer
 0 <= Item_24 <= 1 Integer
 0 <= Item_25 <= 1 Integer
 0 <= Item_26 <= 1 Integer
 0 <= Item_27 <= 1 Integer
 0 <= Item_28 <= 1 Integer
 0 <= Item_29 <= 1 Integer
 0 <= Item_30 <= 1 Integer
 0 <= Item_32 <= 1 Integer
 0 <= Item_33 <= 1 Integer
 0 <= Item_34 <= 1 Integer
 0 <= Item_4 <= 1 Integer
 0 <= Item_6 <= 1 Integer
 0 <= Item_7 <= 1 Integer
 0 <= Item_75 <= 1 Integer
 0 <= Item_8 <= 1 Integer
 0 <= Item_9 <= 1 Integer
 -5 <= tcc_theta_(_2.5)_@20.0_elastic_SubProblem_free_bound <= 5 Continuous
 -inf <= tcc_theta_(_2.5)_@20.0_elastic_SubProblem_neg_penalty_var <= 0 Continuous
 tcc_theta_(_2.5)_@20.0_elastic_SubProblem_pos_penalty_var Continuous

It may be my lack of understanding of how the penalty attributes works, or how elastic constraints work in general. It seems to be creating the free bound correctly (-5 <= tcc_theta_(_2.5)_@20.0_elastic_SubProblem_free_bound <= 5 Continuous). So why is it always returning Optimal even when the result of the sum is outside the target bounds?

References:

https://coin-or.github.io/pulp/guides/how_to_elastic_constraints.html

https://coin-or.github.io/pulp/technical/pulp.html#pulp.LpConstraint

https://groups.google.com/g/pulp-or-discuss/c/_qH73ylmhME/m/nuufhPDcGB4J

How Can an Elastic SubProblem in PuLP be used as a Constraint?

jshbrmn
  • 1,737
  • 3
  • 22
  • 52

1 Answers1

0

Your example is confusing and incomplete in several areas, so it isn't possible to replicate it well. I'd suggest editing it to something slimmed down that reproduces the behavior you are seeing.

That said, you are improperly constraining your variables. For binary variables in pulp you implicitly have bounds of [0, 1]. You are unnecessarily declaring them, and you are setting a lowbound equal to 1, so right now, all of your variables are pinned at 1. Try fixing that first, and if necessary, perhaps whittle down your example to something more easily reproducible.

AirSquid
  • 10,214
  • 2
  • 7
  • 31