Tagged Questions
0
votes
1answer
48 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 ...
1
vote
2answers
269 views
Optimization problem: Maximize the sum of minimum.
Given positive integers $L$ and a set of non-negative integers $N$.
Find maximum of:
$$\large \sum_{i = 1}^{4L}\ N_i\cdot(\min(\vert i - c\vert, 4L - \vert i - c\vert))$$
with $c \in \{1, 2,\dots ...
0
votes
1answer
46 views
Lagrangean Relaxation of quadratic assignment problem to yield $n$ knapsack problems?
Consider the assignment problem:
$$ Z = \min \sum_i\sum_j\sum_k c_{jk}\cdot x_{ij}\cdot x_{ik} $$
s.t.
$$ \sum_i x_{ij} = 1 \quad\forall j $$
$$ a \leq \sum_j x_{ij} \leq b \quad\forall i $$
$$ ...
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
43 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 ...
2
votes
1answer
27 views
How is the upper bound of a minimisation IP determined during branch-and-bound?
When using the branch-and-bound algorithm to solve an Integer Programming (IP) problem, the entire enumeration tree doesn't need to be evaluated and that's where the speed-up is achieved.
Suppose the ...
0
votes
2answers
28 views
Minimize error function with integer constraints
Much time has passed since I studied any form of math so I wanted to take this cheap shot of asking someone else to think for me.
I need to write some software that, for any given real number ...
0
votes
2answers
25 views
how to impose binarity constraint in a vector
This is part of a homework problem. In an optimization problem, I need to have a K dimensional vector S, such that each entry of the vector is either 0 or 1, and $l_1$ norm of S is <= K. I can't ...
1
vote
0answers
43 views
How to minimise an objective function which is not a direct function of the decision variable?
I have a problem with partitioning a water network by closing some pipes. I use some graph theory techniques to find some candidate pipes to close; but to select which pipes among them to close (my ...
1
vote
0answers
22 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
65 views
Is 0-1 integer programming always NP-hard?
I have the following problem.
Maximize $\sum\limits_{m=1}^M\sum\limits_{n=1}^N x_{mn}$
subject to: $\sum\limits_{\substack{m^\prime=1\\ m^\prime \neq m}}^M\sum\limits_{\substack{n^\prime=1\\ ...
0
votes
0answers
47 views
Find all $a_i$ such that $(x_{a_1} - x_{a_2} + x_{a_3}) +\ldots + x_{a_{3k}}$ min
Given $n$ numbers $x_1, x_2, \ldots,x_n \in \mathbb{Z}$ and an integer $k \le\frac n 3$. Find $a_i$ $(i = \overline{1,2,3,\dots,3k}),\ 0 < a_i < a_{i+1} \le n$ such that:
$$M = (x_{a_1} - ...
1
vote
1answer
30 views
organizing rectangles on top of each other
We have some rectangles that should be organized in a number of columns. Each column height should be in the range of $[H, H+d]$ in which $d$ is a small number relative to the height of the ...
0
votes
1answer
15 views
Global consistency of constraints in a MIP program
How does a Mixed Integer Programming (MIP) solver ensure global consistency of constraints while adding an additional constraint (during branch and bound). A naive method would be to add the ...
1
vote
0answers
17 views
Internals of a MIP Solver
I would like to learn about the internals of a Mixed Integer Programming (MIP) solver.
Which concepts shall I read about? Are there a couple of standard books which can be a good start?
0
votes
0answers
28 views
Algorithm Request, choosing rows from a sparse table of integers to sum to a minimum row value
I'm writing some software, and one part of the software needs to be able to solve this problem as well as possible. Consider a table of integers and goal, for example:
$$T = \begin{array} ...
1
vote
0answers
161 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 ...
1
vote
0answers
43 views
How to express coprimality as a constraint in an optimization problem over integers?
I am currently working with an optimization problem that is defined over a a set of $D$-dimensional integer vectors where each component is bounded by $M$.
Let us refer to this optimization problem ...
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 ...
2
votes
1answer
168 views
Minimize $\|Ax-b\|$ where $x$ is a binary vector
For a software project I'm involved on, I have a situation where I have a large vector that is the sum of some smaller vectors. I know all the possible small vectors, and I know that no two of them ...
1
vote
0answers
168 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 ...
1
vote
1answer
50 views
How to schedule different planks to form bridges
Suppose we want to walk from place $A$ to place $B$, but there are several rivers between them. In order to walk from place $A$ to place $B$, we need to build a bridge for each river.
We have ...
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 ...
0
votes
1answer
47 views
Checking whether a solution to MIP is optimal
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
0answers
93 views
Why these two problems lead to same answers?
Suppose these two problems:
Problem 1:
$$\min_{X,P} \quad\max_{1\leq l\leq L-1} \quad {|\sum_{1\leq i\leq N_p}^{N_p}x_ie^{\frac{2\pi l}{N}p_i}| \over {\sum_{i=1}^{N_p} x_i^2}} \quad \equiv \quad ...
1
vote
0answers
325 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 ...
2
votes
1answer
68 views
Software for Binary Integer Linear Programs
I am aware that there is good software out there to solve integer linear programs (ILPs). However, is there (preferably free or low cost) software I could use to solve large binary integer linear ...
1
vote
1answer
147 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 <= ...
0
votes
1answer
239 views
Integer Linear Programming (ILP): NP-hard vs. NP-complete?
I was thinking about examples where a problem is NP-hard but was not NP-complete and ILP came to mind.
It is obviously NP-hard but is it NP-complete? I.e., is it in NP? Given a certificate (the ...
1
vote
1answer
77 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
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
0answers
86 views
How to minimize $\min_k k \frac{b^k/n}{\lfloor b^k/n \rfloor}$
This problem looks familiar, but I don't remember its solution:
$$ \min_k \ \ \frac{b^k/n}{\lfloor b^k/n \rfloor}k $$
subject to
$$ b^k \ge n \\ b,n,k \in \mathbb{N} $$
Does it have a name? What's ...
3
votes
5answers
57 views
Why is my procedure misleading?
Max: $ z = 10( x_1 + x_2)$
subject to constraints:
$$ 2x_1 + 5x_2 \leq 16 $$
$$ 6x_1 + 5x_2 \leq 30 $$
$$ x_1, x_2 \in \mathbb{Z^+} $$
I have the Integer Programming ...
1
vote
1answer
63 views
Efficient MIP reformulation for binary integer problem
Consider an integer programming model where there is some term $x_ix_j$ where the variables $x_i,x_j \in \{0,1\}$
I want to reformulate this into an efficient mixed-integer programming (MIP) problem.
...
0
votes
1answer
63 views
Cutting plane in IP system
I am doing branch-and-bound for 5 decision binary variables. so Decision would be 0 and 1.
and I found sub-problem node Q with optimal value 5.4 (0.3, 0.2, 1, 0.5, 0.1)
my IP constraints are
...
3
votes
0answers
108 views
Binary optimization
Let me first make my background clear. I am a PhD student with not much knowledge in optimization but I need to do some optimization as a part of my research work. My problem is as follows:
There are ...
2
votes
1answer
222 views
Maximizing the number of non-crossing lines between a number of points
Suppose I have a number of points in 2-dimensional space. I want to draw as many lines between the points as possible such that no two lines cross.
Hoping for a polynomial time algorithm, I ...
0
votes
1answer
110 views
integer programming formulation problem
Consider a problem with three variables: $u$, $\sigma_l$, and $\sigma_w$ where $\sigma_w > \sigma_l$. I want to represent the following relationship using integer programming.
\begin{equation}
u =
...
2
votes
1answer
285 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 ...
2
votes
1answer
286 views
Unimodular matrix definition?
I'm a bit confused. Based on Wikipedia:
In mathematics, a unimodular matrix M is a square integer matrix
having determinant +1, 0 or −1. Equivalently, it is an integer matrix that is invertible ...
1
vote
1answer
119 views
For integers $a$ and $b \gt 0$, and $n^2$ a sum of two square integers, does this strategy find the largest integer $x | x^2 \lt n^2(a^2 + b^2)$?
Here is some background information on the problem I am trying to solve. I start with the following equation:
$n^2(a^2 + b^2) = x^2 + y^2$, where $n, a, b, x, y \in \mathbb Z$, and $a \ge b \gt 0$, ...
0
votes
1answer
100 views
How to minimize cost of group of items given that weights of item sums up to fixed value and atmost 'n' number of items are allowed?
Given that we have a set of items :- { (c1, w1) , (c2, w2), (c3, w3) , ... } where (ci, wi) are the respective cost and weight of the ith item. Its required to minimize total cost of items C such ...
1
vote
2answers
447 views
LP relaxation for ILP\IP (integer linear programming)
I am familiar with LP relaxation for ILP (or IP). Assume we concern with integer minimization problem, which we formalize using ILP; we then relax the ILP into LP and we say that the LP provides a ...
5
votes
2answers
137 views
Minimize sum of smallest and largest among integers on the real line.
Suppose there are 3 non-negative integers $x$, $y$ and $z$ on the real line.
We are told that $x + y + z = 300$. Without loss of generality, assume
$x$ to be the smallest integer, and $z$ to be the ...
1
vote
0answers
76 views
Problem formulation for maximizing the number of smaller rectangle inside larger rectangle
I stumble upon a problem which i would like to pose it as "Optimization Problem".
Given the dimension of larger and smaller rectangle, i would like to find the maximum number of smaller rectangle ...
1
vote
0answers
211 views
sum of maxima vs the maximum of the sum
Consider the following integer program
$$
\begin{align}
\max &\sum\nolimits_{i,j} U_i(j)\cdot x_{i,j}\\
\text{subject to}& \sum_{i}x_{i,j}\cdot f\left(i,j\right)\leqslant c_j,& ...
1
vote
0answers
242 views
Book recommendation on Applied Integer Programming/Combinatorial Optimization/OR
Having some very basic and theoretical knowledge about these topics from my study, I'm looking for a book (or other good sources) that explains the stuff from a practical point of view. On the one ...
1
vote
0answers
162 views
Optimization via Simulation
I want to minimize and objective function $\hat{B_i}$ $i\in l$, which can be computed by a matlab code (assume $\operatorname{findB}(a, b, c)$ returns $B$. I have the following optimization problem:
...
3
votes
1answer
324 views
Connected graph solution from IP/LP
I have a problem on a graph (of maximum degree $c$) which looks for a connected subset of edges fulfilling some properties.
I have problems formulating the connectedness condition in an IP/LP.
The ...
