代码编织梦想

I will introduce how to use gurobi to solve a QP with 0/1 variables on python env.

Gurobi is a canonical solver to solve integer programming. I postulate you have mastered basic operations for python. This blog mainly contains three part:

1) Present QP with 0/1 variables;

2) Introduce how to install Gurobi and apply Academic license;

3) Give a specific code to solve given problem.

Now, let's begin.

I Problem model

We focus on this QP problem with 0/1 variables(01-QP):

\min_{x\in R^n} \|Ax-b\|^2\\ s.t., x_i\in\{0,1\}.                                                                  (1)

The main troble of this problem is 0/1 variables. Strictly, this is a NP hard problem. However, there are many commercial  software that can solve it with heuristic algorithm, such as Gurobi and cplex. By the way, Gurobi is the most famous solver.

II. How to install Gurobi and apply Academic license

I recommaned you to use colab provied by Google, since Gurobi is very nicely  embedded in colab. Next we just need to apply a academic license to solve large scale problem.

Following the instruction step by step of https://support.gurobi.com/hc/en-us/articles/4409582394769-Google-Colab-Installation-and-Licensing

More specifically, apply an account in https://www.gurobi.com/account/    

Sign in and click on the following red circle

Then click on the following red circle 

 Notice that your school maybe unable to allow to get a License sometimes.

III Sovle it.

In this part, we solve 01-QP(1) by python use gurobi on colab with m=n=50.

!pip install gurobipy  # install gurobipy, if not already installed
import gurobipy as gp
# Create environment with WLS license
import pandas as pd
from gurobipy import GRB

e = gp.Env(empty=True)
e.setParam('WLSACCESSID', '****************')
e.setParam('WLSSECRET', '***************')
e.setParam('LICENSEID', ******)
e.start()
# # Create the model within the Gurobi environment
model = gp.Model(env=e)

m = gp.Model("miqp", env=e)

# m = gp.Model("qp")
import numpy as np
# Create variables
n = 50
np.random.seed(2)
A0 = 10 * np.random.uniform(-2 / 10, 2 / 3, size=(n, n))
A = np.ceil(A0)
x_or = 10 * np.random.uniform(-5, 5, size=(n, 1))
x_or = np.ceil(x_or)
x_or /= (np.linalg.norm(x_or, axis = 1)).reshape((n,1))
x_or *= (x_or > 0)
b = np.ceil(np.dot(A, x_or))

# A =   10000 * np.array([[2, 0, 9], [7, 1, 10], [0, 1, 1]])
# b0 = 10000 * np.array([9, 11, 2])
Q = np.dot(A.T, A)
b1 = np.dot(b.T, A)
x = m.addMVar(n, vtype=GRB.BINARY)
print("Test{}.".format(np.dot(b.T, b)))
obj = x @ Q  @ x - 2 * b1 @ x + np.dot(b.T, b)
m.setObjective(obj, gp.GRB.MINIMIZE)
m.update()
# # Add constraint: x + 2 y + 3 z >= 4
# m.addConstr(x + 2 * y + 3 * z >= 4, "c0")

# # Add constraint: x + y >= 1
# m.addConstr(x + y >= 1, "c1")

m.optimize()

print('Obj: %g' % obj.getValue())
x_best = (x.x).reshape((n,1))

print("error:{}.".format(np.linalg.norm(x_or - x_best)))

That's the end. Have a good day, dude.

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/nobles007820/article/details/127117047

[阅读] 偶尔一本经典书:by g. polya-爱代码爱编程

        随着学的越深,越发现影响一个人将来发展的东西其实一直都没变:①对某个领域的先验知识 ②个人的思维方式。         对某个领域的知识,随着学习的深入,我们总能掌握它,当然,这是在不考虑难度的情况下,毕竟越深入的东西,需要的高智商是不可或缺的,智商在这里我更想理解成思维方式。同样一个问题,放在2个人面前,其中一个可能一下就解决了,而另一

how to solve the problem in ubuntu: sub-process /usr/bin/dpkg returned an error code (1)_qwfys200的博客-爱代码爱编程

ubuntu错误解决E: Sub-process /usr/bin/dpkg returned an error code (1) lwk@qwfys ~ $ sudo apt-get update --fix-missi

ubuntu18.04 apt-getupdate 遇到问题解决_南山_居士的博客-爱代码爱编程

#sudo apt-get update 遇到错误 Err:1 http://mirrors.aliyun.com/ubuntu xenial InRelease Could not resolve ‘mirrors.ali

gurobi的申请+安装+权限过期(gurobi.lic过期)-爱代码爱编程

开代理网址:https://www.gurobi.com   注册 My account的位置有register,点击注册,输入注册信息   登录,点击同样位置的login申请licence(download&licence->academic license) 复制licence   下载软件 downl

IMPORTANT: PLEASE READ THIS FOR ADVICE ON HOW TO SOLVE THIS ISSUE!解决方法-爱代码爱编程

在捣鼓树莓派获取传感器数据时,执行import numpy时报错 错误信息一大段如下,按照其中的错误信息去网上搜寻解决方法 root@raspberrypi:/home/pi/agri# python3 Python 3.5.3 (default, Sep 27 2018, 17:25:39) [GCC 6.3.0 20170516] on linux

fix: brew: Permission denied @ apply2files - /usr/local/lib/node_modules/webpack/es/ters-brow-爱代码爱编程

文章目录 main solveother 1other 2 main solve other 1 MAC安装openssl报错 Permission denied @ apply2files 2019.12.27 15:11:03 字数 25 阅读 249 报错如下: Error: Permission denied @ apply2

[自动控制原理] Matlab求解二阶系统阶跃响应(过阻尼)响应时间ts的ts/T1-T1/T2曲线方法(模拟二阶系统的阶跃响应及其性能分析)-爱代码爱编程

学习“二阶系统的阶跃响应的性能分析”之后,每次用T1/T2求解ts时,都'只能查表获得'(这是老师说的哈),为了更方便地求得更加精确地ts/T1值,编写了此函数,也对二阶系统的阶跃响应有了一些了解(我可能自控原理不太好QAQ) 最初我考虑直接使用solve来求解,直接输入函数,但matlab提示错误“Unable to find explicit s

gurobi学习笔记1OR-Tools约束规划(1)-爱代码爱编程

OR-tools OR-Tools约束规划核心步骤: 1,声明模型—,2,创建变量——3,创建约束条件—,4,创建约束条件(或者可行解)——5,调用求解器—,6,展示结果 #导入OR-Tools中的CP-SAT求解器中的cp_model模块 from ortools.sat.python import cp_model ortools.sat.pyt