# binmodel

Tags:

Updated:

binmodel converts polynomial expressions involving binary and continuous variables to linear expressions by introducing additional variables and constraints.

### Syntax

[plin1,...,plinN,F] = binmodel(p1,...,pN,Domain)


### Examples

The following example solves a quadratic program with binary variables using a mixed integer linear programming solver, by first converting the quadratic function to a linear expression

x = binvar(5,1);
Q = randn(5);

p = x'*Q*x;
[plinear,F] = binmodel(p)
optimize(F,plinear)


Of course, for this to work, you need a mixed integer linear programming solver (or in the worst-case, BNB together with a linear programming solver).

Products between continuous and binary variables are also supported, but for the big-M modelling to work, you have to specify bounds on the continuous variables

x = binvar(5,1);
y = sdpvar(5,1);
Q = randn(5);
p = x'*Q*y;
[plinear,F] = binmodel(p,[-2 <= y <= 2]);
optimize(F,plinear)


### Comment

The derivation of the linear model is based on simple logic and big-M modelling. A product of two binary variables x and y is replaced with a new binary variable z and the constraints

[z <= x, z <= y, z>= x+y-1];


This idea can be generalized to arbitrary polynomials in binary variables. A product between a binary variable x and a continuous variable w, with known lower and upper bounds L and U, is replaced by a new continuous variable v and the constraints

[ L*x <= v <= x*U, L*(1-x) <= w-v <= U*(1-x)]
optimize(F,plinear)


This can be generalized to expressions having arbitrarily polynomial w.r.t the binary variable.
{"ft_lang_label":"__label__en","ft_lang_prob":0.8557893,"math_prob":0.9980994,"size":1587,"snap":"2020-45-2020-50","text_gpt3_token_len":387,"char_repetition_ratio":0.14845231,"word_repetition_ratio":0.016393442,"special_character_ratio":0.25015754,"punctuation_ratio":0.15047021,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9997367,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2020-11-26T09:40:59Z\",\"WARC-Record-ID\":\"<urn:uuid:4c3c1aa0-5b0c-476a-a498-414d2502f725>\",\"Content-Length\":\"33689\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:486b3025-0cc8-413e-bf22-237ccb409add>\",\"WARC-Concurrent-To\":\"<urn:uuid:2d075de3-6aa4-4c88-b0ea-dc90ba9bb56f>\",\"WARC-IP-Address\":\"185.199.110.153\",\"WARC-Target-URI\":\"https://yalmip.github.io/command/binmodel/\",\"WARC-Payload-Digest\":\"sha1:JLOP5JZ744CHLNU4KVFYUUBMBM4NLIPE\",\"WARC-Block-Digest\":\"sha1:EWL75P5N56OSESRRHRA7DJOREDRZRJXM\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2020/CC-MAIN-2020-50/CC-MAIN-2020-50_segments_1606141187753.32_warc_CC-MAIN-20201126084625-20201126114625-00269.warc.gz\"}"}