How does one solve this kind of problem?

Maximize z = x1^2 + x2^2 + x3^2

x1.x2.x3 = 6

x1,x2,x3 all positive integers.

In the above, it looks like one can look and find that the answer is 1,1,6(probably) - but how does one solve more complicated problems of this nature?

asked 16 May '12, 22:00

Gen's gravatar image

Gen
171310
accept rate: 0%

edited 17 May '12, 02:49


One possibility is to use Constraint Programming: http://kti.ms.mff.cuni.cz/~bartak/constraints/

link

answered 16 May '12, 23:13

Tallys%20Yunes's gravatar image

Tallys Yunes ♦
2.1k518
accept rate: 11%

The following approach introduces binary variables as Paul suggested, but you can avoid factoring by taking the log of both sides of your product constraint. And both the objective and constraints are linear here.

proc optmodel;
    num n = 3;
    num p = 6;
    set VARS = 1..n;
    set VALUES = 1..p;
    var Assign {VARS, VALUES} binary;
    max Objective = sum {var in VARS, value in VALUES} value^2 * Assign[var,value];
    con Assign_var {var in VARS}:
        sum {value in VALUES} Assign[var,value] = 1;
    con Product:
        sum {var in VARS, value in VALUES} log(value) * Assign[var,value] = log(p);
    impvar Solution {var in VARS} = sum {value in VALUES} value * Assign[var,value];
    con Symmetry {var in VARS diff {n}}:
        Solution[var] >= Solution[var+1];
    solve;
    print solution;
quit;
link

answered 17 May '12, 20:55

Rob%20Pratt's gravatar image

Rob Pratt
1.2k26
accept rate: 28%

edited 17 May '12, 21:01

I don't know that I would recommend it in general, but you could formulate it as a 0-1 integer linear program by factoring the RHS value (I'm assuming just the one constraint) and using binary variables to decide in which original variable (x1, x2, ...) each factor lives. The objective ends up a quadratic function of the binary variables, which can be linearized by introducing more variables.

link

answered 17 May '12, 18:35

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
14.6k412
accept rate: 19%

Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Tags:

×28
×11
×7

Asked: 16 May '12, 22:00

Seen: 1,354 times

Last updated: 17 May '12, 21:01

OR-Exchange! Your site for questions, answers, and announcements about operations research.