[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [Help-glpk] "Integer" linear programming with non-uniform quantizati

From: Xypron
Subject: Re: [Help-glpk] "Integer" linear programming with non-uniform quantization
Date: Fri, 28 Jan 2011 20:19:43 +0100
User-agent: Mozilla/5.0 (X11; U; Linux i686; en-US; rv: Gecko/20101123 SeaMonkey/2.0.11

Hello Oscar,

if your problem is sufficiently small you can simply assign a binary to each value your variables can take. See example below.

If you want to write your own branch and bound heuristic on top of GLPK, have a look at glpk-4.45/glpios09.c

Best regards


set X;
set Y;

var x;
var y;

var wx{i in X}, binary;
var wy{j in Y}, binary;

maximize obj : x + y;

s.t. c1 : x + .5 * y <=4;
s.t. c2 : .3 * x + y <= 3.8;

s.t. x1 : x = sum{i in X} i * wx[i];
s.t. x2 : 1 = sum{i in X} wx[i];
s.t. y1 : y = sum{j in Y} j * wy[j];
s.t. y2 : 1 = sum{j in Y} wy[j];


display x,y;


set X := 1 1.6 2.3 3.5 5;
set Y := .8 1.3 1.7 2.1 2.7 4.1;


Oscar Gustafsson wrote:
This may be slightly off-topic as it partly is a general optimization question. Sorry about that. However, GLPK is mentioned later on.

I have a linear programming formulation to which I want to find optimized variables that can take on only certain values (not always integers). As far as I can tell, it should be possible to use branch-and-bound for this problem as well. Can anyone confirm this and is there a term for this?

As I want to solve the problem, I clearly need to define my own branch-and-bound algorithm, both in terms of bounds and branching strategies. Would GLPK be a suitable alternative for this or are there packages where the bounding and branching is easier to extract? I get the impression that SYMPHONY is more or less built for this (playing around with different strategies). SCIP?

With best regards

Oscar Gustafsson

Help-glpk mailing list

reply via email to

[Prev in Thread] Current Thread [Next in Thread]