Questions tagged [linear-programming]

For questions related to problems that optimize (i.e., minimize or maximize) a linear objective subject to linear constraints.

Filter by
Sorted by
Tagged with
4
votes
1answer
85 views

Analytically finding the maximizer of a trace optimization problem

$A \in \mathbb{R}^{m \times n}$ is an arbitrary data matrix. Moreover, $w \in \mathbb{R}^m$ is a data vector which is a probability vector, i.e., $w\succeq 0, \sum_{i=1}^m w_i = 1$. I have a ...
5
votes
1answer
86 views

How to linearize difference of absolutes?

How to linearize difference of absolutes? $$|a|\ge k|b|$$ where $a,b$ are variables and $k$ is a constant.
3
votes
1answer
111 views
8
votes
2answers
97 views

how to penalize a shortfall of a sum of absolute values

I have a model where there is a constraint on the sum of absolute values, and I would like to add a penalty on the shortfall from the constraint. More specifically: \begin{align*} \text{maximize}\ &...
3
votes
1answer
87 views

Linear programming explanation in Algorithms by Sanjoy Dasgupta

I am reading about simplex algorithms in a textbook titled Algorithms by Dasgupta-Papadimitriou-Vairani. On each iteration, simplex has two tasks: Check whether the current vertex is optimal (and if ...
4
votes
1answer
205 views

Transforming a Quadratic constraint to SOCP

I have a problem similar to Markowitz portfolio optimization that I would like to transform into second-order cone programming. I have a linear objective function with a quadratic constraint (assuming ...
3
votes
2answers
111 views

Minimizing a variable over the intersection of simplex and linear constraints

I am solving: \begin{align} \begin{array}{rll} y^* = \min & y & \\ \mathrm{s.t.} & a_i^\top x \leq y, & i=1,\ldots,m \\ & x \succeq 0,\ \mathbf{1}^\top x = 1. & \end{array} \...
5
votes
1answer
147 views

Propagate value through a graph

Here is my question where I am propagating distance through the graph, I was wondering if it is possible to do when the graph has cycles, i.e., traveling the same node multiple time then is it ...
2
votes
1answer
134 views

Controlling the constraint execution sequence in docplex

I have tried to implement my question asked here with the help of Github code link. Below is the linearized version of the MTZ like constraint as per the answer given here. Constraints below assign ...
4
votes
1answer
150 views

TSP subtour elimination with multiple formulations

Referring to the question here. Given a set $S$, which we need to travel following TSP rules. I was wondering if this sub tour elimination method is good enough or not? Let $b_{i,j}$ denote edge ...
8
votes
2answers
740 views

Is there a way to view added constraints in Gurobi (Python)?

I should note that I am very new to Gurobi so apologies if this is obvious. I am working on a project for a class to maximize profit on a theoretical flight network by deciding which routes to fly at ...
3
votes
1answer
58 views

How to set combined stop condition in AMPL/CPLEX?

I would like to set a stop condition combined of a timelimit and a relative MIP gap. So I would like AMPL/CPLEX to look for the solution of my LP for an hour and if there isn't a solution stop if or ...
3
votes
1answer
184 views

Linear programming sensitivity analysis using Matlab

I have a linear program in the MPS file format listing all the rows, columns, right-hand sides, etc. I can read that in Matlab and solve it using linprog. However, it seems there is no easy way to do ...
8
votes
1answer
306 views

if-else condition for the objective variable using big M notation

Let $0\leq \beta\leq 1$ be an objective variable. The size of $\beta$ is $N\!\times\!N$. Now, how can I impose the following? if $\beta_{i,j}>0$ then $\beta_{j,i}=0$ Big M notation can be ...
6
votes
1answer
142 views

TSP subtour elimination by assigning distance traveled

Given a set $S$ which we need to travel following TSP rules. I was wondering if this sub tour elimination method is good enough or not? Let $b_{i,j}$ denote edge from $i$ to $j$ is taken or not and $...
3
votes
1answer
56 views

Iterative calculus with Excel - N° 2

In continuation with the previous post, I propose you another problem. I have this model: \begin{align}\min&\quad F\\\text{s.t.}&\quad F-(1150x_{B_{1}}+1000x_{B_{2}}+1350x_{B_{3}}-S_{1})=430\...
5
votes
1answer
120 views

Delayed column generation in Dantzig-Fulkerson-Johnson formulation

In TSP wiki it is said that delayed column generation method is used to solve Dantzig-Fulkerson-Johnson formulation as it has an exponential number of possible constraints. I wanted to know whether it ...
3
votes
1answer
81 views

In Linear programming, how to determine if shadow price does not change linearly?

As the title says, in linear programming, is there a way to determine that the shadow price does not change linearly for a resource? I understand one way is to simulate but is there a way to tell ...
3
votes
1answer
237 views

Iterative calculus with Excel

I have this model: \begin{align}\max&\quad\small{(0.2(1.07)^{-1}+0.2(1.07)^{-2}+0.9(1.07)^{-3})x_A+0.4(1.07)^{-1}+0.5(1.07)^{-2}+0.3(1.07)^{-3})x_B}\\&\quad 0.2x_{A}+0.4x_{B}\geq300\,000 \\&...
4
votes
1answer
135 views

TSP on a non-complete graph

I have a non-complete graph $G$ with $V$ vertices and a set $D \subset V$ that needs to be traveled by a vehicle and then return to source at last. Binary variables $b_{i,j}$ represent if the edge $(...
7
votes
0answers
136 views

Modeling traffic in a city

I am trying to model traffic in a city, $(i,j)$ represents a road in a city. There are $H$ vehicles in a city they have some prescheduled set of destinations to visit, $A_{j,h}$ denotes arrival time ...
5
votes
1answer
516 views

How can I deal with a possibly undefined constraint?

I have a minimization problem minimizing $d_k \geq 0$ and some other variables with all strictly positive coefficients. I leave my objective function below to better convey my goal. $$\min_{\mathbf{d}...
8
votes
1answer
104 views

Scheduling events in order to maximize preparation time

Problem statement I'm given a set of events $E$, and $\forall e \in E$ also: a set of plausible dates on which the event can happen $D_e$ importance (weight) $w_e$ ideal preparation time duration $...
7
votes
3answers
203 views

Constraint that checks for an undirected graph whether it is connected?

I would like to create a constraint with AMPL that checks whether I am able to reach from one node $v$ to all other nodes of a set but I don't really know how to formulate it (especially in AMPL (+...
11
votes
2answers
998 views

Linear programming: objective function with “buckets”

I had a linear programming problem with the following objective function $$f(x) = \sum_{j}x_jq_jp_j - \sum_{i}\left(\sum_{j}x_jq_jC_{ij} \right) c_i$$ Where $q, p, C, c$ are known. This problem was ...
3
votes
1answer
109 views

Gurobi C++: adding variables with vector

I am solving an LP by using GUROBI - C++ combo. Assume I have a variable $p \in \mathbb{R}^n$. I am adding this as a vector: ...
5
votes
1answer
100 views

Preemptive Goal programming by fixing nonbasic variables with non-zero reduced costs

I have been using the method of fixing nonbasic variables with non-zero reduced costs to do preemptive goal programming. It works for the most part. But I have recently noticed in a certain instance ...
8
votes
3answers
619 views

Bin packing variant

I am currently struggling with a bin packing variant, where we have fuel and compartments of a tank truck. Some industry constraints apply, but the whole picture is that you must fit the total volume ...
3
votes
1answer
211 views

Comparing formulation for traveling salesman

I have a graph $G$ and have a set $S$ which are the points in the graph to visit in a TSP manner. Since the length of the TSP route can't be known as it can use any number of nodes to complete the ...
5
votes
3answers
935 views

Solving continuous Minimax Optimization problem

I want to solve a linear programming minimax problem here mathematically without using software: $$\begin{align*} \text{min}\ \text{max} \quad & \{x_1,x_2,x_3\} \\ \text{s.t.} \...
8
votes
1answer
120 views

Choosing better objective function for vehicle routing problem

I have a graph $G$ and the following variables. $b_{i,j}$ is $(i,j)$ edge is taken or not. $t_{i,j}$ is time to travel $(i,j)$ $A_{i}$, $D_{i}$ are arrival and departure time at node $i$. My first ...
6
votes
0answers
76 views

Building the Scheurman's Model II constraints for a multi period linear program

Scheurman's paper discusses Model I and model II Formulation to solve harvesting and scheduling problems. It is a specific implementation to solve multi period linear programs. Both models are also ...
5
votes
2answers
195 views

Trade off between number of constraints and bounds of a variable

I am not familiar with the inner working of the solvers. I mostly use the python pulp or IBM CPLEX solver. For fast execution ...
3
votes
1answer
109 views

Linearizing constraint with continuous and boolean variables

I have two continuous variables $A$, $B$ and two binary variables $x$, $y$. Condition: if $A = B \wedge x = 1 \wedge y=1$ then $z = 1$ else $z = 0$ from In an integer program, how I can force a ...
5
votes
3answers
177 views

Reducing number of suppliers for product portfolio

I have the following matrix of suppliers who are able to make a certain product, against all products in my portfolio. What is the best way of finding the solution to "the least suppliers necessary ...
7
votes
1answer
268 views

Negative reduced cost for basic variable

I am observing something unusual : after solving a linear program, some basic variables have negative reduced costs (instead of $0$) : ...
6
votes
2answers
103 views

Optimising the current model

After developing the MIP model I noticed that solver is taking a lot of time to reach the solution. So, how should I approach to optimize the current model? Are there any visualization tools or any ...
10
votes
2answers
209 views

Can we have all reduced costs (strictly) positive?

I had a number of students claim on their homework that "All $z_j-c_j$ values are positive, therefore the solution is optimal." Of course, I noted that they should say "non-negative" instead of "...
8
votes
2answers
1k views

How to formulate problems in the language of mathematical programming?

The question says it all. I am having difficulties formulating general problems (meaning no numbers just variables). When I read the solution, I understand but I can't figure how to formulate myself ...
3
votes
0answers
36 views

Extract binary value from continuous variable [duplicate]

I have a continuous variable $c$ which has value in between $[-R, +R]$. I want to create a boolean variable $x$ and, $x = 1$ when $c = 1.0$ otherwise $x = 0$ In more general form: $x = 1$ when $c \...
6
votes
0answers
72 views

Benefits of removing slack variables during presolve

I was reading Tobias Achterberg's thesis, and on page 138 he mentions the following presolving technique for linear equations (I'm slightly paraphrasing Example 10.2): Consider the equation $4x_1+...
9
votes
4answers
791 views

Open Source MILP software for Python with user-friendly API to define the optimization problem

Following the accepted answer to Assignment problem where assignments must be done sequentially I would like to write a Python script which can solve the problem defined there. It's a Mixed Integer ...
4
votes
0answers
63 views

Continue on “Is there a known MILP to schedule routes after routes are made”

I have made some progress on my previous question (Is there a known MILP to schedule routes after routes are made). I have derived the sets of the problem, which are: 1) Itineraries of vehicle: $i \in ...
6
votes
1answer
147 views

How to propagate time using linear inequalities?

I have an adjacency matrix $G_{i,j}$ that tells the distance between $i$ to $j$ (between 0 to 1) if there is no edge between $i$ to $j$ I am putting a large integer $100$. This is my previous ...
7
votes
1answer
153 views

Is Dantzig-Wolfe decomposition finite if variables are unbounded?

Most descriptions of the Dantzig-Wolfe decomposition, I have seen end up with subproblems like this: $$\min_{x_j \in \mathbb{R}^n} \{ (\pi A_j - c_j)x_j \mid x_j \in P_j \}$$ They argue that $P_j$ ...
12
votes
1answer
97 views

Improving cuts from sub-problem with problem-specific hierarchical information

I'm solving an assignment-alike problem with a Logic-based Benders decomposition-alike (LBBD) method. The master problem provides an assignment, which is checked in the sub-problem. Define the set of ...
8
votes
2answers
128 views

Bounding arrival time at a node in a resource-constrained shortest path problem

Given a city map (a graph) $G$, $b_{i,j}$ is a Boolean variable for whether or not edge $i$,$j$ is allocated, $d_{i,j}$ denotes the distance between $i$,$j$. The objective is to move from $s$ to $e$ ...
6
votes
1answer
74 views

Linearizing objective function with absolute differences

I want to turn this objective function $$\max \sum_{i=1}^{N-1} \sum_{j=i+1}^N |TX_i^T - TX_j^T|$$ where $T$ is just a vector with increasing integers (e.g $[1 \ 2]$) and $X_i$ is a vector ...
5
votes
1answer
153 views

How to model shipment size constraint?

I am working on an LP problem where I have to model a constraint as: "The total number of units of product A and B should be shipped in multiples of $1200$" e.g. $700\text{(product A)} + 500\text{(...
4
votes
0answers
160 views

Publishing paper that uses LP solver to solve equation

I was reading this paper by Cerna et al. (2018)1. In the paper there are only CPLEX-solvable equations given by the authors and the results. How valuable is this paper, and what is its quality? Can ...