Questions on optimization constrained to integer variables.

learn more… | top users | synonyms

1
vote
1answer
33 views

What is the difference between linear and integer programming?

Recently I tried to solve a maximization integer programming problem using linear programming by flooring the max point - but got the wrong answer. I'm wondering if someone can explain mathematically ...
1
vote
1answer
25 views

Solving integer programming problem using the graphical method

I have an integer programming problem I need to solve using the graphical method. Maximize $55x_1 + 500x_2$ such that $$\begin{align} 4x_1 + 5x_2 &\le 2000\\ 2.5x_1 + 7x_2 &\le 1750\\ ...
3
votes
1answer
88 views

Discrete Linear Programming over Finite Fields?

$A$ is an $l\times m$ matrix with integer entries and each column of which contains at least one negative entry. $y$ is a column matrix with integer entries of length $l$. Define the set of sequence ...
-2
votes
0answers
32 views

How to show this integer program with irrational data has no optimal solutions.

I want to show the integer program with irrational data max$\{x_1-\sqrt{2}x_2:x_1\leq \sqrt{2}x_2,x_1\geq 1,x\in Z_+^2\}$ has no optimal solution, even though there exist feasible solutions with value ...
0
votes
0answers
11 views

Reference Request For Hermite normal form of non full row rank matrix

Could someone recommend me some references which discuss the problem of the reduction of a matrix which is not full row rank into its Hermite normal form?
0
votes
0answers
22 views

Conditions for a totally unimodular coefficient matrix of a Multi-Commodity-Minimum-Cost-Flow-Problem

I'm considering the following Multi-Commodity-minimum-Cost-Flow-Problem: This leads us to a coefficient matrix $A$ with $N$ donates the incidence matrix of a directed graph and $I$ is the ...
1
vote
0answers
25 views

How to interpret this integer program

I'm having problem understanding the min weight st-cut integer programming in this wiki page: https://en.wikipedia.org/wiki/Max-flow_min-cut_theorem In the min-cut dual part, it has $$d_{ij}-p_i+p_i ...
0
votes
1answer
112 views

Normalized objective function in optimization problem

I have fairly standard linear optimization model with two objectives \begin{align*} \text{max}\, (f_1 &= 4x_1+5 x_2\,,\,f_2 = 1x_1 + 0x_2 ) \\ \text{subject to}& \\ 1x_1 + 1x_2 ...
0
votes
0answers
26 views

KKT conditions (equations) for Generalized Assignment Problem or Binary integer programming problem

I have this formulated Generalized Assignment Problem (GAP) or it can also be considered as Binary integer programming problem. Solving this problem can be achieved through Branch and Bound Technique. ...
1
vote
0answers
45 views

Integer programming, system of linear inequalities.

I am woring on a problem and I got these inequalities. $t_{01}+t_{11}+t_{21}\ge 4$ $t_{02}+t_{12}+t_{22}\ge 4$ $t_{10}+t_{11}+t_{12}\ge 4$ $t_{10}+t_{01}+t_{22}\ge 4$ $t_{10}+t_{02}+t_{21}\ge 4$ ...
0
votes
0answers
25 views

Integer program with known non-integer “solutions”

I have an integer program (IP) (see the formulation here for example) with the matrix $A$ being total unimodular. In this case, the linear program (LP) relaxation of the IP provides an integer ...
0
votes
0answers
18 views

Mixed-integer (Linear) Programming (MILP) standard/canonical form

Is there a standard or canonical form for mixed-integer (linear) programming problems? For linear programms the standard form is sometimes given by: $$ \max_{\boldsymbol x} \boldsymbol c^T \boldsymbol ...
0
votes
0answers
21 views

All facets' coefficients contain only integers -1,0,1

Suppose a polytope $C\subset \mathbb R^{kl}$ is the $l$-product of $k-1$-simplex with extreme points containing coordinates $0$ or $1$ in each coordinate. A linear transformation is given by ...
0
votes
1answer
23 views

integer valued outer normal vectors

Suppose a bounded polyhedra $C$ is given by $$x\in \mathbb R^n: Ax\leq b$$ The matrix $A\in\mathbb R^{m\times n}$ contains only elements from $\{-1,0,1\}$, which implies the outer normal vectors of ...
0
votes
0answers
18 views

Minimum Label Spanning Tree of Odd Hole Disjoint Graph

Can the MLST problem be solved efficiently using odd hole inequalities if my graph G is a vertex disjoint union of odd holes with the additional constraint that the max degee of any vertex = 4 and min ...
0
votes
2answers
27 views

Polynomial time solvable cases of the knapsack problem.

