The decision version of the problem Integar Linear Programming is the following: - Input: two matrices $A\in \mathcal{M}_n(\mathbb{Z})$ and $B\in \mathcal{M}_{n,1}(\mathbb{Z})$. - Question: is there a matrix $X\in \mathcal{M}_{n,1}(\mathbb{Z})$ such that $AX\leqslant B$? (the inequality being component by component). This is a well-known $\mathsf{NP}$-complete problem, but I struggle to prove that it is in $\mathsf{NP}$. An obvious certificate for a positive instance $(A, B)$ would be such a $X$, but there is no guarantee that the size of such an $X$ is polynomial in the size of the input (here, we can consider the size of the instance $(A, B)$ to be $n^2\log_2(\max(|a_{ij}|, |b_i|)$ and the size of $X$ to be $n\log_2(\max |x_i|))$. What I expect is that if there is such an $X$, there is one with coefficients not too big, but I don't know how to prove this. While this is a computer science formulation, I am sure that there is some maths behind this to prove the result, so maybe this question should be asked on maths.SE? This document states: ILP ∈ NP. (Not obvious! Need a little math to prove it. Proof omitted.) and this one states: Unlike with most NP-complete problems, it is not that easy to see that ILP ∈ NP, since a witness need not necessarily have polynomial size. This is the case though, but the reasons are beyond the scope of the course. But none gives further references. (Note: I think that this problem is an answer to my previous question)

We're looking to model the following problem as a standard optimization problem (or even a non-standard one). We can come close, but nothing seems to fit exactly. We have a working algorithm coded, but the performance is unacceptable. Problem statement The problem is set up in two parts. First, there are fixed data: - a set of objects `S`. - for each object `o` in `S`, a subset of objects in `S` that are "compatible" with `o`. Being compatible is guaranteed to be symmetric. Typically, each object is compatible with 90% or more of the objects in `S`. Then there are query-specific data: - a non-negative weight for each `o` in `S`. - an integer bound `m`. - an "available" flag for each `o` in `S`. It's guaranteed that at least `m` objects are available. The problem is to find a subset `A` of `S` such that the sum of the weights of the objects in `A` is maximized, subject to the following constraints: - `A` contains at most `m` objects. - all objects in `A` are available. - all objects in `A` are compatible with one another. If more than one such subset exists, find any one. Discussion We think we can dispense with the availability flags by setting the weights of unavailable objects to something negative. Removing an unavailable object from `A` will then always improve `A`. We can preprocess the fixed data if that will help. (In fact, we do this for our current algorithm.) The query-specific data are not correlated from one query to the next, so no preprocessing is possible there. Typically, the size of `S` is 800 or so, while `m` is on the order of 5-10. (The 800 might grow significantly in the future.) However, the number of available objects can be as small as `m` (although typically larger). Current status We have implemented a solution based on sorting the available objects by weight and using a greedy algorithm with backtracking to add one object at a time to `A`, removing incompatible objects from consideration at each step. A backtracking bran

Problem: Imagine you are an agent with a knapsack, who travels a known route of cities. All cities are different: $C_1 \rightarrow C_2 \rightarrow \dots \rightarrow C_n$. Each city offers you to buy fixed commodity or to sell it (but only to buy or to sell, never both). Prices are known and available; available volume is also known for each city: $Vol_{C_i}, Price_{C_i}$. So, each city has three values: volume, price and offer_side $\in [ buy, sell ]$. Question: - What is an algorithm to decide, in which cities to buy this commodity and in which to sell and with what volume to maximize total revenue? The constraint is that you cannot carry more than 100 of volume in a knapsack at each point of time. Methods: - I was thinking about knapsack problem, but it is not the case, because I can choose, which volume to put in a knapsack and I can "throw things away" from a knapsack by selling the commodity. - I was also thinking about flow algorithms, but they usually maximize the flow with given edge capacity, but flow algorithms do not have constraints on "total flow" at each time. Moreover, flow algorithms do not have a revenue, but only the max flow...

I'm looking for an algorithm that is closely related to the 2-dimensional nesting problem (also known as lay planning, bin packing, and the cutting stock problem). The main differences between this and normal nesting are: - A fixed number of elements to be placed - The elements cannot rotate - The elements must be placed in as small an area as possible, as opposed to placing as many pieces as possible in a fixed-size area. - The elements are rectangular pieces with 0-4 fixed-orientation rectangular corner cutouts (“Utah-like”), as opposed to being randomly shaped Input: `n` “Utah-like”, fixed-orientation polygons. `n` is in the range 1-20. The figures are not shaped to align perfectly with each other. Example figure set: Desired output: A fixed-orientation nesting for a scaleable area with predefined proportions. The scaleable area should be scaled to fit the nested figures as snugly as possible, like so: Note the area where the figures' rectangular boundaries overlap, preventing this from being a more trivial rectangle-packing problem. I have perused several packing questions on SE (e.g. 1, 2, 3) as well as puzzle-solving questions (e.g. 1, 2, 3), and also outside Stack Exchange (1, 2, 3), but they don't describe this particular problem or don't include source code. Related GitHub repos: 1, 2, 3. Online solvers: SVGnest.com and Nestable.xyz.

I need to solve an optimization problem for a given set of polyominoes, for example the five Tetrominoes known from Tetris. The goal is to place each one of the figures on the 2d grid, so the area they enclose is maximal. Staying with our Tetromino example, the optimal solution would be: Bruteforcing the problem becomes unfeaseable very quickly, especially since my check with bfs search alone that an area is even enclosed at all must be performed countless times. I tried to implement systems to recognize when it won't be possible to close the circle with the remaining polyominoes, but didn't achieve a significant speed-up with them. I also researched into strategies for the related polyomino tiling problem to see if I can adapt them, but had no success so far. The most promising approach I found was to translate it into Mixed-Integer Linear Programming like here or in this variation. But to apply this approach to my problem I need to both add the restriction of the enclosed area and then formulate its size as a linear objective function, whereby especially the encoding of the latter may not be possible at all. Are there other algorithms to find the global maximum for this type of optimization problem that I've overlooked? Or are there data structures or strategies for branch elimination to drastically speed up the search of all possibilities?

Instead of finding a solution to a system of linear inequalities (`Ax + b >= 0`), I want to find any system of linear inequalities that satisfy a set of feasible points and does not satisfy a set of infeasible points. As the image shows, I am given points (either a bunch together or one by one) labelled with in/out, yes/no, or similar binary attribute to know if it should be within the system or not, and I want to find lines that separate these. There should be some inductive method to fit any number of linear inequalities to satisfy these points. It's important that the output is a system of linear inequalities so it can be used as input into linear programming solvers to find new solutions. I've looked into SVM's but the model seams just to be a hyperplane. Maybe it is for use. A one-layer neural network should do the trick but then the number of lines must be set from start. There are a few things to add to this problem. - We want to keep as few lines as possible, or, we want to assume as little as possible of the "true" data set we do not yet fully know of (as any machine learning algorithm does). - For the same reason as 1, we'd like to keep the lines as much "in between" the true and false points (just as SVM's)

A convex polyhedron can be represented by a set of linear inequalities. If the inequalities involve $n$ variables, then the polyhedron can be $n$-dimensional, but it can also be of a smaller dimension - in case some of the inequalities in fact define equalities. As a simple example, the following inequalities: $$x_1 \geq 0, x_2\geq 0, x_3 \geq 0\\ x_1 \leq 1, x_2\leq 1, x_3 \leq 1 $$ define a 3-dimensional polyhedron (a cube). But if the last inequality is changed to $x_3 \leq 0$ then the polyhedron becomes 2-dimensional (a square). What is an algorithm for determining the dimension of a polyhedron given by a set of linear inequalities? EDIT: By "convex polyhedron" I meant any object that can be represented by the intersection of a finite number of half-spaces (i.e., conjunction of finitely many linear inequalities).

I have a basic question, if I can model a problem $(P)$ by a linear program, can we say that $(P)$ is polynomial? Linear programs can be solved using simplex, and it was proved that simplex run in exponential time for some instances, so why some references assume that linear programming is polynomial?

I have a doubt about integrality gap. If I know that there is no integrality gap for a given problem, i.e.: $$\frac{\mathrm{OPT}(\mathrm{ILP})}{\mathrm{OPT}(\mathrm{LP})} = 1 \text{ (right?)},$$ then, does it have sense to do an approximation-algorithm with LP-rounding? I mean, by definition of $\alpha$-approximation, I know that this is true for an algorithm, in case of minimization problem, that: $$\mathrm{SOL} \le \alpha \mathrm{OPT}.$$ But since I want to do an approximation with LP-rounding, isn't $\mathrm{SOL}$ equal to $\mathrm{OPT}(\mathrm{ILP})$? This will mean that $\alpha = 1$ (?). So, if I can design an approximation-algorithm for this given problem, what is the best approximation factor that I can get, given there is no integrality gap?

I have an almost linear programme. However one of the constraints has a form $z = min(x,y)$ (all the other things are linear in the model). Is there a way to substitute this with something (or introduce additional variables) to turn this into a linear programme? In other words, I have the problem that looks like the following: $$ \mathbf c' \mathbf x \to \min, $$ s.t. $$ A \mathbf x = \mathbf b,\quad x_1 = \min(x_2, x_3). $$ Update: I thought about substituting the constraint with $\min$ to the following pair: $x_1 \le x_2$ and $x_1 \le x_3$. However, this doesn't work if $x_1$ has a positive coefficient in $\mathbf c$, which is exactly the case for me. In fact, all the entries are positive in $\mathbf c$.