Sum of Max terms maximization
How to create a 2D table with varying step?
What is the right way to query an I2C device from an interrupt service routine?
Auto replacement of characters
How frequently do Russian people still refer to others by their patronymic (отчество)?
What is a "tittering order"?
Go function to test whether a file exists
What is the difference between a historical drama and a period drama?
What do you call the angle of the direction of an airplane?
In National Velvet why didn't they use a stunt double for Elizabeth Taylor?
My players like to search everything. What do they find?
Why did moving the mouse cursor cause Windows 95 to run more quickly?
How might boat designs change in order to allow them to be pulled by dragons?
How to travel between two stationary worlds in the least amount of time? (time dilation)
Olive oil in Japanese cooking
What does "another" mean in this case?
Upload csv into QGIS
Should I hide my travel history to the UK when I apply for an Australian visa?
How is /a/ pronounced before n/m in French?
Can you use a reaction to affect initiative rolls?
Pandas merge and fillna
Isn't "Dave's protocol" good if only the database, and not the code, is leaked?
Has there ever been a cold war other than between the U.S. and the U.S.S.R.?
Phrasing "it says" or "it reads"
If a creature is blocking and it has vigilance does it still tap?
Sum of Max terms maximization
$begingroup$
Maximizing sum-of-max terms is an NP-hard problem. The objective function is a convex function and maximizing a convex function is a hard problem. Also, this is a non-differentiable function.
CPLEX and GUROBI solve these problems to global optimality. I don't know what method they use. I guess they first eliminate the obviously bad terms in the beginning and then follow a branching tree to optimize each combination. Is this correct? What methods do they use, how can I (roughly) learn about this?
I am interested in linear constraints. For example:
beginalign
beginarrayll
max & leftmax3x_1 + 4x_2 , -2x_1 +7x_2 + max-x_1 + 6x_2 , 5x_1 +3x_2 right \
textst & a leq x_1 + x_2 leq b \
& x_1 geq c, x_2 geq d
endarray
endalign
I am solving a way bigger case.
solver nonlinear-programming
asked 8 hours ago
independentvariableindependentvariable
6021 silver badge13 bronze badges
$endgroup$
add a comment |
$begingroup$
Maximizing sum-of-max terms is an NP-hard problem. The objective function is a convex function and maximizing a convex function is a hard problem. Also, this is a non-differentiable function.
CPLEX and GUROBI solve these problems to global optimality. I don't know what method they use. I guess they first eliminate the obviously bad terms in the beginning and then follow a branching tree to optimize each combination. Is this correct? What methods do they use, how can I (roughly) learn about this?
I am interested in linear constraints. For example:
beginalign
beginarrayll
max & leftmax3x_1 + 4x_2 , -2x_1 +7x_2 + max-x_1 + 6x_2 , 5x_1 +3x_2 right \
textst & a leq x_1 + x_2 leq b \
& x_1 geq c, x_2 geq d
endarray
endalign
I am solving a way bigger case.
solver nonlinear-programming
asked 8 hours ago
independentvariableindependentvariable
6021 silver badge13 bronze badges
$endgroup$
$begingroup$
could you please add a reference to the hardness result, please?
$endgroup$
– Marco Lübbecke
6 hours ago
$begingroup$
Maximizing a convex quadratic form over $Vert x Vert_infty leq 1$ is equivalent to binary quadratic optimization, which is NP-hard (so the problem is "hard" without needing a sum). The asker may have been referring to this.
$endgroup$
– Ryan Cory-Wright
6 hours ago
add a comment |
$begingroup$
Maximizing sum-of-max terms is an NP-hard problem. The objective function is a convex function and maximizing a convex function is a hard problem. Also, this is a non-differentiable function.
CPLEX and GUROBI solve these problems to global optimality. I don't know what method they use. I guess they first eliminate the obviously bad terms in the beginning and then follow a branching tree to optimize each combination. Is this correct? What methods do they use, how can I (roughly) learn about this?
I am interested in linear constraints. For example:
beginalign
beginarrayll
max & leftmax3x_1 + 4x_2 , -2x_1 +7x_2 + max-x_1 + 6x_2 , 5x_1 +3x_2 right \
textst & a leq x_1 + x_2 leq b \
& x_1 geq c, x_2 geq d
endarray
endalign
I am solving a way bigger case.
solver nonlinear-programming
asked 8 hours ago
independentvariableindependentvariable
6021 silver badge13 bronze badges
$endgroup$
Maximizing sum-of-max terms is an NP-hard problem. The objective function is a convex function and maximizing a convex function is a hard problem. Also, this is a non-differentiable function.
CPLEX and GUROBI solve these problems to global optimality. I don't know what method they use. I guess they first eliminate the obviously bad terms in the beginning and then follow a branching tree to optimize each combination. Is this correct? What methods do they use, how can I (roughly) learn about this?
I am interested in linear constraints. For example:
beginalign
beginarrayll
max & leftmax3x_1 + 4x_2 , -2x_1 +7x_2 + max-x_1 + 6x_2 , 5x_1 +3x_2 right \
textst & a leq x_1 + x_2 leq b \
& x_1 geq c, x_2 geq d
endarray
endalign
I am solving a way bigger case.
solver nonlinear-programming
solver nonlinear-programming
asked 8 hours ago
independentvariableindependentvariable
6021 silver badge13 bronze badges
asked 8 hours ago
independentvariableindependentvariable
6021 silver badge13 bronze badges
asked 8 hours ago
independentvariableindependentvariable
6021 silver badge13 bronze badges
asked 8 hours ago
independentvariableindependentvariable
6021 silver badge13 bronze badges
asked 8 hours ago
independentvariableindependentvariable
6021 silver badge13 bronze badges
6021 silver badge13 bronze badges
$begingroup$
could you please add a reference to the hardness result, please?
$endgroup$
– Marco Lübbecke
6 hours ago
$begingroup$
Maximizing a convex quadratic form over $Vert x Vert_infty leq 1$ is equivalent to binary quadratic optimization, which is NP-hard (so the problem is "hard" without needing a sum). The asker may have been referring to this.
$endgroup$
– Ryan Cory-Wright
6 hours ago
add a comment |
$begingroup$
could you please add a reference to the hardness result, please?
$endgroup$
– Marco Lübbecke
6 hours ago
$begingroup$
Maximizing a convex quadratic form over $Vert x Vert_infty leq 1$ is equivalent to binary quadratic optimization, which is NP-hard (so the problem is "hard" without needing a sum). The asker may have been referring to this.
$endgroup$
– Ryan Cory-Wright
6 hours ago
$begingroup$
could you please add a reference to the hardness result, please?
$endgroup$
– Marco Lübbecke
6 hours ago
$begingroup$
could you please add a reference to the hardness result, please?
$endgroup$
– Marco Lübbecke
6 hours ago
$begingroup$
Maximizing a convex quadratic form over $Vert x Vert_infty leq 1$ is equivalent to binary quadratic optimization, which is NP-hard (so the problem is "hard" without needing a sum). The asker may have been referring to this.
$endgroup$
– Ryan Cory-Wright
6 hours ago
$begingroup$
Maximizing a convex quadratic form over $Vert x Vert_infty leq 1$ is equivalent to binary quadratic optimization, which is NP-hard (so the problem is "hard" without needing a sum). The asker may have been referring to this.
$endgroup$
– Ryan Cory-Wright
6 hours ago
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
If your problem is reasonably small then one relatively simple approach is to reformulate the objective as a MIP, under a big-M assumption.
Suppose that our objective is to maximize $$sum_i g_i(x),$$ where each $g_i(x):=max_j a_j^itop x+b^i_j$ is the maximum of some affine functions. We can model this by introducing auxilliary variables $theta_i$ such that $theta_i leq g_i(x)$, letting $z_i,j=1$ if the $j$th affine function in $g_i(x)$ is the largest at $x$, and maximizing the following problem:
beginalign*
max quad & sum_i theta_i\
texts.t. quad & theta_i leq a_j^itopx+b_j^i+M(1-z_i,j), forall i, forall j,\
& sum_j z_i,j=1, forall i,\
& z_i,j in 0, 1 , forall i, forall j.
endalign*
The combination of the big-M constraints and "objective pressure" ensures that $theta_i=g_i(x)$ at optimality.
If the problem is larger, the above big-M approach won't give tight enough relaxations for branch-and-bound to perform well and we will need to think about using more complicated formulations. In this case, you should think about exploiting the structure of the problem, i.e., explicitly treating the problem as maximizing the sum of piecewise linear functions.
Tighter formulations than the generic big-M approach have been developed here.
I have no idea whether or not this approach is what CPLEX/Gurobi use.
answered 7 hours ago
Ryan Cory-WrightRyan Cory-Wright
7003 silver badges15 bronze badges
$endgroup$
add a comment |
Your Answer
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "700"
;
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: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
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
);
);
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
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2for.stackexchange.com%2fquestions%2f860%2fsum-of-max-terms-maximization%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
If your problem is reasonably small then one relatively simple approach is to reformulate the objective as a MIP, under a big-M assumption.
Suppose that our objective is to maximize $$sum_i g_i(x),$$ where each $g_i(x):=max_j a_j^itop x+b^i_j$ is the maximum of some affine functions. We can model this by introducing auxilliary variables $theta_i$ such that $theta_i leq g_i(x)$, letting $z_i,j=1$ if the $j$th affine function in $g_i(x)$ is the largest at $x$, and maximizing the following problem:
beginalign*
max quad & sum_i theta_i\
texts.t. quad & theta_i leq a_j^itopx+b_j^i+M(1-z_i,j), forall i, forall j,\
& sum_j z_i,j=1, forall i,\
& z_i,j in 0, 1 , forall i, forall j.
endalign*
The combination of the big-M constraints and "objective pressure" ensures that $theta_i=g_i(x)$ at optimality.
If the problem is larger, the above big-M approach won't give tight enough relaxations for branch-and-bound to perform well and we will need to think about using more complicated formulations. In this case, you should think about exploiting the structure of the problem, i.e., explicitly treating the problem as maximizing the sum of piecewise linear functions.
Tighter formulations than the generic big-M approach have been developed here.
I have no idea whether or not this approach is what CPLEX/Gurobi use.
answered 7 hours ago
Ryan Cory-WrightRyan Cory-Wright
7003 silver badges15 bronze badges
$endgroup$
add a comment |
$begingroup$
If your problem is reasonably small then one relatively simple approach is to reformulate the objective as a MIP, under a big-M assumption.
Suppose that our objective is to maximize $$sum_i g_i(x),$$ where each $g_i(x):=max_j a_j^itop x+b^i_j$ is the maximum of some affine functions. We can model this by introducing auxilliary variables $theta_i$ such that $theta_i leq g_i(x)$, letting $z_i,j=1$ if the $j$th affine function in $g_i(x)$ is the largest at $x$, and maximizing the following problem:
beginalign*
max quad & sum_i theta_i\
texts.t. quad & theta_i leq a_j^itopx+b_j^i+M(1-z_i,j), forall i, forall j,\
& sum_j z_i,j=1, forall i,\
& z_i,j in 0, 1 , forall i, forall j.
endalign*
The combination of the big-M constraints and "objective pressure" ensures that $theta_i=g_i(x)$ at optimality.
If the problem is larger, the above big-M approach won't give tight enough relaxations for branch-and-bound to perform well and we will need to think about using more complicated formulations. In this case, you should think about exploiting the structure of the problem, i.e., explicitly treating the problem as maximizing the sum of piecewise linear functions.
Tighter formulations than the generic big-M approach have been developed here.
I have no idea whether or not this approach is what CPLEX/Gurobi use.
answered 7 hours ago
Ryan Cory-WrightRyan Cory-Wright
7003 silver badges15 bronze badges
$endgroup$
add a comment |
$begingroup$
If your problem is reasonably small then one relatively simple approach is to reformulate the objective as a MIP, under a big-M assumption.
Suppose that our objective is to maximize $$sum_i g_i(x),$$ where each $g_i(x):=max_j a_j^itop x+b^i_j$ is the maximum of some affine functions. We can model this by introducing auxilliary variables $theta_i$ such that $theta_i leq g_i(x)$, letting $z_i,j=1$ if the $j$th affine function in $g_i(x)$ is the largest at $x$, and maximizing the following problem:
beginalign*
max quad & sum_i theta_i\
texts.t. quad & theta_i leq a_j^itopx+b_j^i+M(1-z_i,j), forall i, forall j,\
& sum_j z_i,j=1, forall i,\
& z_i,j in 0, 1 , forall i, forall j.
endalign*
The combination of the big-M constraints and "objective pressure" ensures that $theta_i=g_i(x)$ at optimality.
If the problem is larger, the above big-M approach won't give tight enough relaxations for branch-and-bound to perform well and we will need to think about using more complicated formulations. In this case, you should think about exploiting the structure of the problem, i.e., explicitly treating the problem as maximizing the sum of piecewise linear functions.
Tighter formulations than the generic big-M approach have been developed here.
I have no idea whether or not this approach is what CPLEX/Gurobi use.
answered 7 hours ago
Ryan Cory-WrightRyan Cory-Wright
7003 silver badges15 bronze badges
$endgroup$
If your problem is reasonably small then one relatively simple approach is to reformulate the objective as a MIP, under a big-M assumption.
Suppose that our objective is to maximize $$sum_i g_i(x),$$ where each $g_i(x):=max_j a_j^itop x+b^i_j$ is the maximum of some affine functions. We can model this by introducing auxilliary variables $theta_i$ such that $theta_i leq g_i(x)$, letting $z_i,j=1$ if the $j$th affine function in $g_i(x)$ is the largest at $x$, and maximizing the following problem:
beginalign*
max quad & sum_i theta_i\
texts.t. quad & theta_i leq a_j^itopx+b_j^i+M(1-z_i,j), forall i, forall j,\
& sum_j z_i,j=1, forall i,\
& z_i,j in 0, 1 , forall i, forall j.
endalign*
The combination of the big-M constraints and "objective pressure" ensures that $theta_i=g_i(x)$ at optimality.
If the problem is larger, the above big-M approach won't give tight enough relaxations for branch-and-bound to perform well and we will need to think about using more complicated formulations. In this case, you should think about exploiting the structure of the problem, i.e., explicitly treating the problem as maximizing the sum of piecewise linear functions.
Tighter formulations than the generic big-M approach have been developed here.
I have no idea whether or not this approach is what CPLEX/Gurobi use.
answered 7 hours ago
Ryan Cory-WrightRyan Cory-Wright
7003 silver badges15 bronze badges
answered 7 hours ago
Ryan Cory-WrightRyan Cory-Wright
7003 silver badges15 bronze badges
answered 7 hours ago
Ryan Cory-WrightRyan Cory-Wright
7003 silver badges15 bronze badges
answered 7 hours ago
Ryan Cory-WrightRyan Cory-Wright
7003 silver badges15 bronze badges
7003 silver badges15 bronze badges
add a comment |
add a comment |
Thanks for contributing an answer to Operations Research Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
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
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2for.stackexchange.com%2fquestions%2f860%2fsum-of-max-terms-maximization%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
could you please add a reference to the hardness result, please?
$endgroup$
– Marco Lübbecke
6 hours ago
$begingroup$
Maximizing a convex quadratic form over $Vert x Vert_infty leq 1$ is equivalent to binary quadratic optimization, which is NP-hard (so the problem is "hard" without needing a sum). The asker may have been referring to this.
$endgroup$
– Ryan Cory-Wright
6 hours ago