Questions tagged [integer-programming]
Questions on optimization constrained to integer variables.
963
questions
0
votes
0
answers
4
views
How to solve an Integer Programming problem using Gomory's Cutting Plane method, without using the Dual?
How to solve an Integer Programming problem using Gomory's Cutting Plane method, without using the Dual? This is a concept question.
Im not opposed to using the dual in practice. Im just curious why ...
- 329
0
votes
0
answers
36
views
Polynomial Curve Fit without floating point
big math dummy here hoping to get some advice. I'm working on a closed loop servo system that requires a curve fit on some feedback. The controller for this system is $16$-bit. With the help of excel ...
- 1
0
votes
1
answer
16
views
Integer linear Programming - CVRP
I am dealing with a CVRP with multiple vehicles. I am struggling to come up with a formula for the constraint that each node with a non zero demand must be visited by one vehicle, once.
Im trying to ...
- 1
2
votes
0
answers
62
views
Mysterious distributed optimization problem
Problem. Let $x = (x_1,...,x_N) \in K^{N}$, i.e., each element $x_i$ can take at most $K$ discrete values. Let $x_{(i)}$, for $i \in 1,...,I,$ possible overlapping subsets of $x$. For example, for $K =...
- 248
0
votes
1
answer
28
views
On the non-sufficiency of total unimodularity of the constraint matrix in the definition of an integer polytope
Crossposted at Operations Research SE
Is there an example of an $m\times n$ integer matrix $A$ and an integer vector $b\in \mathbb {Z}^{m}$ such that the polyhedron $P := \{ x\in \mathbb {R}^{n} \mid ...
- 698
1
vote
1
answer
30
views
Select a subset to Minimize a continuous unimodal function
I want to find an approximation algorithm for the following problem.
$\qquad$ Find a $S\subseteq N$ such that $\rho(S) = \frac{\sum_{i\in S}\ V_i}{(1+\sum_{i\in S}\ V_i)(4+\sum_{i\in S}\ V_i)}$ is ...
- 11
1
vote
0
answers
26
views
The optimal value function over all doubly stochastic matrices
Let $I = J = \{1,\dots,n\}$. Define set $X \subset \Bbb R^{I \times J}$ as all $n \times n$ doubly stochastic matrices $x = (x_{ij})$ satisfying
$$\sum_{j=1}^n x_{ij} = 1, \quad \forall i $$
$$\sum_{i=...
- 97
2
votes
1
answer
76
views
Convergence Analysis of A Vector Sequence with Discretization Recurrences (with Toy Examples)
I'm confused by how to analyse if a vector sequence is convergent or not. Here I first post the original problem as follows:
(Although this post is long, the problem meaning is easy to understand but ...
- 160
2
votes
1
answer
35
views
Linear program with exponential decay between variables
I'm trying to create a linear program to solve a scheduling problem, below is a description of the problem, I'll try my best to keep it short but comprehensive.
The core of the problem is that a daily ...
- 23
1
vote
1
answer
35
views
How good is an optimal solution of the Lagrangian relaxation of an integer linear program?
From what I learned, the Lagrangian relaxation of an integer program is used to find a bound. Is the solution to the relaxed problem considered to be a good approximate solution of the original ...
- 45
0
votes
0
answers
21
views
Optimization of a function for a variable constrained to a set
I am familiar with the method of Lagrange multipliers for optimizing a function subject to some constraint. However, I have always seen this expressed along the lines of extremising $f(x,y)$ subject ...
- 101
2
votes
1
answer
42
views
The number of feasible subsets of the knapsack problem - the combinatorial explosion
I am reading the book "Integer Programming" by Wolsey (1998). In 1.4, the author is counting the number of the feasible subsets of a knapsack problem. The formulation is
$\max \sum_{j=1}^n ...
- 21
0
votes
1
answer
45
views
Formulate constraints to an Integer programming: How to algebraically formulate a geometric constraint that the colored grids must form a rectangle?
I am stuck in a constraint formulation of a discrete optimization problem. Consider a board of Cartesian grids (M rows by N columns). We are going to color some grids among them. There is a geometric ...
0
votes
1
answer
33
views
Transfer a nonlieanear function to a linear function
I'm using Java to solve a maximization problem in Cplex. My objective function is quite complex. In a nutshell, there are two parts, A and B. Both of them contain variables.
My goal is to maximize A/B,...
- 11
2
votes
1
answer
72
views
Integer eigenvectors of a rational matrix
I have a $2n\times 2n$ rational matrix $A$ for which I know can be diagonalized in the form
$$A=MDM^{-1}$$
where $D$ is a $2n\times 2n$ matrix consisting of half eigenvalues $1$ and half eigenvalues $...
- 411
2
votes
0
answers
33
views
What is the linear description of a transformation of Birkhoff polytope?
Let $I, J$ be finite sets and $|I|=|J|=n$, Let $F$ be a Birkhoff polytope formed by the convex hull of $n\times n$ doubly stochastic matrices:
$$F=\{R^{I\times J}_+: \sum_j x( i,j)=1,\forall i\in I,
...
- 97
1
vote
1
answer
103
views
Primal Dual algorithm for set cover
I am having trouble understanding the approximation algorithm for set cover
using primal dual.
The entire approximation algorithm in a nutshell.
A set cover problem is given
Form the integer linear ...
- 169
1
vote
1
answer
12
views
Combining multiple binary variable combinations in sum statement
I have a question regarding how to formulate a constraint of an MILP.
I have 2 platforms p and v(p) which are neighbours. Depending on the state of both of these platforms a specific value is chosen. ...
- 11
1
vote
1
answer
31
views
Consecutive ones property fails to agree partition condition
I have the matrix below:
$A=\begin{pmatrix}
0&1&0&0&0 \\
0&1&1&1&1\\
1&0&1&1&1\\
1&0&0&1&0\\
1&0&0&0&0\\
\end{pmatrix}.$
...
- 13
2
votes
1
answer
63
views
Given that the positive integers $x>1$ and $y$ satisfy $2007x-21y=1923$. Find sum of digits of minimum value of $2x+3y$.
Given that the positive integers $x>1$ and $y$ satisfy $2007x-21y=1923$. Find sum of digits of minimum value of $2x+3y$.
Here we have to solve for two variables using only one equation. How is ...
user1017704
1
vote
0
answers
55
views
Edge Interdiction Clique Problem seperation of inequalities
I am currently working on the paper A branch-and-cut algrithm for the Edge Inderdiction Clique Problem.
Basically, the problem asks to find a subset of at most $k$ edges to remove from a graph $G$, so ...
- 11
3
votes
1
answer
68
views
Linear minimization over two integers
Given $x\in]0,1[$, let the function $f:\mathbb{N}^+\times\mathbb{N}\to\mathbb{R}$ be defined by
$$ f(p,q) := x p - q $$
Is there an analytic formula for the minimum of $f$ under the constraint
$$ f(p,...
- 165
2
votes
2
answers
54
views
Number of possible combinations that satisfy the constraints
Let $x_{1}, x_{2}, x_{3} \in \mathbb{Z}^{++}$ (i.e., strictly positive integers).
Suppose the following (in)equalities are given:
\begin{align}
x_{1} &\geq x^{\min}_{1} \tag1\\
x_{2} &\geq x^{\...
- 313
1
vote
1
answer
46
views
how to define the dual of a primal assignment-like program with Hadamard product as a cost function?
I need to define the dual of the assignment-like problem where the cost function is defined as the Hadamard product of two matrices $C=[c_{ij}]$ and $X=[x_{ij}]$ as follows:
\begin{align}
\text{...
- 11
1
vote
0
answers
26
views
How much running time does solving a Mixed Integer Linear Program need?
Given a mixed integer linear program with $m$ constraints and $n$ variables how much time do we need to solve this?
I know that MIPs like IPs are in general NP-hard. Nevertheless for IPs one can show ...
- 578
-1
votes
1
answer
39
views
simple linear programming problem with integer constraints
Given positive numbers $a, b, c, d, e$, how do I find the maximum value of $ax + by$ such that $cx + dy \leq e$ and $x, y$ are non-negative integers?
- 1
1
vote
0
answers
34
views
Minimal distance between intersections of a regular grid parameterized by its change-of-basis matrix
Let a 2D grid basis $\mathcal{B}(\theta_1, \theta_2,r_1, r_2)$ whose change-of-basis matrix with respect to $\mathcal{B}_0$ the canonical basis of $\mathbb{R}^2$ writes :
$$P_{\mathcal{B}_0}^{\mathcal{...
- 11
-1
votes
1
answer
61
views
Finding parameters of a linear programming problem
I have the following programming problem:
$\min c_1x_1+c_2x_2$ such that $$x_2 \leq x_1$$$$x_1 \leq 2x_2+2$$$$x_1, x_2 \geq 0$$
How do I show that this problem is feasible and how do i find the ...
user986741
3
votes
2
answers
92
views
Solving a linear system to infer damage values in an RPG
Background. In an RPG game, I've found that the weapon can destroy each object $i$ in a characteristic number of hits. When upgraded, the weapon can destroy each object $i$ in fewer hits. I am trying ...
- 15.8k
2
votes
2
answers
110
views
Find an optimal allocation of groups in an array
Say we have an $n\times m$ array with $n$ and $m$ are odd, and a list of positive integers $(a_1,\dots, a_k)$. Each $a_i$ represents a number of elements which are to be allocated together in a row of ...
- 5,991
1
vote
2
answers
72
views
Binary programming problem. Any closed solution and/or lower bound for this particular case?
Consider the following problem:
$$\begin{array}{ll} \underset{{\bf x} \in \{0, 1\}^N}{\text{minimize}} & {\bf x}^\top {\bf A} \, {\bf x}\\ \text{subject to} & {\bf B} {\bf x} = {\bf c}\end{...
- 13k
2
votes
1
answer
166
views
Write if-else statement in linear programming representation
Given a if-else statement:
If a > 0 and b > 0:
c = 1
else:
c = 0
Where a and b are input variable with fix values.
For example, I have 20 samples and ...
- 75
0
votes
1
answer
72
views
Finding stable sets from a graph
I am trying to understand what a stable set is and have the following graph:
What are examples of a stable set from this graph?
If possible, what is the maximum stable set of this graph?
My current ...
user960518
2
votes
1
answer
39
views
How do you solve the system $Ax=b$ where $\|x\|_1 \leq \delta$ and $x \in \lbrace 0,1 \rbrace^n$?
During my studies I recently met the problem of finding a binary variable $x \in \lbrace 0,1 \rbrace ^n$ that solves
$$Ax=b, \qquad \|x\|_1 \leq \delta$$
I am curious how this system can be solved. ...
- 578
1
vote
1
answer
117
views
Linear constraint considering binary bit position
Right now, I have some binary variables for a linear programming problem:
$x_1\;x_2\;x_3\;x_4\;x_5\;x_6\;x_7\;x_8$
Say these are groups of 4 bits each in this example. So:
Group 1 ={$x_1\;x_2\;x_3\;...
- 75
0
votes
1
answer
39
views
Calculate the expectation of randomization after randomly taking out the element
Suppose we have two vectors $X = \{x_1, x_2, ....,x_n\}$ and $R = \{r_1, r_2, ...., r_n\}$ with $\sum_i^n{x_i} <= 1$ and $0 <= x_i <= 1$. For $R$, we have $R >= 0$, i.e. for all i, $r_i &...
- 1
1
vote
1
answer
45
views
Linear Programming - Job Scheduling Domain Mapping To Binary Decisions
I am trying to maximise machine profit subject to a repair plan (job schedule), but cannot seem to map between the integer domain from the job schedule to the binary domain for the revenue model in ...
- 11
6
votes
1
answer
75
views
Are packing (i.e., independence) numbers arbitrarily smaller than fractional packing (i.e., Rosenfeld) numbers?
Take a graph $G=(V,E)$.
One of the equivalent ways of defining its independence number (also known as $1$-packing number) is
$$\alpha = \max\left\{ \sum_{v\in V}f(v) : \forall v\in V, f(v) \in \{0,1\}\...
- 352
1
vote
1
answer
24
views
Numerical non-convex integer optimization algorithms
Could you please suggest algorithms for solving non-convex integer optimization with constraints? The search space is very large, so branch and bound does not seem practical. A few methods I have ...
- 53
2
votes
0
answers
43
views
Can clustering be implemented as Linear Programming?
When considering Gaussian mixture models (GMM) one efficient algorithm is the Expectation-Minimization (EM) algorithm. The E-step famously determines the degree of membership.
For example, given a GMM ...
- 2,119
2
votes
1
answer
142
views
Maximize $z=(3100y_1 -2850x_1)+(3250y_2-3050x_2)+(2950y_3-2900x_3)$
A company buys and sells grain in cash. The company has a warehouse with a capacity of $5000$ tons. On the first day of March , the stock balance is $1000$ tons and the account balance is $500$ ...
- 868
1
vote
1
answer
41
views
Hat manufacturing company and maximizing $z=8y_1+5y_2$
A hat manufacturing company produces two types of hats. The time required to produce the first type of hat is twice the time required to produce the second type. If all the hats are only of the second ...
- 868
1
vote
0
answers
41
views
How to maximize quadratic form with a integer variables or its relaxation
Let $A$ be a positive semidefinite matrix. Also, let $\forall i\in [1,n], x_i \in \{-1,1\}$. And finally, for some of indices $I\subset \{1,\ldots,n\}$, values of $x_i\in \{-1,1\}$ are known. ...
- 803
2
votes
1
answer
52
views
Find the $6$-tuples $(x_1,x_2,x_3,x_4,x_5,x_6)$ to determine the least number of needed nurses
A simple examination in a hospital shows that the hospital needs the following number of nurses at different times of the day:
\begin{array}{|c|}
\hline
\text{course} & \text{time} & \text{...
- 868
1
vote
1
answer
42
views
Maximizing a quadratic function subject to linear constraints
Consider the problem:
$$maximize: Z = x_1+2x_2$$
subject to: $$x_1+x_2 \leq 8$$ $$-x_1+2x_2 \leq 2 $$ $$x_1-x_2 \leq 4$$
I know that this problem can be solved by using Branch-and-Bound ...
- 77
1
vote
0
answers
58
views
Defining a Minimum cost-flow problem with piecewise costs
I need to formulate an Integer Linear Programming model for a Minimum cost-flow problem over a graph without constraints on edges. The cost over edges isn't linear but piecewise, given by:
$c(x_{ij})=\...
2
votes
1
answer
201
views
How to find numbers like 174
We know Ramanujan number:
$1729 = 1^3+12^3 = 9^3+10^3$
The smallest number expressible as the sum of cubes of two positive integers in two different ways.
We also know how to find other Ramanujan ...
user960916
1
vote
1
answer
32
views
Modeling some constraints
We have two decision variables $x \in \mathbb{Z}^{0+}$ that is the main decision variable and $0 \leqslant y \leqslant 1$ that is an auxiliary decision variable.
Now based on the nature of the problem ...
- 37
0
votes
0
answers
22
views
Show that incidence vectors of s-t paths are the extreme points
Given a directed graph $G=(V,A)$, let $(U, \bar{U})$ be any partition of the vertices such that $s \in U$ and and $t \in \bar{U}$. Such set of $s-t$ arcs where $s$ and $t$ are tail and head, ...
- 180
2
votes
1
answer
41
views
Fixing a minimal number of variables in linear programming problem to worsen objective
Consider a fairly standard linear program with $A\in \mathbb{R}^{m\times n}$ and cost vector $c\in \mathbb{R}^n_{\geq 0}$ such that
$\begin{align*}\text{maximize}&& c^Tx\\\text{such that} &...
- 78