Is there some restricted version of the knapsack problem, which is not $Np$-complete and there is a polynomial time algorithm? In my cases the weights are all power of $2$, so $(1, 2, 4, 8, 16, ...
0
votes
3answers
115 views

What are common Mathematical Programming Languages out there?

I've seen the term used Mathematical Programming to describe a superset of: Linear programming Quadratic programming Nonlinear programming Mixed-integer programming Mixed-integer nonlinear ...
1
vote
1answer
57 views

MILP optimization constraint formulation

I'm trying to find a sensible way to add constraint for my optimization problem. Lets assume we have binary decision variables $x_i\in\{0,1\}$ and two constraints \begin{align*} \sum\limits_{i=1}^n ...
1
vote
0answers
24 views

Lenstra's integer programming algorithm: Finding a lattice point “near the center”

Preliminaries: As part of Lenstra's algorithm for integer programming (see here, page 4) we compute a linear transformation $\tau$ and a point $z \in \mathbb{R}^n$ which meet certain conditions (step ...
0
votes
1answer
72 views

Can the “goat cabbage wolf” problem be solved using integer programming?

Question: Can you solve the "goat cabbage wolf" problem using integer programming. If so could I get an outline of the solution or a reference to one?
0
votes
2answers
45 views

Need a solution to a specific problem in integer programming, outlining a general solution or pointing me in a direction.

I just started studying linear programming and I have limited resources with which to work. I have to work on a number of exercises but the notes I have do not help much so I have to look online for ...
0
votes
1answer
37 views

Network flow as a linear/integer programming problem with special conditional constraints

Consider the classic network flow problem where the constraint is that the inflow to a vertex is equal to the sum of its outflows. Consider having a more specific constraint where the flow cannot be ...
0
votes
1answer
18 views

Find the global/local minima of a quadratic function over the set of integer?

Sorry for my poor English, I'm trying to find the global and local minima of a quadratic function: $x^2 - 3x$, with $x \in Z $. Here is my solution: It is straightforward to find the global minima ...
0
votes
0answers
15 views

Multiple Choice Integer Program Special Ordered Set Naming

I have been given a problem, for which I have a hard time to find literature, since I'm unsure about the right name of the problem. The problem is defined as: We have given $k$ sets and we need to ...
1
vote
0answers
62 views

Shadow prices in assignment problems (and their relationship to Lagrange multipliers of LP-relaxation)

Lagrange multipliers for linear programs can be interpreted as shadow prices. Shadow prices typically represent marginal/differential changes in the objective from a marginal loosening of a given ...
1
vote
1answer
36 views

Binary variable in a constraint

I have the following optimization problem: Model I: $$f(x,y) \\ s.t., \\ y\leq x+M(1-V)\\ y \leq MV \\ x \geq 0, y \geq 0$$ where x and y are continuous variables whereas V is a binary variable. M ...
0
votes
1answer
31 views

How to formulate LP for shortest path problems?

I'm trying to understand how LP formulaton for shortest path problem. However I'm having trouble understanding constrains. Why this formulation work? http://ie.bilkent.edu.tr/~ie400/Lecture8.pdf ...
0
votes
1answer
90 views

Binary integer program with nonlinear function

I have given a matrix $A^{m \times n}$ and I am looking for a submatrix $B^{m \times k}$ for a given $k$ that maximizes the following expression: $$\sum_{i=1}^m \max_{j \in \{1 \dots k\}} B_{i,j}$$ ...
0
votes
2answers
23 views

Mixed Integer Linear Programming Conditional Constraints

I have a set of variables: $x_1,x_2,x_3,x_4$ $x_1$ is a binary integer variable while the rest are real numbers all between 0 and 1 I want a constraint such that: if $x_2+x_3+x_4$>0 then $x_1$=1 ...
0
votes
2answers
20 views

Integer Programming Conditional Constraints

I have a set of integer [0,1]variables $x_1,y_1,x_2,y_2,x_3,y_3,x_4,y_4$ I want a conditional constraint such that if any of the $x$ variables is equal to 1, I want the sum of the subsequent $y$ ...
3
votes
1answer
109 views

Linear constraints to placing N queens on an N x N chessboard?

I'm trying to formulate the problem of placing N queens on an N x N chessboard such that no two queens share any row, column, or diagonal. I managed to define my decision variable as x[n][n], a ...
0
votes
1answer
59 views

Is this matrix totally unimodular? [closed]

Is this matrix totally unimodular? Thank you in advance! $A=\begin{pmatrix} -1& 0& 0& 0& -1\\ 0& 1& 1& 0& 0\\ 1& 0& 0& 1& 0\\ 0& ...
0
votes
0answers
47 views

Hungarian Method algorithm question. Dual solution.

I have included two images which I have to prove the next problem. The first image is the alternate(k) algorithm (alternate paths algorithm) and the second is the Hungarian Method algorithm. ...
1
vote
2answers
47 views

How can I maximize this expression?

Let $d_1,...,d_n$ be non-negative integers such that $d_1 + ... + d_n = n -1$ and $d_{i} \leq i$. What is the value of the following expression: $\sum_{i=1}^n d_i (n - i)$ when maximized (a good ...
0
votes
0answers
19 views

Clique Cut or Clique Inequality?

I should study the clique cut (or clique inequality), but I try and search, I don't find anything. please if possible, you introduce to me the book (or article or document) about the mater. thanks
2
votes
0answers
26 views

Showing the integrality property for an Integer Linear Program

I am trying to figure out why solving a relaxed Integer Linear Program (ILP) always give an integral solution. The ILP can be summarized as: $$\min \sum_{t\in T} \sum_{s \in S} c_s k_s^t $$ subject ...
0
votes
0answers
11 views

Definition of support of a nonzero vector

I am studying integer programming and specifically Graver Basis and Circuits. However, to define a circuit they use the term of support of a non zero vector $supp(c)$ and say it is minimal. Does ...
0
votes
1answer
51 views

Linear programming. Find the maximum number of vertex disjoint paths in a directed graph.

How I can write like an objective function subject to its corresponding restriccions the next problem? (max "...") subject to ($\sum "..." - \sum "..."=0$ $\forall$ "...") I have a directed graph ...
0
votes
1answer
17 views

The cost function in the Weighted Bipartite Matching Problem (a.k.a the Assignment Problem)

In the definition of this problem, the weight/cost function generally takes value in $\mathbb{Z}$ (or sometimes $\mathbb{Q}$). This is what I observed from some books (e.g. "Combinatorial ...
0
votes
1answer
28 views

Beyond quadratic in binary integer programming

If I have an integer programming problem with binary decision variables in a quadratic objective function with quadratic constraints, I can solve it using branch and bound in a few different solvers. ...
0
votes
1answer
19 views

Integer Programming Problem - Machines To Products

A man is trying to decide how he can assign his five machines to four products in order to maximize output. The estimated output per day for each machine is shown and reflect its productivity for each ...
0
votes
0answers
11 views

Totally uni-modular matrix

I encountered the following matrix and am wondering whether it is totally uni-modular or not: $$\begin{bmatrix} A_{n\times m} & 0_{n\times m}\\ I_{n\times m} & I_{n\times m}\\ ...
2
votes
2answers
62 views

Linear Programming Model (or IP) - Staff Allocation

A retailer is trying to decide how best to assign its 3 staff to two internal departments in order to maximize sales. The estimated sales revenues per day for each staff member are shown and reflect ...
2
votes
0answers
33 views

Approximate algorithms for integer linear programming (for optimal subset selection)

I'm trying to select an optimal subset of some items. I've tried 2 optimal approaches (branch-and-bound and integer programming) but both proved impossible for the size of the problem. I'm wondering ...
1
vote
1answer
26 views

How to increase the lower bound on possible counter-examples to the Collatz Conjecture?

According to Wikipedia, all positive integers up to $2^{60}$ have been tested and follow the Collatz Conjecture. This got me thinking, could one write a program that tests integers of the form $2^{60} ...
1
vote
0answers
23 views

Social welfare convergence in large assignment problems with random utilities

Suppose there are $N$ agents each to be assigned one of $N$ objects. The utility an agent gets for a particular object is drawn uniformly, i.i.d., from the set of integers between $0$ and $100$ ...
0
votes
1answer
23 views

Optimization of a colour graph

Formulate as a discrete optimization problem: Label each node of the graph with a different non negative integer number, in such a way that the numbers of the nodes of each path composed of the same ...
1
vote
1answer
28 views

Defining an integer (binary) linear program to solve a logistics problem

As an analogy, lets say I have $k$ buckets and $n$ items I want to put into these buckets. So we have binary variables $x_{ij}$ ($1 \leq i \leq n$, $1 \leq j \leq k$), whether or not we put the ...
0
votes
2answers
94 views

Binary integer LP problem

Joe Henderson runs a small metal parts shop. The shop contains three machines – a drill press, a lathe, and a grinder. Joe has three operators, each certified to work on all three machines. ...
0
votes
1answer
47 views

Formulation of mutually exclusive condition

So I have two integer variable and they can be one of the following $x=0, y=1$ $x=1, y=0$ $x=2, y=0$ how can I formulate this as an integer program? I've gotten $x + y \le 2$ and $y \le 1$ ...