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

accept rate: 0%

edited 17 May '12, 02:49

One possibility is to use Constraint Programming:


answered 16 May '12, 23:13

Tallys%20Yunes's gravatar image

Tallys Yunes ♦
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];
    print solution;

answered 17 May '12, 20:55

Rob%20Pratt's gravatar image

Rob Pratt
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.


answered 17 May '12, 18:35

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
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



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "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



Asked: 16 May '12, 22:00

Seen: 1,602 times

Last updated: 17 May '12, 21:01

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