Skip to content

Instantly share code, notes, and snippets.

@msakai
Created April 22, 2012 04:21
Show Gist options
  • Save msakai/2450935 to your computer and use it in GitHub Desktop.
Save msakai/2450935 to your computer and use it in GitHub Desktop.
Sample for solving MIP (mixed integer programming) problem with GLPK
#include <stdlib.h>
#include <stdio.h>
#include <glpk.h>
/*
Maximize
obj: x1 + 2 x2 + 3 x3 + x4
Subject To
c1: - x1 + x2 + x3 + 10 x4 <= 20
c2: x1 - 3 x2 + x3 <= 30
c3: x2 - 3.5 x4 = 0
Bounds
0 <= x1 <= 40
2 <= x4 <= 3
General
x4
End
*/
int main(void)
{
glp_prob *mip = glp_create_prob();
glp_set_prob_name(mip, "sample");
glp_set_obj_dir(mip, GLP_MAX);
glp_add_rows(mip, 3);
glp_set_row_name(mip, 1, "c1");
glp_set_row_bnds(mip, 1, GLP_DB, 0.0, 20.0);
glp_set_row_name(mip, 2, "c2");
glp_set_row_bnds(mip, 2, GLP_DB, 0.0, 30.0);
glp_set_row_name(mip, 3, "c3");
glp_set_row_bnds(mip, 3, GLP_FX, 0.0, 0);
glp_add_cols(mip, 4);
glp_set_col_name(mip, 1, "x1");
glp_set_col_bnds(mip, 1, GLP_DB, 0.0, 40.0);
glp_set_obj_coef(mip, 1, 1.0);
glp_set_col_name(mip, 2, "x2");
glp_set_col_bnds(mip, 2, GLP_LO, 0.0, 0.0);
glp_set_obj_coef(mip, 2, 2.0);
glp_set_col_name(mip, 3, "x3");
glp_set_col_bnds(mip, 3, GLP_LO, 0.0, 0.0);
glp_set_obj_coef(mip, 3, 3.0);
glp_set_col_name(mip, 4, "x4");
glp_set_col_bnds(mip, 4, GLP_DB, 2.0, 3.0);
glp_set_obj_coef(mip, 4, 1.0);
glp_set_col_kind(mip, 4, GLP_IV);
int ia[1+9], ja[1+9];
double ar[1+9];
ia[1]=1,ja[1]=1,ar[1]=-1; // a[1,1] = -1
ia[2]=1,ja[2]=2,ar[2]=1; // a[1,2] = 1
ia[3]=1,ja[3]=3,ar[3]=1; // a[1,3] = 1
ia[4]=1,ja[4]=4,ar[4]=10; // a[1,4] = 10
ia[5]=2,ja[5]=1,ar[5]=1; // a[2,1] = 1
ia[6]=2,ja[6]=2,ar[6]=-3; // a[2,2] = -3
ia[7]=2,ja[7]=3,ar[7]=1; // a[2,3] = 1
ia[8]=3,ja[8]=2,ar[8]=1; // a[3,2] = 1
ia[9]=3,ja[9]=4,ar[9]=-3.5; // a[3,4] = -3.5
glp_load_matrix(mip, 9, ia, ja, ar);
glp_iocp parm;
glp_init_iocp(&parm);
parm.presolve = GLP_ON;
int err = glp_intopt(mip, &parm);
double z = glp_mip_obj_val(mip);
double x1 = glp_mip_col_val(mip, 1);
double x2 = glp_mip_col_val(mip, 2);
double x3 = glp_mip_col_val(mip, 3);
double x4 = glp_mip_col_val(mip, 4);
printf("\nz = %g; x1 = %g; x2 = %g; x3 = %g, x4 = %g\n", z, x1, x2, x3, x4);
// z = 122.5; x1 = 40; x2 = 10.5; x3 = 19.5, x4 = 3
glp_delete_prob(mip);
return 0;
}
@lukpank
Copy link

lukpank commented Feb 19, 2015

It seems that the code does not fully match the formulation of the
problem given in the comment. Could you comment on the following
issues:

  1. You declare "c1" and "c2" as GLP_DB (double bounded) so you
    actually have

    c1: 0 <= - x1 + x2 + x3 + 10 x4 <= 20
    c2: 0 <= x1 - 3 x2 + x3 <= 30 
    

    But changing "c1" and "c2" to GLP_UP (upper bounded) does not
    change the result in this example.

  2. For some reason you assume that "x2" and "x3" are non negative,
    thus you do not list "x2 >= 0" and "x3 >= 0" as variable bounds.

  3. Could you explain what you mean by

    General
     x4
    

    I would understand that "x1", "x2", and "x3" are general (i.e.,
    continuous variables) while "x4" is not general (as it is an
    integer variable).

@louisaugusto
Copy link

This code doesn't work. This line:
mip = glp_create_prob();
is necessary.

@msakai
Copy link
Author

msakai commented May 1, 2015

Hi @lukpank,

  1. You declare "c1" and "c2" as GLP_DB (double bounded) so you actually have
    c1: 0 <= - x1 + x2 + x3 + 10 x4 <= 20 c2: 0 <= x1 - 3 x2 + x3 <= 30
    But changing "c1" and "c2" to GLP_UP (upper bounded) does not change the result in this example.

I cannot remember why I used GLP_DB instead of GLP_UP.
But I think it was just my mistake.

  1. For some reason you assume that "x2" and "x3" are non negative, thus you do not list "x2 >= 0" and "x3 >= 0" as variable bounds.

I used CPLEX LP file format to write down the formulation.
In CPLEX LP file, variables are non-negative by default.

  1. Could you explain what you mean by
    General x4
    I would understand that "x1", "x2", and "x3" are general (i.e., continuous variables) while "x4" is not general (as it is an integer variable).

In CPLEX LP file, "General" means general integer variables.
So "x1", "x2" and "x3" are integer variables while "x4" is a continuous variable.

@msakai
Copy link
Author

msakai commented May 6, 2015

Hi @louisaugusto.
Hmm, which version of compiler and GLPK did you used?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment