Questions tagged [integer-programming]

Questions on optimization constrained to integer variables.

Filter by
Sorted by
Tagged with
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 =...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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=...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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,...
user avatar
  • 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 $...
user avatar
  • 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, ...
user avatar
  • 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 ...
user avatar
  • 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. ...
user avatar
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}.$ ...
user avatar
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 ...
user avatar
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 ...
user avatar
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,...
user avatar
  • 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^{\...
user avatar
  • 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{...
user avatar
  • 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 ...
user avatar
  • 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?
user avatar
  • 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{...
user avatar
-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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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{...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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. ...
user avatar
  • 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\;...
user avatar
  • 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 &...
user avatar
  • 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 ...
user avatar
  • 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\}\...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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$ ...
user avatar
  • 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 ...
user avatar
  • 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. ...
user avatar
  • 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{...
user avatar
  • 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 ...
user avatar
  • 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})=\...
user avatar
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 ...
user avatar
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 ...
user avatar
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, ...
user avatar
  • 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} &...
user avatar

1
2 3 4 5
20