我们从Python开源项目中，提取了以下7个代码示例，用于说明如何使用scipy.optimize.linprog()。
def _mario_helper(bands, s, poly_order, opts, callback): # Build the polynomial basis over the bands. P = hermvander(bands, poly_order - 1) f = P.sum(axis=0) if HAS_CVXOPT: solvers.options['show_progress'] = opts['disp'] solvers.options['maxiters'] = opts['maxiter'] solvers.options['abstol'] = opts['tol'] solvers.options['reltol'] = opts['tol'] solvers.options['feastol'] = 1e-100 # For some reason this helps. try: res = solvers.lp(cvx_matrix(f), cvx_matrix(-P), cvx_matrix(-s)) except ValueError as e: # This can be thrown when poly_order is too large for the data size. res = {'status': e.message, 'x': None} return res, P res = linprog(f, A_ub=-P, b_ub=-s, bounds=(-np.inf, np.inf), options=opts, callback=callback) res = {'status': res.message, 'x': res.x if res.success else None} return res, P
def additive_valuation_approximation(all_bids, i): """ All bidders are either unit-demand or not. For non-unit-demand bidders, performs linear programming to minimize estimated v_ij for each item j given Av = b, where each A(r, :) indicates items in bundle and b(r) indicates corresponding bid. Then adds all estimated bids for all bundles in power set of union of bundles bidder i submitted a bid for. """ all_items = list(set.union(*(set.union(*(items for items, bid in bids)) for bids in all_bids))) item_to_idx = {item: i for i, item in enumerate(all_items)} def gen_approximate_bids(bids): v_bounds = (0, None) A = np.array([[-1 if item in items else 0 for item in all_items] for items, bid in bids]) b = np.array([-bid for items, bid in bids]) v = linprog(np.ones(len(all_items)), A_ub=A, b_ub=b, bounds=v_bounds)['x'] def approximate_bid(items): return sum(v[item_to_idx[item]] for item in items) bidder_items = set.union(*(items for items, bid in bids)) return [(set(subset), approximate_bid(subset)) for subset in powerset(bidder_items)] return [bids if is_unit_demand(bids) else gen_approximate_bids(bids) for bids in all_bids]
def _compute_probabilities(self, lists, rankings): ''' Solve the optimization problem in (Multileaved Comparisons for Fast Online Evaluation, CIKM'14) lists: lists of document IDs rankings: a list of Ranking instances Return a list of probabilities for input rankings ''' # probability constraints A_p_sum = np.array([1]*len(rankings)) # unbiasedness constraints ub_cons = self._unbiasedness_constraints(lists, rankings) # sensitivity sensitivity = self._sensitivity(lists, rankings) # constraints A_eq = np.vstack((A_p_sum, ub_cons)) b_eq = np.array([1.0] + [0.0]*ub_cons.shape[0]) # solving the optimization problem res = linprog(sensitivity, # objective function A_eq=A_eq, b_eq=b_eq, # constraints bounds=[(0, 1)]*len(rankings) # 0 <= p <= 1 ) return res.success, res.x, res.fun
def find_feasible_point(halfspaces): """ Use linear programming to find a point inside the halfspaces (needed to define it). Code taken from scipy documentation: https://docs.scipy.org/doc/scipy-0.19.0/reference/generated/scipy.spatial.HalfspaceIntersection.html Parameters ---------- halfspaces: a matrix representation of halfspaces Returns: -------- numpy array """ norm_vector = np.reshape(np.linalg.norm(halfspaces[:, :-1], axis=1), (halfspaces.shape[0], 1)) c = np.zeros((halfspaces.shape[1],)) c[-1] = -1 A = np.hstack((halfspaces[:, :-1], norm_vector)) b = - halfspaces[:, -1:] res = linprog(c, A_ub=A, b_ub=b) return res.x[:-1]
def k_gamma_calc(A,b,c): # use scipy.optimize.linprog """ from scipy.optimize import linprog k_bounds = (0, None) # k >= 1, i.e. log(k) >= 0 gamma_bounds = (None, None) res = linprog(c, A_ub=A, b_ub=b, bounds=(k_bounds, gamma_bounds)) k = exp(res.x[0]) gamma = res.x[1] """ # use glpk lp = glpk.LPX() lp.name = 'logk_gamma' lp.obj.maximize = False # set this as a minimization problem lp.rows.add(len(A)) # append rows to this instance for i in range(len(b)): lp.rows[i].bounds = None, b[i] # set bound: entry <= b[i] lp.cols.add(2) # append two columns for k and gamma to this instance lp.cols[0].name = 'logk' lp.cols[0].bounds = 0.01, 10.0 # k >= 1, i.e. log(k) >= 0 lp.cols[1].name = 'gamma' lp.cols[1].bounds = None, None # no constraints for gamma lp.obj[:] = c # set objective coefficients lp.matrix = np.ravel(A) # set constraint matrix; convert A to 1-d array lp.simplex() # solve this LP with the simplex method k = exp(lp.cols[0].primal) gamma = lp.cols[1].primal return k, gamma #Main part # start = time.time() # dim = 1 # dimension index of the variable we want to calculate coefficients for
def solve(self): """Solves linear program. :return: solution vector """ lp_solution = linprog( self.linear_program.objective_function_coefficients, A_eq=self.linear_program.equality_constraint_matrix or None, b_eq=self.linear_program.equality_constraint_vector or None, A_ub=self._make_upper_constraint_matrix() or None, b_ub=self._make_upper_constraint_vector() or None, bounds=self.linear_program.bounds, options={"disp": False}) self._check_errors(lp_solution) # Naive implementation of getting integer result # from a linear programming algorithm, MIP # (mixed integer programming) should be considered # instead, but it may have a lot of problems (solution # of such equations is NP-hard in some cases), # for our practical purposes it's enough to round # the number down, in this case we may get `n` megabytes # unallocated, where n is len(spaces) * len(disks) solution_vector = utils.round_vector_down(lp_solution.x) return solution_vector
def run_LP(num_types,names,prices,procs,gbRAM,freestorage,max_cost_in_previous_time_window,account_limits,min_cores,min_ram,min_free_storage,max_cost_hour,ram_per_job,procs_per_job,aws_instances): c = prices A_i = [procs,gbRAM,freestorage] b_i = [min_cores,min_ram,min_free_storage] A = map(lambda x: map(lambda y:y*-1,x),A_i) b = map(lambda z: z*-1,b_i) for i in range(0,num_types): append_a = [0] * num_types append_a[i] = 1 add_a = append_a+append_a A.append(add_a) b.append(account_limits[i]) A_limits = [] b_limits = [] for i in range(0,num_types): a_arr = [0]*num_types a_arr[i] = 1 new_a = a_arr+a_arr A_limits.append(new_a) b_limits.append(account_limits[i]) cost = 0 status = 4 while status != 0: A_t = A b_t = b if cost > max_cost_hour: break cost+=1 A_t.append(max_cost_in_previous_time_window) b_t.append(cost) #print("solving:"+str(A_t)+"*x="+str(b_t)) bounds_input = map(lambda x: (0,x),account_limits) lp_output = linprog(c,A_ub=A_t,b_ub=b_t,bounds=tuple(bounds_input)) #print("x="+str(lp_output.x)+"\n\n") #lp_output = linprog(c,A_ub=A_t,b_ub=b_t,bounds=tuple(bounds_input),options={"bland": True}) status=lp_output.status A_t.pop() b_t.pop() if status == 0: break lp_output_n = linprog(c,A_ub=A,b_ub=b,bounds=tuple(bounds_input),options={"bland": True}) return lp_output,lp_output_n
