Fdtxjr

What is better: yes / no radio, or simple checkbox?

Are all players supposed to be able to see each others' character sheets?

Finding the minimum value of a function without using Calculus

Yet another question on sums of the reciprocals of the primes

Rationale to prefer local variables over instance variables?

Can one live in the U.S. and not use a credit card?

Optimal Proportions for Flying Humans

Help! My Character is too much for her story!

The (Easy) Road to Code

What is the purpose of a disclaimer like "this is not legal advice"?

Under what conditions can the right to be silence be revoked in the USA?

How do you make a gun that shoots melee weapons and/or swords?

Volume of hyperbola revolved about the y -axis

The preposition for the verb (avenge) - avenge sb/sth (on OR from) sb

If nine coins are tossed, what is the probability that the number of heads is even?

Locked Away- What am I?

Are E natural minor and B harmonic minor related?

When an outsider describes family relationships, which point of view are they using?

(Codewars) Linked Lists-Sorted Insert

If sound is a longitudinal wave, why can we hear it if our ears aren't aligned with the propagation direction?

Logistic regression BIC: what's the right N?

Smooth vector fields on a surface modulo diffeomorphisms

Professor forcing me to attend a conference, I can't afford even with 50% funding

What can I do if someone tampers with my SSH public key?

Integer programming, elimination of products of variables and transfer it to linear integer program

Linear Programming for Integer SolutionsInteger linear programming, energy constrained max-flow problem, column generationInteger ProgrammingFormulating a bilinear optimization problem as an integer linear programHow do I convert a constraint with a product of two integer variables to a linear constraint?Zero-one linear programming with substitutable constraintsMixed Integer Linear Programming Conditional ConstraintsSubset sum variation integer linear programHow to model a changing constraint in linear programming?maximizing absolute value in linear programming

0

$begingroup$

I have a constraint of the form:

$a_1*a_2 = b_12$

where $a_1$ and $a_2$ are integer variables with ranges $a_1∈[0,1,2,...,m]$, $a_2∈[0,1,2,...,n]$, and $b_12∈[0,1,2,...,m*n]$.

I would want to eliminate the product $a_1*a_2$ to make this constraint linear.

If $a_1$ and $a_2$ do not equal to $0$, I can use the $log(a_1*a_2)= log(b_12)$ to convent it into

$log(a_1) +log(a_2) = log(b_12)$, and then use the pre-defined discrete set to transform it into a linear constraitn with binary vectors. such as

$x_1= log([0,1,2,...,m]) , x_2= log([0,1,2,...,n])$, and $y= log([0,1,2,...,m*n])$.

$x_1*c1 +x_2*c2 = y*d$ where $c_1, c2, d$ are binary vectors and only one element is 1.

However, as in my model, the feasible set of $a_1$ and $a_2$ has 0 element. The "$log$" trick cannot be used as $log(0)$ has no meaning.

It would be a great help if someone could help me out at this.

Thanks a lot.

integer-programming

share|cite|improve this question

edited 2 days ago

Quentin

asked Mar 6 at 4:33

QuentinQuentin

11

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  What is the connection between $a_1, a_2$ and $x_1, x_2$?
  $endgroup$
  – prubin
  Mar 6 at 20:25
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I'm sorry. I made a typo. I have correct this issue. $x_1$ and $x_2$ should be $a_1$ and $a_2$. Do you have any idea? Highly appreciate your help.
  $endgroup$
  – Quentin
  2 days ago
  

  
  
  
  

add a comment | 

0

$begingroup$

I have a constraint of the form:

$a_1*a_2 = b_12$

where $a_1$ and $a_2$ are integer variables with ranges $a_1∈[0,1,2,...,m]$, $a_2∈[0,1,2,...,n]$, and $b_12∈[0,1,2,...,m*n]$.

I would want to eliminate the product $a_1*a_2$ to make this constraint linear.

If $a_1$ and $a_2$ do not equal to $0$, I can use the $log(a_1*a_2)= log(b_12)$ to convent it into

$log(a_1) +log(a_2) = log(b_12)$, and then use the pre-defined discrete set to transform it into a linear constraitn with binary vectors. such as

$x_1= log([0,1,2,...,m]) , x_2= log([0,1,2,...,n])$, and $y= log([0,1,2,...,m*n])$.

$x_1*c1 +x_2*c2 = y*d$ where $c_1, c2, d$ are binary vectors and only one element is 1.

However, as in my model, the feasible set of $a_1$ and $a_2$ has 0 element. The "$log$" trick cannot be used as $log(0)$ has no meaning.

It would be a great help if someone could help me out at this.

Thanks a lot.

integer-programming

share|cite|improve this question

edited 2 days ago

Quentin

asked Mar 6 at 4:33

QuentinQuentin

