-
作者：Boyd, Sylvia; Sitters, Ren; van der Ster, Suzanne; Stougie, Leen
作者单位：University of Ottawa; Vrije Universiteit Amsterdam; Centrum Wiskunde & Informatica (CWI)
摘要：We study the traveling salesman problem (TSP) on the metric completion of cubic and subcubic graphs, which is known to be NP-hard. The problem is of interest because of its relation to the famous 4/3-conjecture for metric TSP, which says that the integrality gap, i.e., the worst case ratio between the optimal value of a TSP instance and that of its linear programming relaxation (the subtour elimination relaxation), is 4/3. We present the first algorithm for cubic graphs with approximation rati...
-
作者：Chen, Xiaojun; Wang, Zhengyu
作者单位：Hong Kong Polytechnic University; Nanjing University
摘要：The dynamic Nash equilibrium problem with shared constraints (NEPSC) involves a dynamic decision process with multiple players, where not only the players' cost functionals but also their admissible control sets depend on the rivals' decision variables through shared constraints. For a class of the dynamic NEPSC, we propose a differential variational inequality formulation. Using this formulation, we show the existence of solutions of the dynamic NEPSC, and develop a regularized smoothing meth...
-
作者：Berthold, Timo; Gleixner, Ambros M.
作者单位：Zuse Institute Berlin
摘要：We present Undercover, a primal heuristic for nonconvex mixed-integer nonlinear programs (MINLPs) that explores a mixed-integer linear subproblem (sub-MIP) of a given MINLP. We solve a vertex covering problem to identify a smallest set of variables to fix, a so-called cover, such that each constraint is linearized. Subsequently, these variables are fixed to values obtained from a reference point, e.g., an optimal solution of a linear relaxation. Each feasible solution of the sub-MIP correspond...
-
作者：Burer, Samuel; Letchford, Adam N.
作者单位：University of Iowa; Lancaster University
摘要：This paper introduces a fundamental family of unbounded convex sets that arises in the context of non-convex mixed-integer quadratic programming. It is shown that any mixed-integer quadratic program with linear constraints can be reduced to the minimisation of a linear function over a face of a set in the family. Some fundamental properties of the convex sets are derived, along with connections to some other well-studied convex sets. Several classes of valid and facet-inducing inequalities are...
-
作者：Gowda, M. Seetharama; Tao, Jiyuan
作者单位：University System of Maryland; University of Maryland Baltimore County; Loyola University Maryland
摘要：A real square matrix is a bilinear complementarity relation on a proper cone in if where is the dual of . The bilinearity rank of is the dimension of the linear space of all bilinear complementarity relations on . In this article, we continue the study initiated by Rudolf et al. (Math Prog Ser B 129:5-31, 2011). We show that bilinear complementarity relations are related to Lyapunov-like transformations that appear in dynamical systems and in complementarity theory and further show that the bi...
-
作者：Kogan, Alexander; Lejeune, Miguel A.
作者单位：Rutgers University System; Rutgers University Newark; Rutgers University New Brunswick; George Washington University
摘要：We develop a new modeling and solution method for stochastic programming problems that include a joint probabilistic constraint in which the multirow random technology matrix is discretely distributed. We binarize the probability distribution of the random variables in such a way that we can extract a threshold partially defined Boolean function (pdBf) representing the probabilistic constraint. We then construct a tight threshold Boolean minorant for the pdBf. Any separating structure of the t...
-
作者：Gupta, Anupam; Nagarajan, Viswanath; Ravi, R.
作者单位：Carnegie Mellon University; International Business Machines (IBM); IBM USA; Carnegie Mellon University
摘要：In a two-stage robust covering problem, one of several possible scenarios will appear tomorrow and require to be covered, but costs are higher tomorrow than today. What should you anticipatorily buy today, so that the worst-case cost (summed over both days) is minimized? We consider the -robust model where the possible scenarios tomorrow are given by all demand-subsets of size . In this paper, we give the following simple and intuitive template for -robust covering problems: having built some ...
-
作者：Ames, Brendan P. W.; Vavasis, Stephen A.
作者单位：California Institute of Technology; University of Waterloo
摘要：We consider the -disjoint-clique problem. The input is an undirected graph in which the nodes represent data items, and edges indicate a similarity between the corresponding items. The problem is to find within the graph disjoint cliques that cover the maximum number of nodes of . This problem may be understood as a general way to pose the classical 'clustering' problem. In clustering, one is given data items and a distance function, and one wishes to partition the data into disjoint clusters ...
-
作者：Hirai, Hiroshi; Pap, Gyula
作者单位：University of Tokyo; Eotvos Lorand University
摘要：Given an undirected graph with a terminal set , a weight function on terminal pairs, and an edge-cost , the -weighted minimum-cost edge-disjoint -paths problem (-CEDP) is to maximize over all edge-disjoint sets of -paths, where denote the ends of and is the sum of edge-cost over edges in . Our main result is a complete characterization of terminal weights for which -CEDP is tractable and admits a combinatorial min-max theorem. We prove that if is a tree metric, then -CEDP is solvable in polyno...
-
作者：Mascarenhas, Walter F.
作者单位：Universidade de Sao Paulo
摘要：We present examples of divergence for the BFGS and Gauss Newton methods. These examples have objective functions with bounded level sets and other properties concerning the examples published recently in this journal, like unit steps and convexity along the search lines. As these other examples, the iterates, function values and gradients in the new examples fit into the general formulation in our previous work Mascarenhas (Comput Appl Math 26(1), 2007), which also presents an example of diver...
