lpcore.cpp 15.8 KB
Newer Older
1
/* Copyright (C) 2017 INRA
Gauthier Quesnel's avatar
Gauthier Quesnel committed
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 *
 * Permission is hereby granted, free of charge, to any person obtaining a
 * copy of this software and associated documentation files (the
 * "Software"), to deal in the Software without restriction, including
 * without limitation the rights to use, copy, modify, merge, publish,
 * distribute, sublicense, and/or sell copies of the Software, and to
 * permit persons to whom the Software is furnished to do so, subject to
 * the following conditions:
 *
 * The above copyright notice and this permission notice shall be included
 * in all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
 * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 */

Gauthier Quesnel's avatar
Gauthier Quesnel committed
23
24
#include <baryonyx/core>

Gauthier Quesnel's avatar
Gauthier Quesnel committed
25
#include "lpformat-consistency.hpp"
26
#include "lpformat-io.hpp"
Gauthier Quesnel's avatar
Gauthier Quesnel committed
27
#include "mitm.hpp"
28
#include "utils.hpp"
29
30

#include <algorithm>
31
#include <fstream>
Gauthier Quesnel's avatar
Gauthier Quesnel committed
32

33
34
35
36
37
38
#include <cerrno>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstring>

39
#ifndef _WIN32
40
41
#include <getopt.h>
#include <sys/types.h>
42
43
44
#include <unistd.h>
#endif

45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
namespace {

double
to_double(const char* s, double bad_value) noexcept
{
    char* c;
    errno = 0;
    double value = std::strtod(s, &c);

    if ((errno == ERANGE and (value == HUGE_VAL or value == -HUGE_VAL)) or
        (value == 0.0 and c == s))
        return bad_value;

    return value;
}

long
to_long(const char* s, long bad_value) noexcept
{
    char* c;
    errno = 0;
    long value = std::strtol(s, &c, 10);

    if ((errno == ERANGE and (value == LONG_MIN or value == LONG_MAX)) or
        (value == 0 and c == s))
        return bad_value;

    return value;
}

Gauthier Quesnel's avatar
Gauthier Quesnel committed
75
std::tuple<std::string, baryonyx::parameter>
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
split_param(const char* param) noexcept
{
    std::string name, value;

    while (*param) {
        if (isalpha(*param) or *param == '_' or *param == '-')
            name += *param;
        else
            break;

        param++;
    }

    if (*param and (*param == ':' or *param == '=')) {
        param++;

        while (*param)
            value += *param++;
    }

    auto valuel = to_long(value.c_str(), LONG_MIN);
    auto valued = to_double(value.c_str(), -HUGE_VAL);

    double tmp;
    if (valued != -HUGE_VAL and std::modf(valued, &tmp))
Gauthier Quesnel's avatar
Gauthier Quesnel committed
101
        return std::make_tuple(name, baryonyx::parameter(valued));
102
103

    if (valuel != LONG_MIN)
Gauthier Quesnel's avatar
Gauthier Quesnel committed
104
        return std::make_tuple(name, baryonyx::parameter(valuel));
105

Gauthier Quesnel's avatar
Gauthier Quesnel committed
106
    return std::make_tuple(name, baryonyx::parameter(value));
107
108
109
}

void
Gauthier Quesnel's avatar
Gauthier Quesnel committed
110
help(std::shared_ptr<baryonyx::context> ctx) noexcept
111
112
113
114
115
116
117
118
119
120
121
122
123
{
    ctx->info("--help|-h                   This help message\n"
              "--param|-p [name]:[value]   Add a new parameter (name is"
              " [a-z][A-Z]_ value can be a double, an integer otherwise a"
              " string.\n"
              "--optimize|-O               Optimize model (default "
              "feasibility search only)\n"
              "--limit int                 Set limit\n"
              "--quiet                     Remove any verbose message\n"
              "--verbose|-v int            Set verbose level\n");
}
}

