If the solver "handles" non-convex quadratic constraints, the question becomes what "handle" means. If the solver guarantees a globally optimal solution, then the issue reduces to speed, and I honestly do not know which would be faster. I'm not sure how many solvers guarantee global optimality versus local optimality in this case. Linearizing results in a guaranteed optimal solution (assuming you have enough time and memory, which is itself not certain).
------------------------------
Paul Rubin
Professor Emeritus
Michigan State University
------------------------------
Original Message:
Sent: Sun June 13, 2021 12:37 AM
From: Bhartendu Awasthi
Subject: Using quadratic constraint(s) with multi-objective function (docplex)
Thank you Dr Rubin for the ingenious work around. I certainly can linearize the product of a continuous and a binary variable.
Just had one general follow up question - in case the solver (i know some solvers have the capability to solve Non convex QCP) has the capability to handle quadratic constraints (non - convex), then is there a merit in linearizing ? Would the solver speed be higher if we linearize the constraints. Pardon me if this question does not make much sense, I am relatively new to the world of mathematical programming.
Thanks again,
------------------------------
Bhartendu Awasthi
Original Message:
Sent: Sat June 12, 2021 02:15 PM
From: Paul Rubin
Subject: Using quadratic constraint(s) with multi-objective function (docplex)
If T, A and x_i are respectively the total margin, average margin and indicators for number of items, then T = A * sum_i x_i = sum_i (A * x_i). That is still quadratic (and nonconvex), but assuming you know bounds on the average margin you can now linearize each of the products A * x_i using some additional continuous variables and some additional constraints (https://orinanobworld.blogspot.com/2010/10/binary-variables-and-quadratic-terms.html).
------------------------------
Paul Rubin
Professor Emeritus
Michigan State University
Original Message:
Sent: Sat June 12, 2021 02:32 AM
From: Bhartendu Awasthi
Subject: Using quadratic constraint(s) with multi-objective function (docplex)
I am building an multi-objective optimization model with a quadratic constraint. However, when I solve the model I get the following error :
CPLEX Error 1031: Not available for QCP
When I replace multi-objective function with the single objective objective function, I get the following error :
CPLEX Error 5002: 'q1' is not convex.
I am enclosing the code. There is one quadratic constraint that gets introduced as I need to calculate the average margin (total margin / number of items). Now, both numerator and denominator expression have decision variables, I have used logical constraints (using indicator variables to get my way through). Is there any other way of calculating average, without making the constraint quadratic ?
mdl = Model('assortment_optimization')sku_binary_var = mdl.binary_var_dict(skus, lb = 0, ub = 1, name = lambda p: '%s' % p)num_sku_selected = mdl.integer_var(name = 'total_selected_sku')mdl.add_constraint(num_sku_selected == mdl.sum(sku_binary_var[i] for i in skus))mdl.add_constraint(mdl.sum(sku_binary_var[i] * sku_char[i]['shelf_capacity'] * sku_char[i]['item_cbm'] for i in skus) <= VOLUME_CAPACITY_CBM, ctname = 'volume_constraint')mdl.add_constraint(mdl.sum(sku_binary_var[i] * sku_char[i]['shelf_capacity'] * sku_char[i]['cost'] for i in skus) <= MAX_COST, ctname = 'cost_constraint')# mdl.add_constraint(mdl.sum(sku_binary_var[i] for i in skus) <= 233)tot_margin = mdl.continuous_var(name = 'tot_margin')avg_margin = mdl.continuous_var(name = 'avg_margin')mdl.add_constraint(tot_margin == mdl.sum(sku_binary_var[i] * sku_char[i]['avg_wk_sales_units'] * sku_char[i]['margin'] for i in skus))# indicator constraints to help calculate average marginindic_varbs = mdl.binary_var_dict(range(1, len(skus)+1))for i in range(1, len(skus)+1): mdl.add_indicator(indic_varbs[i], num_sku_selected == i, active_value = 1)mdl.add_constraint(mdl.sum(indic_varbs[i] for i in range(1, len(skus)+1)) == 1)# this becomes a quadratic constraintmdl.add_constraint(avg_margin == tot_margin * mdl.sum(indic_varbs[i] * (1 / i) for i in range(1, len(skus) + 1)))mdl.add_constraint(avg_margin >= 8)mdl.add_kpi(num_sku_selected, 'Number of SKUs in the new assortment')# below are the objectives that I'd like to maximizeobj_margin = mdl.sum(sku_binary_var[i] * sku_char[i]['avg_wk_sales_units'] * sku_char[i]['margin'] for i in skus)obj_freq = mdl.sum(sku_binary_var[i] * sku_char[i]['freq_trans'] for i in skus)obj_unique = mdl.sum(sku_binary_var[i] * sku_char[i]['uniq_factor'] for i in skus)# mdl.maximize(obj_margin)mdl.maximize_static_lex(exprs=[obj_margin, obj_freq, obj_unique])mdl.solve(log_output=True)
------------------------------
Bhartendu Awasthi
------------------------------
#DecisionOptimization