solver_highs: init

4 files changed, 269 insertions, 20 deletions

diff --git a/src/evanix.c b/src/evanix.c
index c75bd70..293c8fe 100644
--- a/src/evanix.c
+++ b/src/evanix.c
@@ -1,11 +1,13 @@
 #include <getopt.h>
 #include <stdlib.h>
 #include <string.h>
+#include <errno.h>
 
 #include "build.h"
 #include "evanix.h"
 #include "queue.h"
 #include "solver_greedy.h"
+#include "solver_highs.h"
 #include "util.h"
 
 static const char usage[] =
@@ -17,11 +19,12 @@ static const char usage[] =
 	"built.\n"
 	"  -s, --system                     System to build for.\n"
 	"  -m, --max-build                  Max number of builds.\n"
+	"  -b, --break-evanix               Enable experimental features.\n"
 	"  -r, --solver-report              Print solver report.\n"
 	"  -p, --pipelined          <bool>  Use evanix build pipeline.\n"
 	"  -l, --check_cache-status <bool>  Perform cache locality check.\n"
 	"  -c, --close-unused-fd    <bool>  Close stderr on exec.\n"
-	"  -k, --solver             greedy  Solver to use.\n"
+	"  -k, --solver       highs|greedy  Solver to use.\n"
 	"\n";
 
 struct evanix_opts_t evanix_opts = {
@@ -34,6 +37,7 @@ struct evanix_opts_t evanix_opts = {
 	.solver_report = false,
 	.check_cache_status = true,
 	.solver = solver_greedy,
+	.break_evanix = false,
 };
 
 static int evanix_build_thread_create(struct build_thread *build_thread);
@@ -122,7 +126,7 @@ out_free:
 	return ret;
 }
 
-int main(int argc, char *argv[])
+int opts_read(struct evanix_opts_t *opts, char **expr, int argc, char *argv[])
 {
 	extern int optind, opterr, optopt;
 	extern char *optarg;
@@ -132,6 +136,7 @@ int main(int argc, char *argv[])
 		{"help", no_argument, NULL, 'h'},
 		{"flake", no_argument, NULL, 'f'},
 		{"dry-run", no_argument, NULL, 'd'},
+		{"break-evanix", no_argument, NULL, 'b'},
 		{"solver", required_argument, NULL, 'k'},
 		{"system", required_argument, NULL, 's'},
 		{"solver-report", no_argument, NULL, 'r'},
@@ -147,23 +152,28 @@ int main(int argc, char *argv[])
 		switch (c) {
 		case 'h':
 			printf("%s", usage);
-			exit(EXIT_SUCCESS);
+			return -EINVAL;
 			break;
 		case 'f':
-			evanix_opts.isflake = true;
+			opts->isflake = true;
+			break;
+		case 'b':
+			opts->break_evanix = true;
 			break;
 		case 'd':
-			evanix_opts.isdryrun = true;
+			opts->isdryrun = true;
 			break;
 		case 's':
-			evanix_opts.system = optarg;
+			opts->system = optarg;
 			break;
 		case 'r':
-			evanix_opts.solver_report = true;
+			opts->solver_report = true;
 			break;
 		case 'k':
 			if (!strcmp(optarg, "greedy")) {
-				evanix_opts.solver = solver_greedy;
+				opts->solver = solver_greedy;
+			} else if (!strcmp(optarg, "highs")) {
+				opts->solver = solver_highs;
 			} else {
 				fprintf(stderr,
 					"option -%c has an invalid solver "
@@ -171,7 +181,7 @@ int main(int argc, char *argv[])
 					"Try 'evanix --help' for more "
 					"information.\n",
 					c);
-				exit(EXIT_FAILURE);
+				return -EINVAL;
 			}
 			break;
 		case 'm':
@@ -183,10 +193,10 @@ int main(int argc, char *argv[])
 					"Try 'evanix --help' for more "
 					"information.\n",
 					c);
-				exit(EXIT_FAILURE);
+				return -EINVAL;
 			}
 
-			evanix_opts.max_build = ret;
+			opts->max_build = ret;
 			break;
 		case 'p':
 			ret = atob(optarg);
@@ -196,10 +206,10 @@ int main(int argc, char *argv[])
 					"Try 'evanix --help' for more "
 					"information.\n",
 					c);
-				exit(EXIT_FAILURE);
+				return -EINVAL;
 			}
 
-			evanix_opts.ispipelined = ret;
+			opts->ispipelined = ret;
 			break;
 		case 'c':
 			ret = atob(optarg);
@@ -209,10 +219,10 @@ int main(int argc, char *argv[])
 					"Try 'evanix --help' for more "
 					"information.\n",
 					c);
-				exit(EXIT_FAILURE);
+				return -EINVAL;
 			}
 
-			evanix_opts.close_unused_fd = ret;
+			opts->close_unused_fd = ret;
 			break;
 		case 'l':
 			ret = atob(optarg);