11

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  What is the connection between $a_1, a_2$ and $x_1, x_2$?
  $endgroup$
  – prubin
  Mar 6 at 20:25
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I'm sorry. I made a typo. I have correct this issue. $x_1$ and $x_2$ should be $a_1$ and $a_2$. Do you have any idea? Highly appreciate your help.
  $endgroup$
  – Quentin
  2 days ago
  

  
  
  
  

add a comment | 

$begingroup$

I have a constraint of the form:

$a_1*a_2 = b_12$

where $a_1$ and $a_2$ are integer variables with ranges $a_1∈[0,1,2,...,m]$, $a_2∈[0,1,2,...,n]$, and $b_12∈[0,1,2,...,m*n]$.

I would want to eliminate the product $a_1*a_2$ to make this constraint linear.

If $a_1$ and $a_2$ do not equal to $0$, I can use the $log(a_1*a_2)= log(b_12)$ to convent it into

$log(a_1) +log(a_2) = log(b_12)$, and then use the pre-defined discrete set to transform it into a linear constraitn with binary vectors. such as

$x_1= log([0,1,2,...,m]) , x_2= log([0,1,2,...,n])$, and $y= log([0,1,2,...,m*n])$.

$x_1*c1 +x_2*c2 = y*d$ where $c_1, c2, d$ are binary vectors and only one element is 1.

However, as in my model, the feasible set of $a_1$ and $a_2$ has 0 element. The "$log$" trick cannot be used as $log(0)$ has no meaning.

It would be a great help if someone could help me out at this.

Thanks a lot.

integer-programming

share|cite|improve this question

edited 2 days ago

Quentin

asked Mar 6 at 4:33

QuentinQuentin

11

$endgroup$

share|cite|improve this question

edited 2 days ago

Quentin

asked Mar 6 at 4:33

QuentinQuentin

11

share|cite|improve this question

edited 2 days ago

Quentin

asked Mar 6 at 4:33

QuentinQuentin

11

asked Mar 6 at 4:33

QuentinQuentin

11

asked Mar 6 at 4:33

QuentinQuentin

11

1 Answer
1

active

oldest

votes

0

$begingroup$

If you are willing to use binary expansions, you do not need logs. Using your notation, let $c_1,0,dots, c_1,m$, $c_2,0,dots, c_2,n$ and $d_0,dots, d_m*n$ be binary variables, with each set summing to 1. Add the following constraints:$$d_0 ge c_1,0$$$$d_0 ge c_2,0$$and$$d_j*kge c_1,j + c_2,k - 1quadforall jge 1,kge 1.$$

share|cite|improve this answer

answered yesterday

prubinprubin

1,505125

$endgroup$

add a comment | 

Your Answer

StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
);
);
, "mathjax-editing");

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "69"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name

Email

Required, but never shown

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3137077%2finteger-programming-elimination-of-products-of-variables-and-transfer-it-to-lin%23new-answer', 'question_page');

);

Post as a guest

Name

Email

Required, but never shown

0

$begingroup$

If you are willing to use binary expansions, you do not need logs. Using your notation, let $c_1,0,dots, c_1,m$, $c_2,0,dots, c_2,n$ and $d_0,dots, d_m*n$ be binary variables, with each set summing to 1. Add the following constraints:$$d_0 ge c_1,0$$$$d_0 ge c_2,0$$and$$d_j*kge c_1,j + c_2,k - 1quadforall jge 1,kge 1.$$

share|cite|improve this answer

answered yesterday

prubinprubin

1,505125

$endgroup$

add a comment | 

0

$begingroup$

If you are willing to use binary expansions, you do not need logs. Using your notation, let $c_1,0,dots, c_1,m$, $c_2,0,dots, c_2,n$ and $d_0,dots, d_m*n$ be binary variables, with each set summing to 1. Add the following constraints:$$d_0 ge c_1,0$$$$d_0 ge c_2,0$$and$$d_j*kge c_1,j + c_2,k - 1quadforall jge 1,kge 1.$$

share|cite|improve this answer

answered yesterday

prubinprubin

1,505125

$endgroup$

add a comment | 

$begingroup$

If you are willing to use binary expansions, you do not need logs. Using your notation, let $c_1,0,dots, c_1,m$, $c_2,0,dots, c_2,n$ and $d_0,dots, d_m*n$ be binary variables, with each set summing to 1. Add the following constraints:$$d_0 ge c_1,0$$$$d_0 ge c_2,0$$and$$d_j*kge c_1,j + c_2,k - 1quadforall jge 1,kge 1.$$

share|cite|improve this answer

answered yesterday

prubinprubin

1,505125

$endgroup$

share|cite|improve this answer

answered yesterday

prubinprubin

1,505125

answered yesterday

prubinprubin

1,505125

answered yesterday

prubinprubin

1,505125