8

This is where decomposition algorithms (specifically Dantzig-Wolfe can be quite useful). My thesis work and subsequent OSS in COIN provides APIs to do this kind of thing: https://projects.coin-or.org/Dip The basic idea is that the oracle is the graph implementation while the side constraints are modeled as the master constraints in the decomposition ...


6

In general ILP solvers are not as efficient in solving the Maximum Matching problem. A comparison of efficient matching algorithm implementations, as well as an ILP formulation for the Maximum Cardinality Matching Problem and the Minimum Weight perfect matching problem can be found in Figures 5 and 6 of this paper: Dimitrios Michail, Joris Kinable, Barak ...


4

If you are willing to entertain an element of risk, and assuming that the feasible region is bounded, you might get away with a single new binary variable $z$. Assume that the feasible region $X$ is bounded, which implies that the number of feasible $x$ is finite. Generate a vector $r\in \mathbb{R}^n$ uniformly over the unit rectangle. Since the feasible ...


4

Here's one way, assuming $L_i \le x_i \le U_i$. Introduce binary variables $y_i$ and $z_i$, with linear constraints \begin{align} \sum_i (y_i+z_i) &\ge 1 \tag1\\ y_i + z_i &\le 1 &\text{for all $i$} \tag2\\ L_i(1-z_i) + (x_i^*+1)z_i \le x_i &\le (x_i^*-1)y_i + U_i(1-y_i) &\text{for all $i$} \tag3\\ \end{align} Constraint $(1)$ forces $...


3

Have a look at MQLib, which contains efficient implementations of many published algorithms. Their paper is awesome too. You can find a lot of code for QUBO online, one of the most publicized being qbsolv from Dwave. It is meant as a demonstrator of how much better quantum algorithms are, and the method is very basic. In general, I would take any hype on ...


3

This is what I have been using. Assume $\color{darkred}x_i \in \{\color{darkblue}L_i,\dots,\color{darkblue}U_i\}$ and we want: $$ \sum_i |\color{darkred}x_i-\color{darkblue}x_i^*| \ge 1$$ or $$\begin{align} & \color{darkred}z_i \le |\color{darkred}x_i-\color{darkblue}x_i^*| \\ & \sum_i \color{darkred}z_i \ge 1 \end{align}$$ This can be modeled with ...


3

Here's one possible formulation, where $a_1,\dots, a_n$ are the values of the $n$ integers. Let binary decision variable $x_{i,j}$ indicate whether integer $i$ is assigned to subset $j\in\{1,\dots,k\}$. The problem is to maximize $z$ subject to \begin{align} \sum_j x_{i,j} &= 1 &&\text{for all $i$} \tag1\\ \sum_i a_i x_{i,j} &\ge z &&...


3

https://en.m.wikipedia.org/wiki/Diophantine_equation any milp solver can handle it, but maybe something like mathematica/mable has special algortihms or one can use the algorithm described by the wiki entry 4a) https://en.m.wikipedia.org/wiki/Lattice_problem 4b) is i think polytime, either the problem is unbounded, infeasible or all solutions are optimal.


2

Assuming that the routing of the vehicles is part of the solution, you will likely need a ton of binary variables. The binary variables will determine both which vehicles serve which stations and also the sequencing. There are multiple ways to approach this. For instance, you might have $x_{ij}=1$ if vehicle $i$ serves station $j$ and $y_{jk}=1$ if station $...


2

Maxcut with CPLEX CPOptimizer in https://github.com/AlexFleischerParis/howtowithopl/blob/master/maxcutcpo.mod using CP; execute { // time limit 10 s cp.param.timelimit=10; } int n=400; range r=1..n; // Random graph float edge_prob=0.5; int weight_range=10; int big=100000; tuple t { int i; int j; } {t} s={<i,j> | ordered i,j in r}; int ...


1

{0,1}-ILP can be rewritten as Pseudo-Boolean programming or MAX-Sat. It might be worth to explore alternative solving technologies for your problem.


Only top voted, non community-wiki answers of a minimum length are eligible