@@ -222,24 +232,43 @@ int main(int argc, char *argv[])
 					"Try 'evanix --help' for more "
 					"information.\n",
 					c);
-				exit(EXIT_FAILURE);
+				return -EINVAL;
 			}
 
-			evanix_opts.check_cache_status = ret;
+			opts->check_cache_status = ret;
 			break;
 		default:
 			fprintf(stderr,
 				"Try 'evanix --help' for more information.\n");
-			exit(EXIT_FAILURE);
+			return -EINVAL;
 			break;
 		}
 	}
 	if (optind != argc - 1) {
 		fprintf(stderr, "evanix: invalid expr operand\n"
 				"Try 'evanix --help' for more information.\n");
-		exit(EXIT_FAILURE);
+		return -EINVAL;
+	}
+
+	if (opts->solver == solver_highs && !opts->break_evanix) {
+		fprintf(stderr,
+			"Running --solver=highs without --break-evanix\n");
+		return -EINVAL;
 	}
 
+	*expr = argv[optind];
+	return 0;
+}
+
+int main(int argc, char *argv[])
+{
+	char *expr;
+	int ret;
+
+	ret = opts_read(&evanix_opts, &expr, argc, argv);
+	if (ret < 0)
+		exit(EXIT_FAILURE);
+
 	ret = evanix(argv[optind]);
 	if (ret < 0)
 		exit(EXIT_FAILURE);
diff --git a/src/jobid.c b/src/jobid.c
index d1ca8ab..07f3ea5 100644
--- a/src/jobid.c
+++ b/src/jobid.c
@@ -3,8 +3,8 @@
 #include <stdlib.h>
 #include <string.h>
 
-#include "jobs.h"
 #include "jobid.h"
+#include "jobs.h"
 #include "util.h"
 
 static int dag_id_assign(struct job *j, struct jobid *jobid);
@@ -42,6 +42,9 @@ static int dag_id_assign(struct job *j, struct jobid *jobid)
 
 void jobid_free(struct jobid *jid)
 {
+	if (jid == NULL)
+		return;
+
 	free(jid->jobs);
 	free(jid);
 }
diff --git a/src/meson.build b/src/meson.build
index d4ccec2..b0dac71 100644
--- a/src/meson.build
+++ b/src/meson.build
@@ -9,6 +9,7 @@ e = executable(
 		'build.c',
 		'jobid.c',
 		'solver_greedy.c',
+		'solver_highs.c',
 	],
 
 	include_directories: evanix_inc,
diff --git a/src/solver_highs.c b/src/solver_highs.c
new file mode 100644
index 0000000..722fe27
--- /dev/null
+++ b/src/solver_highs.c
@@ -0,0 +1,216 @@
+#include <assert.h>
+#include <errno.h>
+#include <highs/interfaces/highs_c_api.h>
+#include <math.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+#include "jobid.h"
+#include "solver_highs.h"
+#include "util.h"
+
+static int solver_highs_unwrapped(double *solution, struct job_clist *q,
+				  int32_t resources, struct jobid *jobid)
+{
+	HighsInt precedence_index[2];
+	double precedence_value[2];
+	struct job *j;
+	int ret;
+
+	double *col_profit = NULL;
+	double *col_lower = NULL;
+	double *col_upper = NULL;
+	HighsInt *integrality = NULL;
+	void *highs = NULL;
+
+	HighsInt *constraint_index = NULL;
+	double *constraint_value = NULL;
+
+	/* set objective */
+	col_profit = calloc(jobid->filled, sizeof(*col_profit));
+	if (col_profit == NULL) {
+		print_err("%s", strerror(errno));
+		return -errno;
+	}
+	for (size_t i = 0; i < jobid->filled; i++) {
+		if (jobid->jobs[i]->scheduled)
+			col_profit[i] = 1.0;
+	}
+
+	col_lower = calloc(jobid->filled, sizeof(*col_lower));
+	if (col_lower == NULL) {
+		print_err("%s", strerror(errno));
+		ret = -errno;
+		goto out_free_col_profit;
+	}
+
+	col_upper = malloc(jobid->filled * sizeof(*col_lower));
+	if (col_upper == NULL) {
+		print_err("%s", strerror(errno));
+		ret = -errno;
+		goto out_free_col_profit;
+	}
+	for (size_t i = 0; i < jobid->filled; i++)
+		col_upper[i] = 1.0;
+
+	integrality = malloc(jobid->filled * sizeof(*integrality));
+	for (size_t i = 0; i < jobid->filled; i++)
+		integrality[i] = 1;
+
+	highs = Highs_create();
+	ret = Highs_setBoolOptionValue(highs, "output_flag", 1);
+	if (ret != kHighsStatusOk) {
+		print_err("%s", "highs did not return kHighsStatusOk");
+		ret = -EPERM;
+		goto out_free_col_profit;
+	}
+	ret = Highs_addCols(highs, jobid->filled, col_profit, col_lower,
+			    col_upper, 0, NULL, NULL, NULL);
+	if (ret != kHighsStatusOk) {
+		print_err("%s", "highs did not return kHighsStatusOk");
+		ret = -EPERM;
+		goto out_free_col_profit;
+	}
+
+	/* set resource constraint */
+	constraint_index = malloc(jobid->filled * sizeof(*constraint_index));
+	if (constraint_index == NULL) {
+		print_err("%s", strerror(errno));
+		ret = -errno;
+		goto out_free_col_profit;
+	}
+	for (size_t i = 0; i < jobid->filled; i++)
+		constraint_index[i] = i;
+
+	constraint_value = malloc(jobid->filled * sizeof(*constraint_value));
+	if (constraint_value == NULL) {
+		print_err("%s", strerror(errno));
+		ret = -errno;
+		goto out_free_col_profit;
+	}
+	for (size_t i = 0; i < jobid->filled; i++)
+		constraint_value[i] = 1.0;
+
+	ret = Highs_addRow(highs, 0, resources, jobid->filled + 1,
+			   constraint_index, constraint_value);
+	if (ret != kHighsStatusOk) {
+		print_err("%s", "highs did not return kHighsStatusOk");
+		ret = -EPERM;
+		goto out_free_col_profit;
+	}
+
+	/* set precedance constraints */
+	CIRCLEQ_FOREACH (j, q, clist) {
+		for (size_t i = 0; i < j->deps_filled; j++) {
+			/* follow the CSR matrix structure */
+			if (j->id < j->deps[i]->id) {
+				precedence_index[0] = j->id;
+				precedence_index[1] = j->deps[i]->id;
+				precedence_value[0] = 1;
+				precedence_value[1] = -1;
+			} else {
+				precedence_index[0] = j->deps[i]->id;
+				precedence_index[1] = j->id;
+				precedence_value[0] = -1;
+				precedence_value[1] = 1;
+			}
+
+			ret = Highs_addRow(highs, -INFINITY, 0, 2,
+					   precedence_index, precedence_value);
+		}
+	}
+
+	/* run milp solver */
+	ret = Highs_changeObjectiveSense(highs, kHighsObjSenseMaximize);
+	if (ret != kHighsStatusOk) {
+		print_err("%s", "highs did not return kHighsStatusOk");
+		ret = -EPERM;
+		goto out_free_col_profit;
+	}
+	ret = Highs_changeColsIntegralityByMask(highs, integrality,
+						integrality);
+	if (ret != kHighsStatusOk) {
+		print_err("%s", "highs did not return kHighsStatusOk");
+		ret = -EPERM;
+		goto out_free_col_profit;
+	}
+	ret = Highs_run(highs);
+	if (ret != kHighsStatusOk) {
+		print_err("%s", "highs did not return kHighsStatusOk");
+		ret = -EPERM;
+		goto out_free_col_profit;
+	}
+	ret = Highs_getSolution(highs, solution, NULL, NULL, NULL);
+	if (ret != kHighsStatusOk) {
+		print_err("%s", "highs did not return kHighsStatusOk");
+		ret = -EPERM;
+		goto out_free_col_profit;
+	}
+
+out_free_col_profit:
+	free(col_profit);
+	free(col_lower);
+	free(col_upper);
+	free(integrality);
+	free(constraint_value);
+	free(constraint_index);
+
+	return ret;
+}
+
+static int job_get(struct job **job, struct job_clist *q)
+{
+	struct job *j;
+
+	CIRCLEQ_FOREACH (j, q, clist) {
+		if (j->stale)
+			continue;
+
+		*job = j;
+		return 0;
+	}
+
+	print_err("%s", "empty queue");
+	return -ESRCH;
+}
+
+int solver_highs(struct job **job, struct job_clist *q, int32_t resources)
+{
+	static bool solved = false;
+	struct jobid *jobid = NULL;
+	double *solution = NULL;
+	int ret = 0;
+
+	if (solved)
+		goto out_free_jobid;
+
+	ret = jobid_init(q, &jobid);
+	if (ret < 0)
+		return ret;
+
+	solution = malloc(jobid->filled * sizeof(*solution));
+	if (solution == NULL) {
+		print_err("%s", strerror(errno));
+		ret = -errno;
+		goto out_free_jobid;
+	}
+
+	ret = solver_highs_unwrapped(solution, q, resources, jobid);
+	if (ret < 0)
+		goto out_free_jobid;
+
+	for (size_t i = 0; i < jobid->size; i++) {
+		if (solution[i] == 0.0)
+			job_stale_set(jobid->jobs[i]);
+	}
+
+	solved = true;
+out_free_jobid:
+	jobid_free(jobid);
+	free(solution);
+
+	if (ret < 0)
+		return ret;
+	else
+		return job_get(job, q);
+}