0
votes
0answers
20 views

Finding the optimal solution to an ILP, when feasibility is not ultimately required

I have the following problem: I would like to solve an ILP with binary variables, i.e. I have a set of possible items, each having properties like "size" "weight" "value" "age" and so on, in total, ...
0
votes
1answer
29 views

Can there be a unique natural number vector solution to $Ax =b$ where $A$ is not a specific type of square matrix?

Let $A$ be $(n-1) \times n$ matrix that is of the following form: $$\left( \begin{array}{ccc} n-1 & 1 & 0 &.... & ....\\ 0 & n-2 & 2 & .... & ....\\ 0 & 0 & n-3 ...
0
votes
1answer
50 views

Shortest path problem: dual formulation and proof of total unimodularity

The IP formulation of the shortest path problem looks as follows: \begin{align*} \min & \sum_{u,v \in A} c_{uv} x_{uv}\\ \text{s.t } & \sum_{v \in V^{+}(s)} x_{sv} - \sum_{v \in ...
0
votes
1answer
38 views

Almost linear programming problem

I have a problem that is almost the typical in linear programming, but not quite. All variables take real non-negative values. Certain simple linear inequalities and equalities should hold. But what ...
0
votes
1answer
25 views

Disjunction of conjunction in linear programming

I'm trying to get my model working with less variable/constraints possible. I want the binary variable $R$ to store the result of this Boolean expression: R = (a1 and b1) or (a2 and b2) or (a3 and ...
0
votes
0answers
19 views

Name search for special Linear Mixed Integer Programm

I am looking for a name for the following question in literature! (and if you know it, then it would be great) I couldn't find it and due to wide audience here, presumably you know more. Thank you ...
0
votes
0answers
31 views

Mixed Interprogramm remodeling

for example i have the following problem min z 5 x_1a + 6 x_1b - 3 x_2a + 0 x_2b <= z -3 x_1a + 0 x_1b - 1 x_2a + 2 x_2b <= z x_1a + x_1b = 1 (Constraint say of this group only one variable ...
1
vote
0answers
44 views

Minimising waste in a cutting problem.

I have three possible board sizes: $8$, $10$ and $12$ feet long. I want to make some number of cuts to these, say, $3, 2,1,1,1,6,5,3,4,2,1$ feet cuts and I want to minimize waste. I've done a quick ...
1
vote
1answer
49 views

Why optimization problems cannot be solved by simple derivative?

Let $f(\cdot)$ be a linear function. $f:\mathbb{R}^n\rightarrow\mathbb{R}$ $\;\quad\;\mathbf{x}\;\rightarrow f(\mathbf{x})$. Let $\mathbf{A}$ be a matrix in $\mathbb{R}^{m\times ...
0
votes
1answer
56 views

primal and dual lp optimal?

I have a simple assignment problem. I have four tasks that can be assigned to two persons. It is possible that not every task is assigned to a person due to capacity limitations. Each task requires: ...
1
vote
0answers
65 views

Help solving this linear (?) programming problem with odd integer constraints.

I would like some help writing the following linear (integer? quadratic?) programming problem in matrix form including the application of the constraints. I am drawing a dashed line around the ...
1
vote
0answers
23 views

Highest (lowest) index of positive time-indexed variable

I have a simple problem involving a variable $x_{it}$ representing the amount of a resource allotted to a task $i$ in time $t$. The quantity of the (renewable) resource is constrained at a value $R$ ...
1
vote
0answers
64 views

Integral Farkas Lemma

The context of this question is commutative algebra, however the question itself is more related to convex geometry. All necessary information is given. In the proof of Lemma 3.1.1 in the book ...
0
votes
1answer
80 views

How to enforce a constraint that a decision variable can only take 1 of $k$ integer values?

How would you enforce the constraint that $x$, a decision variable, can only take values -3, 7, or 19? I think I probably need to introduce a binary variable here but not sure where to start. Thanks. ...
0
votes
1answer
47 views

Designing an algorithm to determine if a linear combination of k-1 sets is contained in the k-th set .

I am trying to solve the following problem - given $k$ sets : $A_1,A_2,...,A_k$ containing $O(n)$ integers each I need to design an algorithm that will determine if there is such a group of elements ...
1
vote
0answers
167 views

Constraints of a linear programming problem

QUESTION Sandy Arledge is the program scheduling manager for WCBN‐TV. Sandy would like to plan the schedule of television shows for next Wednesday evening. Of the nine possible one‐half hour ...
0
votes
1answer
32 views

Sufficient conditions for relaxed integer programs to have integer solutions.

Suppose we are given an integer program and we remove the integrality constraints to get a relaxed linear program. Are there a set of sufficient conditions on the form of the linear program, (e.g. ...
0
votes
0answers
47 views

Integer programming with pairwise relaxations: optimality?

In David Sontag's thesis [1] (page 11, 3rd paragraph from the end), it is mentioned that "Most previous linear programming approaches to approximate inference optimize over the pairwise LP ...
0
votes
1answer
57 views

Integer Programming

I've been having trouble getting started with this problem. Suppose $x_1,x_2,x_3$ are integers $\geq 0$, satisfying $$21.7x_1-18.2x_2-19.4x_3=5.3$$ Then show $$7x_1+8x_2+6x_3=3+10z_1$$. ...
1
vote
0answers
38 views

Regression/compressive sensing with non-linear constrains where the coefficients are assumed to be integer or binary {0,1}

The following regression problem $$ \mathbf{y} = \mathbf{A}\mathbf{x} $$ where $\mathbf{y}$ is a $N\times 1$ column real vector, $\mathbf{A}$ is a $N\times M$ real matrix where each column ...
0
votes
1answer
105 views

Maximize two-variable linear function

How would you maximize the following function (with integer domain) $$f(x,y) = a * x + b * y$$ subject to $$c * x + d * y \leq N$$ $$x \geq 0, y \geq 0$$ the constants $a, b, c, d, N$ are known ...
1
vote
0answers
171 views

Strange but practical Bin packing problem

I am trying to solve the following MILP through LP solve. A link for the original problem is here I am re-iterating the problem as follows: I am trying to write an application that generates drawing ...
0
votes
1answer
88 views

Intersection of Cartesian product and set - what is the meaning?

I came across the following two definitions in a book about Integer Programming: Definition 1.1 A subset of $R^n$ described by a finite set of linear constraints $P=\{x \in R^n: Ax \leq b \}$ is a ...
1
vote
0answers
65 views

Speeding up solution of a binary integer program

To solve the problem of making a "good" schedule for a tournament between N teams, using memories from my (long gone) student days, I expressed it as a binary integer program. With the current set of ...
1
vote
1answer
35 views

Does a linear expression exist for these ILP variables?

I am formulating an integer linear program. Suppose I have a set of binary variables $X_{i,j,k}$ that is $1$ if subject $i \in I$ is taught by lecturer $j \in J$ during timeslot $k \in K$, or $0$ ...
1
vote
0answers
331 views

How does Microsoft Excel Solver's Simplex algorithm deal with integers?

I was wondering how the Simplex algorithm in Excel's Solver deals with integers. From what I understand, the Simplex algorithm is meant to be used for linear programming/optimizations only. Yet, Excel ...
1
vote
0answers
30 views

If the following LP has an integral solution

I know the constraints matrix A of a linear program "Min cx such that Ax>=b" is totally unimodular. So, the program has integral solutions for integral vector b. If this is also the case for the ...
1
vote
1answer
305 views

linear programming constraint for conditional

I having formulating the following (what should be fairly simple) ilp constraint. Basically let $p$ be a binary variable and $s$ be an integer that is greater than or equal to 0. The constraint is ...
0
votes
0answers
172 views

Its just one point… How do I find it?

Okay so here is the deal... I have a CLOSED convex polyhedron $Ax \le b$ (where $x$ is in $R^n$) and it has i vertices denoted $V_i$ such that $V_i = (x_{i1}, x_{i2}, \ldots, x_{iN})$ where $0 \le ...
1
vote
1answer
149 views

Characterization of Subset Sum via Linear Programming

I have a sample subset sum problem. Given numbers $x_1, x_2... x_N$ and a target value to sum to $x_S$ Minimize $x_S - x_1y_1 - x_2y_2 - x_3y_3 ... x_Ny_N$ such that 0 <= $y_1$ <= 1 0 <= ...
1
vote
1answer
138 views

Integer linear programming, energy constrained max-flow problem, column generation

We have graph $(V,A)$, $V$ is teh set of nodes, $A$ is the set of arcs. There is a source node $s \in V$ and a sink $t \in V$. Each node $i$ has a battery with capacity $E_i$. Sending flow on arc ...
1
vote
1answer
80 views

Minimizing deviations from threshold value from a given group of numbers

Given a set of numbers $a_n$, a threshold level $t$, how do I find the combination of numbers that will sum to at least the threshold with minimum deviation? Added: That is, they must always exceed ...
0
votes
1answer
107 views

Partial linear relaxation yields an integer solution

Consider a binary integer program \begin{align} \min \quad &\sum _{j \in J}f_j x_j +\sum _{i \in I} c_i y_i \notag \\ \mbox{s.t.} \quad &\sum _{j \in N_i} x_j \ge 1-y_i, \quad \forall i\in I ...
1
vote
1answer
201 views

Strict inequality in MILP

I have a problem with the following constraint. There are 2 variables $p \in [0,1] \subseteq \mathcal{R}$ $\sigma \in [0,1] \subseteq \mathcal{Z}$ The constraint over the variables is $c - p < ...
1
vote
1answer
156 views

How tell if a polyhedron contains a lattice point

So given a polyhedron $Ax \le b$ Is there an Algorithm or formula to determine whether said polyhedron contains a lattice point (integer point) I was thinking a couple things: brute force ...
1
vote
1answer
1k views

Linear programming vs. Integer programming

I was trying to solve a problem where I want to choose which items to choose where each item has a number b_i associated with it and a reward r_i associated with it. I need to choose items that ...
4
votes
1answer
269 views

Is the inverse of an invertible totally unimodular matrix also totally unimodular?

My question is learned from here. Let me restate it as follows: A unimodular matrix $M$ is a square integer matrix having determinant $+1$ or $−1$. A totally unimodular matrix (TU matrix) is a matrix ...
1
vote
1answer
149 views

Linear Programming for Integer Solutions

Connsider the linear programming problem Max $z = 5x_1 + 6x_2$ st. $10x_1 + 3x_2 \leq 52,2x_1 + 3x_2 \leq 18$ and $x_1, x_2 \geq 0$ and integer. How would one manipulate the resources so that the ...
1
vote
1answer
147 views

Are there 0-1-matrices that are not unimodular?

I am just wondering if there are matrices that only consists of $0$s and a few $1$s that are not totally unimodular (TU)? I cannot come up with an example but I am not very experienced with this ...
2
votes
1answer
394 views

Linear programming problem with no objective function

I have a binary integer programming problem for which I only need a solution that meets all the constraints. I do not have an objective function that I am trying to minimize or maximize. I've been ...
2
votes
3answers
184 views

How to formulate Unique value constraint in Integer Programming?

Given the following integer programming formulation, how can I specify that the variables are unique and none of them has the same value as the other one. basically ...
3
votes
1answer
93 views

A particular ILP where the existence of a relaxed solution implies the existence of an integer solution

This question emerged from a discussion on my previous question Determining quickly whether this Integer Linear Program has any solution at all, which I would like to elaborate separately. I am ...
4
votes
1answer
290 views

Determining quickly whether this Integer Linear Program has any solution at all

I've got an integer linear program of the form $$ \begin{aligned} \text{Minimize}&& c &= x_1 + \cdots + x_m \\ \text{subject to}&& A\mathbf{x} &\geq \mathbf{b} \\ \text{where} ...
2
votes
1answer
240 views

Linear Programming: Breaking Variables Product

Given two sets of binary variables $x_{i...N} \in X$ and $y_{i...M} \in Y$ and another binary variable $\alpha$ how can I linearize the following constraint, i.e break the product of variables? ...
1
vote
1answer
169 views

Linear Integer Programming: consecutive/adjacent variables constraint

Given a set of binary variables $x_{ij} \in X,\ i=0,..,N,\ j=0,..,M$ how do I model an adjacency constraint on $i$'s such that: $\sum_i^N\sum_j^Mx_{ij} = \alpha, \;\text{with }\ 0 < \alpha < ...
2
votes
1answer
296 views

A variation of the Assignment Problem

In the following Wikipedia article about the Assignment Problem in the Example section, it says: Similar tricks can be played in order to allow more tasks than agents, tasks to which multiple ...
1
vote
1answer
83 views

Linear programming: expressing the fact that precisely $k$ variables are nonzero

Given some variables $x_1,\ldots,x_n$ is it possible to somehow express in a linear program the fact that precisely $k$ of them are non-zero? I suspect this would already be enough to simulate ...
7
votes
5answers
3k views

Good software for linear/integer programming

I never did any linear/integer programming so I am wondering the following two things What are some efficient free linear programming solvers? What are some efficient commercial linear programming ...
1
vote
2answers
69 views

What's the relation between the non-convex sets and the hardness of ILP problems?

If some or all of the unknown variables are required to be integers, then the problem is called an integer programming (IP) or integer linear programming (ILP) problem. If understand ...
0
votes
0answers
184 views