source: trunk/Cbc/test/CInterfaceTest.c @ 2591

Last change on this file since 2591 was 2591, checked in by unxusr, 4 months ago

C89 compatibility fix

File size: 13.1 KB
Line 
1/* $Id$ */
2/* Copyright (C) 2014, International Business Machines
3   Corporation and others.  All Rights Reserved.
4   This code is licensed under the terms of the Eclipse Public License (EPL). */
5
6#undef NDEBUG /* force asserts to work */
7#include "Cbc_C_Interface.h"
8#include <assert.h>
9#include <math.h>
10#include <stdio.h>
11#include <stdlib.h>
12#include <string.h>
13
14#ifndef INFINITY /* workaround for non-C99 compilers */
15#define INFINITY (HUGE_VAL * 2)
16#endif
17
18
19static int callback_called = 0;
20
21void (COINLINKAGE_CB test_callback)(Cbc_Model * model,int  msgno, int ndouble,
22                            const double * dvec, int nint, const int * ivec,
23                            int nchar, char ** cvec) {
24
25    callback_called = 1;
26    printf("In callback: message %d\n", msgno);
27
28}
29
30
31void testKnapsack() {
32
33    Cbc_Model *model = Cbc_newModel();
34
35    /* Simple knapsack problem
36       Maximize  5x[1] + 3x[2] + 2x[3] + 7x[4] + 4x[5]
37       s.t.      2x[1] + 8x[2] + 4x[3] + 2x[4] + 5x[5] <= 10
38       All x binary
39       */
40   
41    CoinBigIndex start[] = {0, 1, 2, 3, 4, 5, 6};
42    int rowindex[] = {0, 0, 0, 0, 0};
43    double value[] = {2, 8, 4, 2, 5};
44    double collb[] = {0,0,0,0,0};
45    double colub[] = {1,1,1,1,1};
46    double obj[] = {5, 3, 2, 7, 4};
47    double feasible[] = {1,1,0,0,0};
48    double rowlb[] = {-INFINITY};
49    double rowub[] = {10};
50    const double *sol;
51    const char* setname = "test model";
52    char *getname = malloc(20);
53    int i;
54
55    printf("Interface reports Cbc version %s\n", Cbc_getVersion());
56
57    Cbc_loadProblem(model, 5, 1, start, rowindex, value, collb, colub, obj, rowlb, rowub);
58
59    Cbc_setColName(model, 2, "var2");
60    Cbc_setRowName(model, 0, "constr0");
61
62
63    assert(Cbc_getNumCols(model) == 5);
64    assert(Cbc_getNumRows(model) == 1);
65
66    for (i = 0; i < 5; i++) {
67        Cbc_setInteger(model, i);
68        assert(Cbc_isInteger(model,i));
69    }
70
71    Cbc_setObjSense(model, -1);
72    assert(Cbc_getObjSense(model) == -1);
73
74    Cbc_setProblemName(model, setname);
75
76    Cbc_registerCallBack(model, test_callback);
77
78    Cbc_setInitialSolution(model, feasible);
79
80    Cbc_solve(model);
81
82    assert(Cbc_isProvenOptimal(model));
83    assert(!Cbc_isAbandoned(model));
84    assert(!Cbc_isProvenInfeasible(model));
85    assert(!Cbc_isContinuousUnbounded(model));
86    assert(!Cbc_isNodeLimitReached(model));
87    assert(!Cbc_isSecondsLimitReached(model));
88    assert(!Cbc_isSolutionLimitReached(model));
89    assert(fabs( Cbc_getObjValue(model)- (16.0) < 1e-6));
90    assert(fabs( Cbc_getBestPossibleObjValue(model)- (16.0) < 1e-6));
91
92    assert(callback_called == 1);
93   
94    sol = Cbc_getColSolution(model);
95   
96    assert(fabs(sol[0] - 1.0) < 1e-6);
97    assert(fabs(sol[1] - 0.0) < 1e-6);
98    assert(fabs(sol[2] - 0.0) < 1e-6);
99    assert(fabs(sol[3] - 1.0) < 1e-6);
100    assert(fabs(sol[4] - 1.0) < 1e-6);
101
102    Cbc_problemName(model, 20, getname);
103    i = strcmp(getname,setname);
104    assert( (i == 0) );
105
106    Cbc_getColName(model, 2, getname, 20);
107    i = strcmp(getname, "var2");
108    assert( (i == 0) );
109    Cbc_getRowName(model, 0, getname, 20);
110    i = strcmp(getname, "constr0");
111    assert( (i == 0) );
112    assert( Cbc_maxNameLength(model) >= 7 );
113   
114    Cbc_deleteModel(model);
115    free(getname);
116
117}
118
119/*
120void testProblemModification() {
121
122    Cbc_Model *model = Cbc_newModel();
123
124    / * Simple knapsack problem
125       Maximize  5x[1] + 3x[2] + 2x[3] + 7x[4] + 4x[5]
126       s.t.      2x[1] + 8x[2] + 4x[3] + 2x[4] + 5x[5] <= 10
127       All x binary
128       * /
129   
130    CoinBigIndex start[] = {0, 1, 2, 3, 4, 5, 6};
131    int rowindex[] = {0, 0, 0, 0, 0};
132    double value[] = {2, 8, 4, 2, 5};
133    double collb[] = {0,0,0,0,0};
134    double colub[] = {1,1,1,1,1};
135    double obj[] = {5, 3, 2, 7, 4};
136    double rowlb[] = {-INFINITY};
137    double rowub[] = {10};
138    const double *sol;
139    int i;
140
141    printf("Interface reports Cbc version %s\n", Cbc_getVersion());
142
143    Cbc_loadProblem(model, 5, 1, start, rowindex, value, collb, colub, obj, rowlb, rowub);
144
145    for (i = 0; i < 5; i++) {
146        Cbc_setInteger(model, i);
147        assert(Cbc_isInteger(model,i));
148    }
149
150    Cbc_setObjSense(model, -1);
151    assert(Cbc_getObjSense(model) == -1);
152
153    Cbc_solve(model);
154
155    assert(Cbc_isProvenOptimal(model));
156    assert(fabs( Cbc_getObjValue(model)- (16.0) < 1e-6));
157
158    sol = Cbc_getColSolution(model);
159   
160    assert(fabs(sol[0] - 1.0) < 1e-6);
161    assert(fabs(sol[1] - 0.0) < 1e-6);
162    assert(fabs(sol[2] - 0.0) < 1e-6);
163    assert(fabs(sol[3] - 1.0) < 1e-6);
164    assert(fabs(sol[4] - 1.0) < 1e-6);
165
166    Cbc_setColUpper(model, 0, 0.0);
167    Cbc_solve(model);
168
169    assert(Cbc_isProvenOptimal(model));
170    assert(fabs( Cbc_getObjValue(model)- (11.0) < 1e-6));
171
172    sol = Cbc_getColSolution(model);
173   
174    assert(fabs(sol[0] - 0.0) < 1e-6);
175    assert(fabs(sol[1] - 0.0) < 1e-6);
176    assert(fabs(sol[2] - 0.0) < 1e-6);
177    assert(fabs(sol[3] - 1.0) < 1e-6);
178    assert(fabs(sol[4] - 1.0) < 1e-6);
179
180
181    Cbc_setColLower(model, 1, 1.0);
182
183    assert(Cbc_isProvenOptimal(model));
184    assert(fabs( Cbc_getObjValue(model)- (10.0) < 1e-6));
185
186    sol = Cbc_getColSolution(model);
187   
188    assert(fabs(sol[0] - 0.0) < 1e-6);
189    assert(fabs(sol[1] - 1.0) < 1e-6);
190    assert(fabs(sol[2] - 0.0) < 1e-6);
191    assert(fabs(sol[3] - 1.0) < 1e-6);
192    assert(fabs(sol[4] - 0.0) < 1e-6);
193
194   
195    Cbc_deleteModel(model);
196
197}
198*/
199
200
201void testSOS() {
202
203    Cbc_Model *model = Cbc_newModel();
204
205    /*
206       Maximize  5x[1] + 3x[2] + 2x[3] + 7x[4] + 4x[5]
207       s.t.       x[1] +  x[2] +  x[3] +  x[4] +  x[5] == 1
208       All x binary
209       */
210   
211    CoinBigIndex start[] = {0, 0, 0, 0, 0, 0, 0};
212    double collb[] = {0,0,0,0,0};
213    double colub[] = {1,1,1,1,1};
214    double obj[] = {5, 3, 2, 7, 4};
215    int sosrowstart[] = {0,5};
216    int soscolindex[] = {0,1,2,3,4}; 
217    const double *sol;
218    int i;
219
220    Cbc_loadProblem(model, 5, 0, start, NULL, NULL, collb, colub, obj, NULL, NULL);
221
222    assert(Cbc_getNumCols(model) == 5);
223    assert(Cbc_getNumRows(model) == 0);
224
225    for (i = 0; i < 5; i++) {
226        Cbc_setInteger(model, i);
227        assert(Cbc_isInteger(model,i));
228    }
229
230    Cbc_setObjSense(model, -1);
231    assert(Cbc_getObjSense(model) == -1);
232   
233    Cbc_addSOS(model,1,sosrowstart,soscolindex,obj,1); 
234
235    Cbc_solve(model);
236
237    assert(Cbc_isProvenOptimal(model));
238    assert(!Cbc_isAbandoned(model));
239    assert(!Cbc_isProvenInfeasible(model));
240    assert(!Cbc_isContinuousUnbounded(model));
241    assert(!Cbc_isNodeLimitReached(model));
242    assert(!Cbc_isSecondsLimitReached(model));
243    assert(!Cbc_isSolutionLimitReached(model));
244    assert(fabs( Cbc_getObjValue(model)- (7.0) < 1e-6));
245    assert(fabs( Cbc_getBestPossibleObjValue(model)- (7.0) < 1e-6));
246
247    sol = Cbc_getColSolution(model);
248   
249    assert(fabs(sol[0] - 0.0) < 1e-6);
250    assert(fabs(sol[1] - 0.0) < 1e-6);
251    assert(fabs(sol[2] - 0.0) < 1e-6);
252    assert(fabs(sol[3] - 1.0) < 1e-6);
253    assert(fabs(sol[4] - 0.0) < 1e-6);
254
255    Cbc_deleteModel(model);
256
257}
258
259
260void testIntegerInfeasible() {
261
262    Cbc_Model *model = Cbc_newModel();
263
264    /* Minimize x
265     * s.t.     x <= -10
266     * x binary */
267
268    CoinBigIndex start[] = {0, 1};
269    int rowindex[] = {0};
270    double value[] = {1.0};
271    double rowlb[] = {-INFINITY};
272    double rowub[] = {-10};
273
274    double collb[] = {0.0};
275    double colub[] = {1.0};
276    double obj[] = {1.0};
277
278    Cbc_loadProblem(model, 1, 1, start, rowindex, value, collb, colub, obj, rowlb, rowub);
279
280    Cbc_setInteger(model, 0);
281
282    assert(Cbc_getNumCols(model) == 1);
283    assert(Cbc_getNumRows(model) == 1);
284
285    Cbc_solve(model);
286   
287    assert(!Cbc_isProvenOptimal(model));
288    assert(Cbc_isProvenInfeasible(model));
289   
290    Cbc_deleteModel(model);
291
292}
293
294void testIntegerUnbounded() {
295
296    Cbc_Model *model = Cbc_newModel();
297
298    /* http://list.coin-or.org/pipermail/cbc/2014-March/001276.html
299     * Minimize x
300     * s.t. x + y <= 3
301     *      x - y == 0
302     *      x,y Free
303     *      x integer */
304
305    CoinBigIndex start[] = {0,2,4};
306    int rowindex[] = {0, 1, 0, 1};
307    double value[] = {1, 1, 1, -1};
308    double rowlb[] = {-INFINITY, 0.0};
309    double rowub[] = {3.0,0.0};
310    double collb[] = {-INFINITY, -INFINITY};
311    double colub[] = {INFINITY, INFINITY};
312    double obj[] = {1.0,0.0};
313
314    Cbc_loadProblem(model, 2, 2, start, rowindex, value, collb, colub, obj, rowlb, rowub);
315
316    Cbc_setInteger(model, 0);
317
318    Cbc_setParameter(model, "log", "0");
319   
320    printf("About to solve problem silently. You should see no output except \"Done\".\n");
321    Cbc_solve(model);
322    printf("Done\n");
323   
324    assert(!Cbc_isProvenOptimal(model));
325    assert(!Cbc_isProvenInfeasible(model));
326    assert(Cbc_isContinuousUnbounded(model));
327
328    Cbc_deleteModel(model);
329
330
331}
332
333void testIntegerBounds() {
334    /* max 1.1x + 100.0z
335       st     x +      z <= 3
336         0 <= x <= 3
337         0 <= z <= 1.5, Integer
338     x* = 2, z* = 1 */
339   
340    Cbc_Model *model = Cbc_newModel();
341
342    CoinBigIndex start[] = {0,1,2};
343    int rowindex[] = {0, 0};
344    double value[] = {1, 1};
345    double rowlb[] = {-INFINITY};
346    double rowub[] = {3.0};
347    double collb[] = {0.0, 0.0};
348    double colub[] = {3.0, 1.5};
349    double obj[] = {1.1,100.0};
350    const double *sol;
351
352    Cbc_loadProblem(model, 2, 1, start, rowindex, value, collb, colub, obj, rowlb, rowub);
353
354    Cbc_setInteger(model, 1);
355    Cbc_setObjSense(model, -1);
356
357    Cbc_solve(model);
358   
359    assert(Cbc_isProvenOptimal(model));
360
361    sol = Cbc_getColSolution(model);
362   
363    assert(fabs(sol[0] - 2.0) < 1e-6);
364    assert(fabs(sol[1] - 1.0) < 1e-6);
365
366    Cbc_deleteModel(model);
367
368}
369
370void testQueens(int n) {
371    int **x = malloc( sizeof(int*)*n );
372    int i, j, k, p;
373    x[0] = malloc( sizeof(int)*n*n );
374    for ( i=1 ; (i<n) ; ++i )
375        x[i] = x[i-1] + n;
376
377    Cbc_Model *model = Cbc_newModel();
378   
379    /* adding variables */
380    k = 0;
381    for ( i=0 ; (i<n) ; ++i )
382    {
383        for ( j=0 ; (j<n) ; ++j )
384        {
385            x[i][j] = k++;
386            char name[256];
387            sprintf(name, "x(%d,%d)", i, j);
388            Cbc_addCol(model, name, 0.0, 1.0, 0.0, 1, 0, NULL, NULL);
389        }
390    }
391
392    int *idx = malloc(sizeof(int)*n);
393    double *coef = malloc(sizeof(double)*n);
394
395    /* constraint one per row */
396    for ( i=0 ; (i<n) ; ++i )
397    {
398        for ( j=0 ; j<n ; ++j )
399        {
400            idx[j] = x[i][j];
401            coef[j] = 1.0;
402        }
403        char name[256];
404        sprintf(name, "row(%d)", i);
405        Cbc_addRow(model, name, n, idx, coef, 'E', 1.0);
406    }
407
408    /* constraint one per column */
409    for ( j=0 ; (j<n) ; ++j )
410    {
411        for ( i=0 ; i<n ; ++i )
412        {
413            idx[i] = x[i][j];
414            coef[i] = 1.0;
415        }
416        char name[256];
417        sprintf(name, "col(%d)", j);
418        Cbc_addRow(model, name, n, idx, coef, 'E', 1.0);
419    }
420
421    /* diagonal  */
422    p = 0;
423    for ( k=2-n ; k<(n-1) ; ++k, ++p )
424    {
425        int nz = 0;
426        for ( i=0 ; (i<n) ; ++i )
427        {
428            for ( j=0 ; (j<n) ; ++j )
429            {
430                if (i-j==k)
431                {
432                    idx[nz] = x[i][j];
433                    coef[nz] = 1.0;
434                    ++nz;
435                }
436            }
437        }
438        char name[256];
439        sprintf(name, "diag1(%d)", k);
440        Cbc_addRow(model, name, nz, idx, coef, 'L', 1.0);
441    }
442
443    /* diagonal */
444    p = 0;
445    for ( k=3 ; k<(n+n) ; ++k, ++p )
446    {
447        int nz = 0;
448        for ( i=0 ; (i<n) ; ++i )
449        {
450            for ( j=0 ; (j<n) ; ++j )
451            {
452                if (i+j==k)
453                {
454                    idx[nz] = x[i][j];
455                    coef[nz] = 1.0;
456                    ++nz;
457                }
458            }
459        }
460        char name[256];
461        sprintf(name, "diag2(%d)", k);
462        Cbc_addRow(model, name, nz, idx, coef, 'L', 1.0);
463    } 
464
465    Cbc_setMaximumSeconds(model, 60);
466    int status = Cbc_solve(model);
467    const double *xs = Cbc_getColSolution(model);
468    if (n<=75)
469    {
470        /* should find the optimal for small problems */
471        assert(Cbc_isProvenOptimal(model));
472        assert(xs);
473    }
474    if (xs) {
475        /* solution check
476
477        // total number of queens */
478        int nq = 0;
479        for ( i=0 ; (i<n) ; ++i )
480            for ( j=0 ; (j<n) ; ++j )
481                if ((fabs(xs[x[i][j]]-1.0))<1e-5)
482                    nq++;
483        assert(nq == n);
484        for ( i=0 ; (i<n) ; ++i )
485        {
486            nq = 0;
487            for ( j=0 ; (j<n) ; ++j )
488                if ((fabs(xs[x[i][j]]-1.0))<1e-5)
489                    nq++;
490            assert( nq == 1);
491        }
492        for ( j=0 ; (j<n) ; ++j )
493        {
494            nq = 0;
495            for ( i=0 ; (i<n) ; ++i )
496                if ((fabs(xs[x[i][j]]-1.0))<1e-5)
497                    nq++;
498            assert( nq == 1);
499        }
500    }
501
502    free(idx);
503    free(coef);
504    free(x[0]);
505    free(x);
506
507    Cbc_deleteModel(model);
508}
509
510int main() {
511
512    printf("Knapsack test\n");
513    testKnapsack();
514    printf("SOS test\n");
515    testSOS();
516    printf("Infeasible test\n");
517    testIntegerInfeasible();
518    printf("Unbounded test\n");
519    testIntegerUnbounded();
520    /*printf("Problem modification test\n");
521    testProblemModification();*/
522    printf("Integer bounds test\n");
523    testIntegerBounds();
524    printf("n-Queens test\n");
525    testQueens(10);
526    testQueens(25);
527    testQueens(50);
528    testQueens(75);
529
530    return 0;
531}
Note: See TracBrowser for help on using the repository browser.