Gauthier Quesnel's avatar
Gauthier Quesnel committed
124
namespace baryonyx {
Gauthier Quesnel's avatar
Gauthier Quesnel committed
125

126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
class standard_stream_logger : public context::logger
{
public:
    void write(int priority,
               const char* file,
               int line,
               const char* fn,
               const char* format,
               va_list args) noexcept override
    {
        if (priority > 5)
            vfprintf(stdout, format, args);
        else {
            fprintf(stderr,
                    "lp: %d at %d in function '%s' from file %s: ",
                    priority,
                    line,
                    fn,
                    file);
            vfprintf(stderr, format, args);
        }
    }

Gauthier Quesnel's avatar
Gauthier Quesnel committed
149
    void write(baryonyx::context::message_type m,
150
151
152
               const char* format,
               va_list args) noexcept override
    {
153
#ifndef __WIN32
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
        if (::isatty(STDOUT_FILENO)) {
            switch (m) {
            case context::message_type::emerg:
            case context::message_type::alert:
            case context::message_type::crit:
            case context::message_type::err:
                ::puts("\033[30m\033[2m");
                break;
            case context::message_type::warning:
                ::puts("\033[32m\033[1m");
                break;
            case context::message_type::notice:
                break;
            case context::message_type::info:
                break;
            case context::message_type::debug:
                ::puts("\033[33m\033[1m");
                break;
            }

            vfprintf(stdout, format, args);
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194

            switch (m) {
            case context::message_type::emerg:
            case context::message_type::alert:
            case context::message_type::crit:
            case context::message_type::err:
                ::puts("\033[30m\033[0m");
                break;
            case context::message_type::warning:
                ::puts("\033[30m\033[0m");
                break;
            case context::message_type::notice:
                break;
            case context::message_type::info:
                break;
            case context::message_type::debug:
                ::puts("\033[30m\033[0m");
                break;
            }

195
196
197
198
199
200
201
202
203
        } else {
            vfprintf(stdout, format, args);
        }
#else
        vfprintf(stdout, format, args);
#endif
    }
};

204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
int
context::parse(int argc, char* argv[]) noexcept
{
    const char* const short_opts = "Ohp:l:qv:";
    const struct option long_opts[] = { { "optimize", 0, nullptr, 'O' },
                                        { "help", 0, nullptr, 'h' },
                                        { "param", 1, nullptr, 'p' },
                                        { "limit", 1, nullptr, 'l' },
                                        { "quiet", 0, nullptr, 'q' },
                                        { "verbose", 1, nullptr, 'v' },
                                        { 0, 0, nullptr, 0 } };

    int opt_index;
    int verbose = 1;
    int quiet = 0;

Gauthier Quesnel's avatar
Gauthier Quesnel committed
220
    auto ctx = std::make_shared<baryonyx::context>();
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
    ctx->set_standard_stream_logger();

    for (;;) {
        const auto opt =
          getopt_long(argc, argv, short_opts, long_opts, &opt_index);
        if (opt == -1)
            break;

        switch (opt) {
        case 0:
            break;
        case 'O':
            m_optimize = true;
            break;
        case 'l':
            m_parameters["limit"] = ::to_long(::optarg, 1000l);
            break;
        case 'h':
            ::help(ctx);
            break;
        case 'p': {
            std::string name;
Gauthier Quesnel's avatar
Gauthier Quesnel committed
243
            baryonyx::parameter value;
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
            std::tie(name, value) = ::split_param(::optarg);
            m_parameters[name] = value;
        } break;
        case 'q':
            quiet = 1;
            break;
        case '?':
        default:
            ctx->error("Unknown command line option\n");
            return -1;
        };
    }

    if (quiet)                    // priority to quiet over the
        ctx->set_log_priority(3); // verbose mode.
    else if (verbose >= 0 and verbose <= 7)
        ctx->set_log_priority(verbose);

    return ::optind;
}

void
context::set_parameter(const std::string& name, double p) noexcept
{
    if (name.empty())
        return;

    if (not std::isalnum(name[0]))
        return;

    m_parameters[name] = p;
}

void
context::set_parameter(const std::string& name, long int p) noexcept
{
    if (name.empty())
        return;

    if (not std::isalnum(name[0]))
        return;

    m_parameters[name] = p;
}

void
context::set_parameter(const std::string& name, std::string p) noexcept
{
    if (name.empty())
        return;

    if (not std::isalnum(name[0]))
        return;

    m_parameters[name] = std::move(p);
}

double
context::get_real_parameter(const std::string& name, double def) const noexcept
{
    auto it = m_parameters.find(name);
    if (it == m_parameters.cend())
        return def;

    if (it->second.type == parameter::tag::real)
        return it->second.d;

    if (it->second.type == parameter::tag::integer)
        return static_cast<double>(it->second.l);

    warning("fail to convert parameter %s\n", name.c_str());

    return def;
}

long int
context::get_integer_parameter(const std::string& name, long int def) const
  noexcept
{
    auto it = m_parameters.find(name);
    if (it == m_parameters.cend())
        return def;

    if (it->second.type == parameter::tag::integer)
        return it->second.l;

    if (it->second.type == parameter::tag::real)
        return static_cast<long>(it->second.d);

    warning("fail to convert parameter %s\n", name.c_str());

    return def;
}

std::string
context::get_string_parameter(const std::string& name, std::string def) const
  noexcept
{
    auto it = m_parameters.find(name);
    if (it == m_parameters.cend())
        return def;

    if (it->second.type == parameter::tag::string)
        return it->second.s;

    if (it->second.type == parameter::tag::real)
        return std::to_string(it->second.d);

    if (it->second.type == parameter::tag::integer)
        return std::to_string(it->second.l);

    warning("fail to convert parameter %s\n", name.c_str());

    return def;
}

360
361
362
void
context::set_log_priority(int priority) noexcept
{
363
    m_log_priority = priority < 0 ? 0 : 7 < priority ? 7 : priority;
364
365
366
367
368
369
370
371
}

int
context::get_log_priority() const noexcept
{
    return m_log_priority;
}

372
373
374
375
376
377
bool
context::optimize() const noexcept
{
    return m_optimize;
}

378
379
380
381
382
383
384
385
386
387
388
389
390
void
context::set_standard_stream_logger() noexcept
{
    set_logger(std::make_unique<standard_stream_logger>());
}

void
context::set_logger(std::unique_ptr<logger> function) noexcept
{
    m_logger = std::move(function);
}

#ifndef LP_DISABLE_LOGGING
391
392
393
394
395
//
// Default, the logging system is active and the call to the @c log function
// are send to the logger functor. Define LP_DISABLE_LOGGING as preprocessor
// value to hide all logging message..
//
396
void
397
context::log(message_type type, const char* format, ...) const noexcept
398
399
400
401
{
    if (not m_logger)
        return;

402
    switch (type) {
Gauthier Quesnel's avatar
Gauthier Quesnel committed
403
    case baryonyx::context::message_type::emerg:
404
        break;
Gauthier Quesnel's avatar
Gauthier Quesnel committed
405
    case baryonyx::context::message_type::alert:
406
407
408
        if (m_log_priority < 1)
            return;
        break;
Gauthier Quesnel's avatar
Gauthier Quesnel committed
409
    case baryonyx::context::message_type::crit:
410
411
412
        if (m_log_priority < 2)
            return;
        break;
Gauthier Quesnel's avatar
Gauthier Quesnel committed
413
    case baryonyx::context::message_type::err:
414
415
416
        if (m_log_priority < 3)
            return;
        break;
Gauthier Quesnel's avatar
Gauthier Quesnel committed
417
    case baryonyx::context::message_type::warning:
418
419
420
        if (m_log_priority < 4)
            return;
        break;
Gauthier Quesnel's avatar
Gauthier Quesnel committed
421
    case baryonyx::context::message_type::notice:
422
423
424
        if (m_log_priority < 5)
            return;
        break;
Gauthier Quesnel's avatar
Gauthier Quesnel committed
425
    case baryonyx::context::message_type::info:
426
427
428
        if (m_log_priority < 6)
            return;
        break;
Gauthier Quesnel's avatar
Gauthier Quesnel committed
429
    case baryonyx::context::message_type::debug:
430
431
432
433
434
        if (m_log_priority < 7)
            return;
        break;
    }

435
436
437
438
439
440
441
442
443
444
445
446
447
    va_list args;

    va_start(args, format);
    m_logger->write(type, format, args);
    va_end(args);
}

void
context::log(int priority,
             const char* file,
             int line,
             const char* fn,
             const char* format,
448
             ...) const noexcept
449
{
450
    if (not m_logger and m_log_priority < priority)
451
452
453
454
455
456
457
458
459
460
        return;

    va_list args;

    va_start(args, format);
    m_logger->write(priority, file, line, fn, format, args);
    va_end(args);
}

void
461
context::info(const char* format, ...) const noexcept
462
{
463
    if (not m_logger or m_log_priority < 6)
464
465
466
467
468
469
470
471
472
473
        return;

    va_list args;

    va_start(args, format);
    m_logger->write(context::message_type::info, format, args);
    va_end(args);
}

void
474
context::debug(const char* format, ...) const noexcept
475
{
476
    if (not m_logger or m_log_priority < 7)
477
478
479
480
481
482
483
484
485
486
        return;

    va_list args;

    va_start(args, format);
    m_logger->write(context::message_type::debug, format, args);
    va_end(args);
}

void
487
context::warning(const char* format, ...) const noexcept
488
{
489
    if (not m_logger and m_log_priority < 4)
490
491
492
493
494
495
496
497
498
499
        return;

    va_list args;

    va_start(args, format);
    m_logger->write(context::message_type::warning, format, args);
    va_end(args);
}

void
500
context::error(const char* format, ...) const noexcept
501
{
502
    if (not m_logger and m_log_priority < 3)
503
504
505
506
507
508
509
510
        return;

    va_list args;

    va_start(args, format);
    m_logger->write(context::message_type::err, format, args);
    va_end(args);
}
511
512
#else
void
513
context::log(message_type, const char*, va_list) const noexcept
514
515
516
517
{
}

void
518
519
context::log(int, const char*, int, const char*, const char*, va_list) const
  noexcept
520
521
522
523
{
}

void
524
context::info(const char*, va_list) const noexcept
525
526
{
}
527

528
void
529
context::warning(const char*, va_list) const noexcept
530
531
532
533
{
}

void
534
context::debug(const char*, va_list) const noexcept
535
536
537
538
{
}

void
539
context::error(const char*, va_list) const noexcept
540
541
{
}
542
543
#endif

544
problem
545
546
make_problem(std::shared_ptr<baryonyx::context> ctx,
             const std::string& filename)
Gauthier Quesnel's avatar
Gauthier Quesnel committed
547
{
548
549
    ctx->info("problem read from file `%s'\n", filename.c_str());

Gauthier Quesnel's avatar
Gauthier Quesnel committed
550
551
552
553
554
555
556
    std::ifstream ifs;
    ifs.exceptions(std::ifstream::badbit);
    ifs.open(filename);

    return details::read_problem(ifs);
}

557
problem
Gauthier Quesnel's avatar
Gauthier Quesnel committed
558
make_problem(std::shared_ptr<baryonyx::context> ctx, std::istream& is)
Gauthier Quesnel's avatar
Gauthier Quesnel committed
559
{
560
561
    ctx->info("problem read from stream\n");

Gauthier Quesnel's avatar
Gauthier Quesnel committed
562
563
564
565
566
    is.exceptions(std::ifstream::badbit);

    return details::read_problem(is);
}

567
568
std::ostream&
operator<<(std::ostream& os, const problem& p)
Gauthier Quesnel's avatar
Gauthier Quesnel committed
569
570
571
572
573
574
{
    details::problem_writer pw(p, os);

    return os;
}

575
result
Gauthier Quesnel's avatar
Gauthier Quesnel committed
576
solve(std::shared_ptr<baryonyx::context> ctx, problem& pb)
Gauthier Quesnel's avatar
Gauthier Quesnel committed
577
578
579
{
    check(pb);

580
    return mitm_solve(ctx, pb);
581
582
583
}

result
Gauthier Quesnel's avatar
Gauthier Quesnel committed
584
optimize(std::shared_ptr<baryonyx::context> ctx, problem& pb)
585
586
587
{
    check(pb);

588
    return mitm_optimize(ctx, pb);
Gauthier Quesnel's avatar
Gauthier Quesnel committed
589
590
}

591
template<typename functionT, typename variablesT>
Gauthier Quesnel's avatar
Gauthier Quesnel committed
592
593
594
595
596
597
598
599
600
601
602
603
int
compute_function(const functionT& fct, const variablesT& vars) noexcept
{
    int v{ 0 };

    for (auto& f : fct)
        v += f.factor * vars[f.variable_index];

    return v;
}

bool
604
is_valid_solution(const problem& pb, const std::vector<int>& variable_value)
Gauthier Quesnel's avatar
Gauthier Quesnel committed
605
{
606
    Expects(not variable_value.empty(), "variables vector empty");
607

Gauthier Quesnel's avatar
Gauthier Quesnel committed
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
    for (auto& cst : pb.equal_constraints) {
        if (compute_function(cst.elements, variable_value) != cst.value) {
            printf("constraint %s (=) fails\n", cst.label.c_str());
            return false;
        }
    }

    for (auto& cst : pb.greater_constraints) {
        if (compute_function(cst.elements, variable_value) <= cst.value) {
            printf("constraint %s (>) fails\n", cst.label.c_str());
            return false;
        }
    }

    for (auto& cst : pb.greater_equal_constraints) {
        if (compute_function(cst.elements, variable_value) < cst.value) {
            printf("constraint %s (>=) fails\n", cst.label.c_str());
            return false;
        }
    }

    for (auto& cst : pb.less_constraints) {
        if (compute_function(cst.elements, variable_value) >= cst.value) {
            printf("constraint %s (<) fails\n", cst.label.c_str());
            return false;
        }
    }

    for (auto& cst : pb.greater_constraints) {
        if (compute_function(cst.elements, variable_value) > cst.value) {
            printf("constraint %s (<=) fails\n", cst.label.c_str());
            return false;
        }
    }

    return true;
}
645
646

double
647
compute_solution(const problem& pb, const std::vector<int>& variable_value)
648
{
649
650
    Expects(not variable_value.empty(), "variables vector empty");

651
652
653
654
655
656
657
    double ret = pb.objective.constant;

    for (auto& elem : pb.objective.elements)
        ret += elem.factor * variable_value[elem.variable_index];

    return ret;
}
Gauthier Quesnel's avatar
Gauthier Quesnel committed
658
659

} // namespace baryonyx